基于 JDK 1.8

属性字段

  1. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //  初始默认容量大小，如果指定容量，容量必须是 2 的倍数
  3. static final int MAXIMUM_CAPACITY = 1 << 30; // 最大的容量大小 1*2^30=1073741824 ，如果指定容量，容量必须是 2 的倍数
  5. static final float DEFAULT_LOAD_FACTOR = 0.75f;  // 默认负载因子
  7. static final int TREEIFY_THRESHOLD = 8;  // 超过 8 就变为 红黑树
  9. static final int UNTREEIFY_THRESHOLD = 6;  // 小于 6 变为链表
  11. transient Node<K,V>[] table; // 存放元素的哈希桶数组
  13. transient int size; // 当前 Map 中 键值对数量
  15. final float loadFactor; // 负载因子
  17. int threshold; // 当前 Map 能容纳的最大键值对数量，threshold = length * Load factor 
  19. transient int modCount; // 结构性修改的次数，用于 fail-fast 机制

构造方法

  • 默认负载因子 0.75
  • 初始传参不要超过 1073741824(10 亿级别)，超过这个数会被这个数代替
  • tableSizeFor(int n) 将返回第一个大于 n 的为 2 的次幂的数。
  • threshold = initialCapacity*loadFactor，threshold 表示当前容量的Map能包含的键值对数量。
  1. static final float DEFAULT_LOAD_FACTOR = 0.75f;
  2. static final int MAXIMUM_CAPACITY = 1 << 30;
  4. public HashMap() {
  5.     this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
  6. }
  8. public HashMap(int initialCapacity) {
  9.     this(initialCapacity, DEFAULT_LOAD_FACTOR);
  10. }
  12. public HashMap(int initialCapacity, float loadFactor) {
  13.     if (initialCapacity < 0)
  14.         throw new IllegalArgumentException("Illegal initial capacity: " +
  15.                                            initialCapacity);
  16.     if (initialCapacity > MAXIMUM_CAPACITY)
  17.         initialCapacity = MAXIMUM_CAPACITY;
  18.     if (loadFactor <= 0 || Float.isNaN(loadFactor))
  19.         throw new IllegalArgumentException("Illegal load factor: " +
  20.                                            loadFactor);
  21.     this.loadFactor = loadFactor;
  22.     this.threshold = tableSizeFor(initialCapacity);
  23. }
  25. // 第一个大于 n 的为 2 的次幂的数
  26. static final int tableSizeFor(int cap) {
  27.     int n = cap - 1;
  28.     n |= n >>> 1;
  29.     n |= n >>> 2;
  30.     n |= n >>> 4;
  31.     n |= n >>> 8;
  32.     n |= n >>> 16;
  33.     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  34. }

key 对应到哈希桶的过程

  1. static final int hash(Object key) {
  2.     int h;
  3.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  4. }
  6. index = hash(key) & (length - 1)

  1. 若 key == null，放到数组第一位

  2. key != null，调用 Object.hashCode() 方法将 key 进行 hash 得到 h

  3. 将 h 与 h 右移 16 位后的数值进行异或得到一个 hash 值

  4. 将第 3 步得到 hash 值与数组长度减一进行与运算，得到 key 在哈希桶的索引位置。

第 4 步非常巧妙，它通过 h&(table.length -1) 来得到该对象的保存位，而 HashMap 底层数组的长度总是 2的 n 次方，这是 HashMap 在速度上的优化。

当 length 总是 2 的 n 次方时，h& (length-1) 运算等价于对 length 取模，也就是 h%length ，但是 & 比 % 具有更高的效率。
HashMap 源码学习基于 JDK1.8 - 图1

插入put 方法

  • (n - 1) & hash 相当于对 length 取余
  • (h = key.hashCode()) ^ (h >>> 16) 高 16 位和低 16 位进行异或，是因为当桶数组比较小时候，hashcode 值比较大，避免取模只有低位生效，高位不生效的问题。

流程：

  1. key 进行 hash，hash 办法为：将 key 的 hashcode 值与 key 的高 16 位进行异或运行，这种运算是时间和空间的折中办法。key 若为 null，将元素放到第一位。
  2. 判断 HashMap 是否初始化，若没有，调用 resize() 方法进行初始化
  3. 将 hash 值与数组长度-1进行与，得到 tab(i) 位置
  4. 若 tab(i) 没有元素，直接插入。tab(i)有元素，如果 key 相同，直接替换；若为红黑树节点，进行红黑树插入逻辑；若为链表节点，循环并插入到末尾，若链表长度 >= 7 将转为红黑树（当数组长度小于 64 直接扩容）。
  5. 将对应节点的 value 更改为设定的值
  6. 是否扩容判断。
  2. public V put(K key, V value) {
  3.     return putVal(hash(key), key, value, false, true);
  4. }
  7. static final int hash(Object key) {
  8.     int h;
  9.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  10. }
  12. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  13.                boolean evict) {
  14.     Node<K,V>[] tab; Node<K,V> p; int n, i;
  15.     // 如果为空，进行初始化
  16.     if ((tab = table) == null || (n = tab.length) == 0)
  17.         n = (tab = resize()).length;
  18.     //  如果当前位置没有元素，直接保存   
  19.     if ((p = tab[i = (n - 1) & hash]) == null)
  20.         tab[i] = newNode(hash, key, value, null);
  21.     else {
  22.         // 发生碰撞
  23.         Node<K,V> e; K k;
  24.         // 如果hash值相同并且相等（引用相同或者equals返回true），直接替换
  25.         if (p.hash == hash &&
  26.             ((k = p.key) == key || (key != null && key.equals(k))))
  27.             e = p;
  28.         else if (p instanceof TreeNode)
  29.             // 是树节点，调用红黑树插入办法
  30.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  31.         else {
  32.             // 当前hash的位置是链表节点
  33.             for (int binCount = 0; ; ++binCount) {
  34.                 // 遍历到空节点
  35.                 if ((e = p.next) == null) {
  36.                     // 尾插法插入节点
  37.                     p.next = newNode(hash, key, value, null);
  38.                     // 如果当前节点长度 >= 7，转换为树
  39.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  40.                         // 
  41.                         treeifyBin(tab, hash);
  42.                     break;
  43.                 }
  44.                 // 当前节点是相同的，直接替换
  45.                 if (e.hash == hash &&
  46.                     ((k = e.key) == key || (key != null && key.equals(k))))
  47.                     break;
  48.                 p = e;
  49.             }
  50.         }
  51.         // 如果插入成功，更新指定位置的值
  52.         if (e != null) { // existing mapping for key
  53.             V oldValue = e.value;
  54.             if (!onlyIfAbsent || oldValue == null)
  55.                 e.value = value;
  56.             afterNodeAccess(e);
  57.             return oldValue;
  58.         }
  59.     }
  60.     ++modCount;
  61.     // 进行扩容  
  62.     if (++size > threshold)
  63.         resize();
  64.     afterNodeInsertion(evict);
  65.     return null;
  66. }
  68. final void treeifyBin(Node<K,V>[] tab, int hash) {
  69.     int n, index; Node<K,V> e;
  70.     // 数组长度小于 64 的时候直接进行扩容，而不是树化
  71.     if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
  72.         resize();
  73.     else if ((e = tab[index = (n - 1) & hash]) != null) {
  74.         TreeNode<K,V> hd = null, tl = null;
  75.         do {
  76.             TreeNode<K,V> p = replacementTreeNode(e, null);
  77.             if (tl == null)
  78.                 hd = p;
  79.             else {
  80.                 p.prev = tl;
  81.                 tl.next = p;
  82.             }
  83.             tl = p;
  84.         } while ((e = e.next) != null);
  85.         if ((tab[index] = hd) != null)
  86.             hd.treeify(tab);
  87.     }
  88. }
  • JDK 8 是先插入后扩容，JDK 7 是先扩容再插入

扩容 resize

  1. final Node<K,V>[] resize() {
  2.     Node<K,V>[] oldTab = table;
  3.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
  4.     int oldThr = threshold;
  5.     int newCap, newThr = 0;
  6.     // table已经初始化，且容量 > 0
  7.     if (oldCap > 0) {
  8.         if (oldCap >= MAXIMUM_CAPACITY) {
  9.             // 如果旧的容量已近达到最大值，则不再扩容，阈值直接设置为最大值
  10.             threshold = Integer.MAX_VALUE;
  11.             return oldTab;
  12.         }
  13.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  14.                  oldCap >= DEFAULT_INITIAL_CAPACITY)
  15.                  // 扩容两倍的容量小于最大值并且旧容量大于默认的capacity，就直接扩容两倍
  16.             newThr = oldThr << 1; // double threshold
  17.     }
  18.     // 用 newCap 保存 threshold 值
  19.     else if (oldThr > 0) // initial capacity was placed in threshold
  20.         newCap = oldThr;
  21.     // 首次初始化的情况
  22.     else {               // zero initial threshold signifies using defaults
  23.         // 无参构造函数调用，默认值
  24.         newCap = DEFAULT_INITIAL_CAPACITY;
  25.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  26.     }
  27.     if (newThr == 0) {
  28.         // 若新的阈值为 0，threhold =  cap * loadFactor
  29.         float ft = (float)newCap * loadFactor;
  30.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  31.                   (int)ft : Integer.MAX_VALUE);
  32.     }
  34.     // 更新阈值，可保存的最大元素数量
  35.     threshold = newThr;
  36.     // 新建数组桶
  37.     @SuppressWarnings({"rawtypes","unchecked"})
  38.     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  39.     table = newTab;
  40.     // 数组原来有数据，重新计算hash
  41.     if (oldTab != null) {
  42.         for (int j = 0; j < oldCap; ++j) {
  43.             Node<K,V> e;
  44.             // 当前位置元素不为 null
  45.             if ((e = oldTab[j]) != null) {
  46.                 // e 保存了该节点，所以将此处元素置为 null
  47.                 oldTab[j] = null;
  48.                 // 如果下一个节点为null，不为链表或者树
  49.                 if (e.next == null)
  50.                     // 将该元素放到新位置
  51.                     newTab[e.hash & (newCap - 1)] = e;
  52.                 else if (e instanceof TreeNode)
  53.                     // 放到树节点
  54.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  55.                 else { // preserve order
  56.                     // 链表节点
  57.                     Node<K,V> loHead = null, loTail = null;
  58.                     Node<K,V> hiHead = null, hiTail = null;
  59.                     Node<K,V> next;
  60.                     do {
  61.                         next = e.next;
  62.                         if ((e.hash & oldCap) == 0) {
  63.                             if (loTail == null)
  64.                                 loHead = e;
  65.                             else
  66.                                 loTail.next = e;
  67.                             loTail = e;
  68.                         }
  69.                         else {
  70.                             if (hiTail == null)
  71.                                 hiHead = e;
  72.                             else
  73.                                 hiTail.next = e;
  74.                             hiTail = e;
  75.                         }
  76.                     } while ((e = next) != null);
  77.                     if (loTail != null) {
  78.                         loTail.next = null;
  79.                         newTab[j] = loHead;
  80.                     }
  81.                     if (hiTail != null) {
  82.                         hiTail.next = null;
  83.                         newTab[j + oldCap] = hiHead;
  84.                     }
  85.                 }
  86.             }
  87.         }
  88.     }
  89.     return newTab;
  90. }

  1. JDK 1.7 引发的循环链表问题（参考其它博文）

  2. 扩容之后，节点的位置变化特点

执行运算 ： hash & oldCap ，如果为 0 放在原位置，如果不为 0，新位置为 原位置+oldCap
HashMap 源码学习基于 JDK1.8 - 图2HashMap 源码学习基于 JDK1.8 - 图3
HashMap 源码学习基于 JDK1.8 - 图4

get

  • put 方法支持，key、value 都为 null，并且是 尾插法

  • get 方法返回 null，有两种情况：一是不包含这个键值对，二是该键值对的键 key 对应的 value 就是 null，可以通过 containsKey 方法判断 Map 是否包含该 key

  2. public V get(Object key) {
  3.     Node<K,V> e;
  4.     return (e = getNode(hash(key), key)) == null ? null : e.value;
  5. }
  7. final Node<K,V> getNode(int hash, Object key) {
  8.     Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  9.     // 如果map不为空并且当前hash值与数组与之后值不为null
  10.     if ((tab = table) != null && (n = tab.length) > 0 &&
  11.         (first = tab[(n - 1) & hash]) != null) {
  12.         // 第一个节点的 hash 值等于传进来的并且 equals 返回 true，直接返回这个节点
  13.         if (first.hash == hash && // always check first node
  14.             ((k = first.key) == key || (key != null && key.equals(k))))
  15.             return first;
  16.         // 如果是链表节点或者树节点    
  17.         if ((e = first.next) != null) {
  19.             if (first instanceof TreeNode)
  20.                 // 返回树节点中的
  21.                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  22.             do {
  23.                 // 链表里面循环 找到相等的
  24.                 if (e.hash == hash &&
  25.                     ((k = e.key) == key || (key != null && key.equals(k))))
  26.                     return e;
  27.             } while ((e = e.next) != null);
  28.         }
  29.     }
  30.     return null;
  31. }

问题

  • 为什么使用红黑树？

虽然 AVL 可以提供更快的查找结果，但是在节点变化时，为了维持高度的平衡，在节点旋转方面，AVL 更加复杂

  • JDK 1.7 用头插法、JDK 1.8 用尾插法

JDK 1.7 在多线程环境下会出现环形链表的问题，JDK 1.8 改成了尾插，但是 HashMap 依旧不能用于多线程环境。

  • 为什么 table 使用 transient 修饰？

根据 Java 中的定义，被 transient 修饰的对象不能被序列化

  1. table 没有存满，未使用的部分序列化浪费空间
  2. 不同 JVM 环境中，计算 key 的 hash 值不同，在还原过程中可能出现桶位置不一样的情况。

参考

Java8的HashMap详解（存储结构，功能实现，扩容优化，线程安全，遍历方法），是下面的总结

Java 8系列之重新认识HashMap

HashMap 源码详细分析(JDK1.8)