java源码解读--identityhashmap

IdentityHashMap

IdentityHashMap不常被用到，我也是这次系统性看集合源码时才发先这个类，感觉这个类的实现比较有意思。

1. 首先这个类底层没有使用自己特殊的数据结构(hashmap内部使用node，linkedhashmap使用entry等)，IdentityHashMap底层直接使用Object数组实现，奇数下标存储键，偶数位下标存储值
2. identityHashMap使用==来判断两个键是否相等，这个特性使得identityHashMap中的键可以重复
3. identityHashMap使用System.identityHashCode进行存储位置查找，而HashMap使用Object中的HashCode实现

System.identityHashCode与Object.hashCode区别

1. hashCode是Object类下的一个方法，子类可以继承、重写该方法，根据对象内存地址计算哈希值。比如String类重写了hashCode方法，并改为根据字符串序列计算哈希值
2. identityHashCode方法是System类中的静态方法，根据对象内存地址计算哈希值

public static void testHashCode() {
    // a，b是不同的对象
    String a = new String("string");
    String b = new String("string");
    //String类重写了hashcode方法，只要内容一样，hashcode就相等
    System.out.println(a.hashCode() + "   " + b.hashCode());
    //由于两个对象不一样，所以System.identityHashCode结果不一样
    System.out.println(System.identityHashCode(a) + "   " + System.identityHashCode(b));

    //c,d是一个对象，因为没有使用new String，所以"string"是常量，存在于常量池中
    String c = "string";
    String d = "string";
    //c,d字符串一样，所以哈希吗一样
    System.out.println(c.hashCode() + "   " + d.hashCode());
    //由于是同一个常量，所以identityHashCode一样
    System.out.println(System.identityHashCode(c) + "   " + System.identityHashCode(d));
}

类定义

该类继承了AbstractMap，实现了Map接口

public class IdentityHashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, java.io.Serializable, Cloneable

重要的成员变量和类变量

//默认初始大小，必须是2的幂次，
   private static final int DEFAULT_CAPACITY = 32;
//最小容量
   private static final int MINIMUM_CAPACITY = 4;
//最大容量
   private static final int MAXIMUM_CAPACITY = 1 << 29;
//存储结构
   transient Object[] table; // non-private to simplify nested class access
//键值对个数
   int size;
//修改次数
   transient int modCount;
//null key对应的value
   static final Object NULL_KEY=new Object();

构造函数

   public IdentityHashMap() {
//默认初始容量
       init(DEFAULT_CAPACITY);
   }

   public IdentityHashMap(int expectedMaxSize) {
       if (expectedMaxSize < 0)
           throw new IllegalArgumentException("expectedMaxSize is negative: "
                                              + expectedMaxSize);
//使用传入的容量大小
       init(capacity(expectedMaxSize));
   }

   public IdentityHashMap(Map<? extends K, ? extends V> m) {
       // Allow for a bit of growth
//扩容10%
       this((int) ((1 + m.size()) * 1.1));
       putAll(m);
   }

capacity

此函数返回最小的大于expectedMaxSize的2次幂

private static int capacity(int expectedMaxSize) {
    // assert expectedMaxSize >= 0;
    return
        (expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY :
        (expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY :
        Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
}

hash

使用System.identityHasCode求哈希值

//返回对应的下标index
   private static int hash(Object x, int length) {
       int h = System.identityHashCode(x);
       // Multiply by -127, and left-shift to use least bit as part of hash
       return ((h << 1) - (h << 8)) & (length - 1);
   }

put

   public V put(K key, V value) {
//如果key==null，返回一个固定的Object对象作为键
       final Object k = maskNull(key);

       retryAfterResize: for (;;) {
           final Object[] tab = table;
           final int len = tab.length;
	//求元素对应的数组下标值
           int i = hash(k, len);
	//如果发生hash冲突，会调用nextKeyIndex向后探测没有使用的位置
           for (Object item; (item = tab[i]) != null;
                i = nextKeyIndex(i, len)) {
	//此处注意，判断键是否相等使用==，不是用equals
               if (item == k) {
                   @SuppressWarnings("unchecked")
		//冲突则把value替换，返回旧值
                       V oldValue = (V) tab[i + 1];
                   tab[i + 1] = value;
                   return oldValue;
               }
           }
	//更新size
           final int s = size + 1;
           // Use optimized form of 3 * s.
           // Next capacity is len, 2 * current capacity.
           if (s + (s << 1) > len && resize(len))
               continue retryAfterResize;

           modCount++;
	//key放在i
           tab[i] = k;
	//value放在i+1
           tab[i + 1] = value;
           size = s;
           return null;
       }
   }

get

   public V get(Object key) {
//如果key是null，返回null对应的Object对象
       Object k = maskNull(key);
       Object[] tab = table;
       int len = tab.length;
//查找key对应的下标
       int i = hash(k, len);
//遍历table，由于采用向后探测的方式解决hash冲突，所以这里回循环找下去
       while (true) {
           Object item = tab[i];
	//找到对应key，返回value
           if (item == k)
               return (V) tab[i + 1];
           if (item == null)
               return null;
	//若没有找到，有可能发生hash冲突，向后寻找
           i = nextKeyIndex(i, len);
       }
   }

nextKeyIndex

向后探测逻辑比较简单，每次移动一个key-value的位置，即2个index

private static int nextKeyIndex(int i, int len) {
    // 往后移两个单位
    return (i + 2 < len ? i + 2 : 0);
}

resize

   private boolean resize(int newCapacity) {
       // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
//扩容一倍 
       int newLength = newCapacity * 2;

       Object[] oldTable = table;
       int oldLength = oldTable.length;
//判断新容量是否合法
       if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
           if (size == MAXIMUM_CAPACITY - 1)
               throw new IllegalStateException("Capacity exhausted.");
           return false;
       }
       if (oldLength >= newLength)
           return false;

       Object[] newTable = new Object[newLength];
//把oldTable里的元素重新放入newTable
       for (int j = 0; j < oldLength; j += 2) {
           Object key = oldTable[j];
           if (key != null) {
               Object value = oldTable[j+1];
               oldTable[j] = null;
               oldTable[j+1] = null;
	//重新计算老元素在newTable中的index
               int i = hash(key, newLength);
	//发生冲突，向后探测
               while (newTable[i] != null)
                   i = nextKeyIndex(i, newLength);
               newTable[i] = key;
               newTable[i + 1] = value;
           }
       }
       table = newTable;
       return true;
   }

remove

  public V remove(Object key) {
      Object k = maskNull(key);
      Object[] tab = table;
      int len = tab.length;
      int i = hash(k, len);

      while (true) {
          Object item = tab[i];
          if (item == k) {
              modCount++;
              size--;
              @SuppressWarnings("unchecked")
                  V oldValue = (V) tab[i + 1];
//删除value
              tab[i + 1] = null;
//删除key
              tab[i] = null;
//该位置上的元素被删除后查找后面是否有元素可以被往前移动
              closeDeletion(i);
              return oldValue;
          }
          if (item == null)
              return null;
          i = nextKeyIndex(i, len);
      }
  }

closeDeletion

   private void closeDeletion(int d) {
       Object[] tab = table;
       int len = tab.length;

       Object item;
//查看下一个key的位置上元素是否满足移动要求
       for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
            i = nextKeyIndex(i, len) ) {
	//求下一个元素的哈希值
           int r = hash(item, len);
	//如果出现过hash冲突，并且符合条件，把冲突的键值对向前移动
           if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
               tab[d] = item;
               tab[d + 1] = tab[i + 1];
               tab[i] = null;
               tab[i + 1] = null;
               d = i;
           }
       }
   }