在JDK 1.7 中， HashMap是通过数组 + 链表的结构进行实现

image.png

HashMap的使用

  1. HashMap<String, String> map = new HashMap<>();
  2. map.put("spectrumrpc", "spectrum");

先看其构造函数
使用默认的容量16，以及默认的负载因子0.75，进行初始化
将传入的两个变量保存到 loadFactor，以及threshold中

  1. public HashMap() {
  2.     this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
  3. }
  5. public HashMap(int initialCapacity, float loadFactor) {
  6.     if (initialCapacity < 0)
  7.         throw new IllegalArgumentException("Illegal initial capacity: " +
  8.                                            initialCapacity);
  9.     if (initialCapacity > MAXIMUM_CAPACITY)
  10.         initialCapacity = MAXIMUM_CAPACITY;
  11.     if (loadFactor <= 0 || Float.isNaN(loadFactor))
  12.         throw new IllegalArgumentException("Illegal load factor: " +
  13.                                            loadFactor);
  15.     this.loadFactor = loadFactor;
  16.     threshold = initialCapacity;
  17.     init();
  18. }

  • 在进行put操作时,首先先判断table属性是否为空数组，因为在构造函数中没有进行初始化，在属性进行初始化时，定义为了EMPTY_TABLE，所以在第一次put的时候，将会进行inflateTable逻辑

    1. if (table == EMPTY_TABLE) {
    2.   inflateTable(threshold);
    3. }

    • inflateTable(int toSize) 进行table属性的初始化，这里的toSize就是在构造函数中传入的initialCapacity容量，可以通过有参构造器进行指定，但是，这里的初始化容量并不是严格按照传入的参数进行初始化，而是会通过 roundUpToPowerOf2 去计算大于等于这个数的最小2次幂，如传入的大小为6，通过这个函数，算出来的大小为8，如果为20，算出来的大小为32，即会初始化一个大于等于传入数的最小2次幂的数组

      1. private void inflateTable(int toSize) {
      2. // Find a power of 2 >= toSize
      3. int capacity = roundUpToPowerOf2(toSize);
      5. threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
      6. table = new Entry[capacity];
      7. initHashSeedAsNeeded(capacity);
      8. }

    • roundUpToPowerOf2(toSize); 1. 先找到比传入的toSize大的最小的2的幂次方，关于roundUpToPowerOf2(toSize)的分析，详见附录一

    • threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); 2. 设置它的阈值
    • table = new Entry[capacity]; 3. 初始化table属性，大小为第一步中的大小

  • 初始化完成数组之后，首先判断传入的key是否为null值，如果是，执行putForNullKey(value)

    1. if (key == null)
    2.   return putForNullKey(value);

  • 否则，key不为null，进行如下操作

    • int hash = hash(key); 对key进行hash运算，计算出这个key对应的hash值

    • indexFor(hash, table.length); 通过 算出来的hash值，和初始化数组的长度，进行与运算，算出这个hash值对应于数组的下标，详解见附录二

      1. static int indexFor(int h, int length) {
      2. // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
      3. return h & (length-1);
      4. }

    • 根据数组的下标，找到对应的链表头节点，对链表进行遍历，当hash值相同，且key相同时，对这个链表节点的value进行替换，将原先的值返回回去。

      1. for (Entry<K,V> e = table[i]; e != null; e = e.next) {
      2. Object k;
      3. if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
      4.    V oldValue = e.value;
      5.    e.value = value;
      6.    e.recordAccess(this);
      7.    return oldValue;
      8. }
      9. }

    • 否则，key不相同，说明是不同的key，算出来的index相同，即发生了hash冲突，则调用addEntry(hash, key, value, i); 将新的节点添加到链表中。

      1. void addEntry(int hash, K key, V value, int bucketIndex) {
      2. if ((size >= threshold) && (null != table[bucketIndex])) {
      3.    resize(2 * table.length);
      4.    hash = (null != key) ? hash(key) : 0;
      5.    bucketIndex = indexFor(hash, table.length);
      6. }
      7. createEntry(hash, key, value, bucketIndex);
      8. }

    • 在添加时，首先判断当前的size是否大于了扩容的阈值，即在初始化table属性时，指定的阈值(capacity loadFactor),如果大雨了这个阈值，并且是发生了hash冲突(null != table[bucketIndex] 则表示之前有值，冲突了)，就进行resize 扩容。 *jdk1.7 中HashMap在多线程环境下扩容会产生死锁的问题，详见附录三

    • 否则，没达到扩容的阈值，直接进行createEntry(hash, key, value, bucketIndex); 将新Entry添加到链表中(采用头插法)
      1. void createEntry(int hash, K key, V value, int bucketIndex) {
      2. Entry<K,V> e = table[bucketIndex];
      3. table[bucketIndex] = new Entry<>(hash, key, value, e);
      4. size++;
      5. }

附录：

附录一：关于 roundUpToPowerOf2 的分析

  1. private static int roundUpToPowerOf2(int number) {
  2.     // assert number >= 0 : "number must be non-negative";
  3.     return number >= MAXIMUM_CAPACITY
  4.         ? MAXIMUM_CAPACITY
  5.         : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
  6. }

一般来讲，肯定容量不会超过MAXIMUM_CAPACITY (1<<30)，所以，一般的逻辑，都是进去到Integer.highestOneBit((number -1) << 1)这个函数中

举个例子，例如，传入的容量是 20

  1. 20 转化为2进制 == 0001 0100                       
  2. 20 -1 << 1 ===  0010 0110

highestOneBit 源码

  1. public static int highestOneBit(int i) {
  2.     i |= (i >>  1);
  3.     i |= (i >>  2);
  4.     i |= (i >>  4);
  5.     i |= (i >>  8);
  6.     i |= (i >> 16);
  7.     return i - (i >>> 1);
  8. }

其中用到了几个运算符

  1. | 或运算，有0则0
  2. >> 右移，把二进制全部往右一位，对比于10进制，相当于 除以2
  3. >>> 无符号右移

我们将上面的例子 0010 0110 带入看看（实际上，一个int是4位，即32个字节，有32个0/1）

  1. 0000 0000 0000 0000 0000 0000 0010 0110  # 源数据
  2. # i |= (i >> 1);
  3. 0000 0000 0000 0000 0000 0000 0001 0011  #i >>1;
  4. # i |= ;
  5. 0000 0000 0000 0000 0000 0000 0010 0110
  6. |
  7. 0000 0000 0000 0000 0000 0000 0001 0011
  8. # 有一则一 结果为
  9. 0000 0000 0000 0000 0000 0000 0011 0111
  10. # i |= (i >>  2);
  11. 0000 0000 0000 0000 0000 0000 0000 1101
  12. # i |= ;
  13. 0000 0000 0000 0000 0000 0000 0011 0111
  14. |
  15. 0000 0000 0000 0000 0000 0000 0000 1101
  16. # 有一则一 结果为
  17. 0000 0000 0000 0000 0000 0000 0011 1111 # 63
  18. # i |= (i >>  4);
  19. 0000 0000 0000 0000 0000 0000 0000 0011
  20. # i |= ;
  21. 0000 0000 0000 0000 0000 0000 0011 1111
  22. |
  23. 0000 0000 0000 0000 0000 0000 0000 0011
  24. # 有一则一 结果为
  25. 0000 0000 0000 0000 0000 0000 0011 1111 # 63
  26. # 后续 移 8位，16位，因为前面都是0，或运算之后，还是和原来的值相等，所以，最后的i = 63
  27. # 63 - (63 >>> 1)
  28. return i - (i >>> 1);
  29. # 对于正数来说， >>> 和 >> 没有差别，相当于 / 2
  30. # 所以最后的return 值为 63 - 31 = 32， 就找到了大于传入的value的最小2次幂

这里的思想就是，通过 不断的右移，将32位的int数低位全部改成1，再通过最后的减法，达到效果


附录二：关于 indexFor()__ 计算下标的分析

  1. static int indexFor(int h, int length) {
  2.     // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
  3.     return h & (length-1);
  4. }

将传入的HashCode 与 table的长度进行 &运算

  1. & 运算的逻辑为，有0则0

下面通过一个案例来说明

  1. h:  0010 1111
  2. length - 1 = 15: 0000 1111
  3.       h & (length - 1)
  4.      0010 1111
  5.      &
  6.      0000 1111
  7.      = 
  8.      0000 1111

因为length 是 2的幂次方，所以，低位都是1，高位都是0，在进行 & 运算的时候，产生的范围，肯定就是处于 (0， length-1) 这个范围，而不会出现在其他范围中
而如果length 没有按照附录一说的，修改为2的幂次方，例如，length = 17，根据&运算的规则，只有都为1才为1
所以，这种情况下，出现的index 只有 0000 0000， 0001 0000，这两种情况，导致的hash冲突增大。

  1. h:  0010 1111
  2. length - 1 = 16: 0001 0000
  3.       h & (length - 1)
  4.      0010 1111
  5.      &
  6.      0001 0000
  7.      = 
  8.      0000 0000

而&运算相比于 % 运算，在二进制运算中，效率更高，所以在计算下标时，采用&运算来计算下标

附录三：JDK1.7 中HashMap 多线程环境下扩容会产生死锁的问题分析

在正文中，在addEntry()方法中，会首先判断是否需要扩容
会调用resize进行扩容

  1. void resize(int newCapacity) {
  2.     Entry[] oldTable = table;
  3.     int oldCapacity = oldTable.length;
  4.     if (oldCapacity == MAXIMUM_CAPACITY) {
  5.         threshold = Integer.MAX_VALUE;
  6.         return;
  7.     }
  9.     Entry[] newTable = new Entry[newCapacity];
  10.     transfer(newTable, initHashSeedAsNeeded(newCapacity));
  11.     table = newTable;
  12.     threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
  13. }

主要产生死锁的原因在于transfer 函数中

  1. void transfer(Entry[] newTable, boolean rehash) {
  2.     int newCapacity = newTable.length;
  3.     for (Entry<K,V> e : table) {
  4.         while(null != e) {
  5.             Entry<K,V> next = e.next;
  6.             if (rehash) {
  7.                 e.hash = null == e.key ? 0 : hash(e.key);
  8.             }
  9.             int i = indexFor(e.hash, newCapacity);
  10.             e.next = newTable[i];
  11.             newTable[i] = e;
  12.             e = next;
  13.         }
  14.     }
  15. }

先不看多线程的情况，首先考虑单线程扩容

假设一个数组当中的一个的链表长度为3，value依次为1，2，3，此时发生了扩容，需要调用transfer进行转移
逻辑为，循环链表中的所有元素，重新计算所属的下标，这边假设，三个元素重新计算之后，所属的下标还都是一样的

  1. 第一次循环
    1. e 指向value = 1的节点
    2. e.next = newTable[i] 将此元素的next指向新数组，第一次为null，所以1节点的next = null
    3. newTable[i] = e 将旧元素转移到newTable[i]上
    4. e = next 此时 e 指向 value = 2 的节点
  2. 第二次循环
    1. e 指向 value = 2的节点
    2. e.next = newTable[i] 将此元素的next指向新数组，此时newTable[i] = 1 所以 2节点的next = 1
    3. newTable[i] = e 将2所在的节点当作头节点，此时newTable[i] 的元素有两个，结构为 2 -> 1
    4. e = next 此时 e 指向 value = 3 的节点
  3. 第三次循环
    1. e 指向 value = 3的节点
    2. e.next = newTable[i] 将此元素的next指向新数组，此时newTable[i] = 2 所以 3节点的next = 2
    3. newTable[i] = e 将3所在的节点当作头节点，此时newTable[i] 的元素有三个，结构为 3 -> 2 -> 1
    4. e = next 此时 e指向的 null节点
  4. e = null，循环结束

通过上述的单线程扩容，可以发现，扩容完成之后，链表的节点倒了过来，原本为 1 -> 2 -> 3, 此时却为 3 -> 2 -> 1

再看多线程环境下的扩容
假设此时的元素还有 1，2，3三个元素。
有两个线程，thread1，thread2，两个线程同时执行了put操作，并且同时满足resize的条件，在各自的线程空间中，开辟了newTable 的空间，准备进行transfer 操作。
此时，线程2 由于CPU的调度问题，执行完transfer的第五行，即赋值完next变量之后，被挂起了，此时，线程2 的 e 指向的是 1 节点，next指向的是2节点
线程1 被CPU完美调度，已经执行完了transfer的所有操作，此时 线程1 的结构按照单线程情况，为 3 -> 2 -> 1
此时线程2 活了，开始执行transfer()， 按照挂起时的变量，此时，线程2 的 e 指向的是 1 节点，next指向的是2节点。开始扩容
1. 第一次循环
1.1. e 指向value = 1的节点
1.2. next = e.next (在线程二被挂起之前，就已经赋值，指向的是 value = 2的节点)
1.3. e.next = newTable[i] 将此元素的next指向新数组，第一次为null，所以1节点的next = null
1.4. newTable[i] = e 将旧元素转移到newTable[i]上
1.5. e = next 此时 e 指向 value = 2 的节点
2.第二次循环
2.1. e 指向value = 2 的节点
2.2 next = e.next 指向 value = 1的节点(因为线程1 扩容完成之后，结构为 3 -> 2 -> 1)
2.3. e.next = newTable[i] 将此元素的next指向新数组，此时newTable[i] = 1 所以 2节点的next = 1 (原本就是如此，等于啥都没干)
2.4. newTable[i] = e 将2所在的节点当作头节点，此时newTable[i] 的元素有两个，结构为 2 -> 1
2.5. e = next，因为 next 此时指向的是value = 1 的节点，所有此时 e也指向 value = 1的节点
3.第三次循环
3.1 e指向 value = 1 的节点
3.2 next = e.next 指向null( 在第一次循环的时候 e.next = newTable[i]，因为第一次循环，newTable[i] = null，所以 e.next = null)
3.3 e.next = newTable[i] 将1 节点的next指向newTable[i]，而此时的newTable[i] 是 2 所在的节点，在这步，就已经造成了一个循环链表(2 -> 1 -> 2)
3.4 e = next，此时 e 指向 value = 2的节点

因为在3.3中已经造成了循环列表，所以此时的while循环，就已经造成了一个死循环，永远无法结束，这就是1.7中HashMap多线程扩容时，会产生循环链表的解析，且你可以发现， value = 3的节点，貌似就被抛弃了，永远也找不到了。