手撕 JDK1.8 HashMap源码（下）
手撕 JDK1.8 HashMap源码（下）
手撕源码
1. 核心常量与属性
常量
// table初始容量大小 默认值是16 且容量一定是2的次数static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;// table最大长度 2的30次方static final int MAXIMUM_CAPACITY = 1 << 30;// 负载因子大小 默认值是0.75 当哈希表使用了75%就会扩容static final float DEFAULT_LOAD_FACTOR = 0.75f;// 树化条件1 树化阈值 链表长度达到8static final int TREEIFY_THRESHOLD = 8;// 树化条件2 table的长度达到64 满足该条件且满足树化条件1 链表才会树化static final int MIN_TREEIFY_CAPACITY = 64;// 树降级为链表的阈值static final int UNTREEIFY_THRESHOLD = 6;Node类
// put到Map里面的数据都会被封装为一个Node存放到散列表当中static class Node<K,V> implements Map.Entry<K,V> { final int hash; // K.hash()经过一次扰动 final K key; V value; Node<K,V> next; // hash碰撞 链表的next指针 Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } // equals() public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }属性
// 哈希表table 由Node数组构建 只有第一次put操作时才会初始化table 默认长度是16transient Node<K,V>[] table;// 每一个Node构成的一个Set集合transient Set<Map.Entry<K,V>> entrySet;// 当前哈希表元素个数transient int size;// 当前哈希表结构修改次数 只有增删元素才会改变结构 替换元素不会使modCount变化transient int modCount;// 扩容阈值 当哈希表中的元素个数超过(数组长度 * 负载因子)时 就会扩容int threshold;// 负载因子 默认值是0.75final float loadFactor;2. 构造方法
双参
// 传入一个初始化大小和负载因子public HashMap(int initialCapacity, float loadFactor) { // 这3个if就是对参数进行校验 if (initialCapacity < 0) // 如果为负数则抛出异常 throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); // 如果大于最大值 则还原为最大值 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // 如果<=0或者非数 则抛出异常 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; // 赋值 // 传进来的initialCapacity可能是5,7这些值 需要利用tableSizeFor()确保大小是合法的 往下看该方法解析 this.threshold = tableSizeFor(initialCapacity); /* ↓ 作用：通过进制计算 返回一个大于等于当前值cap的一个数字 并且这个数字一定是2的次方。详见下方对于cap为10的计算 static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } cap = 10; n = 10 - 1 => 9 n >>> x 表示n在2进制中右移x位 00001001 | 00000100 => 00001101 00001101 | 00000011 => 00001111 00001111 | 00000000 => 00001111 00001111 | 00000000 => 00001111 00001111 | 00000000 => 00001111 00001111(2) => 15(10) return 15 + 1 => 16 */}单参
// 传入初始化大小public HashMap(int initialCapacity) { // 这里的this其实是套娃了上面的双参构造方法 this(initialCapacity, DEFAULT_LOAD_FACTOR);}无参
// 最常用的构造方法 无参 将负载因子初始化为默认的0.75public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}Map为参数
// 将一个Map中数据复制到新的Map中public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false);}3. put() => putVal()
put()
public V put(K key, V value) { // 通过hash()计算key的哈希值 再把hash,key,value传给putval()方法 return putVal(hash(key), key, value, false, true); /*↓ 这个hash()就是我们上面提到的扰动函数 作用：让key的hash值的高16位也参与路由运算。 static final int hash(Object key) { int h; // 当key为null时 hash值为0 放到table下标为0的位置 不为null则对key的hashCode进行^异或运算 详见下方 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}^ 异或：相同返回0，不同返回1 h = 0b 0010 0101 1010 1100 0011 1111 0010 1110 0b 0010 0101 1010 1100 0011 1111 0010 1110 ^ 0b 0000 0000 0000 0000 0010 0101 1010 1100 右移16位 => 0010 0101 1010 1100 0001 1010 1000 0010 一般我们的length会比较小 但是hashcode范围是很大的 这样的话key的hashCode的高位就没有参数到运算中，容易造成哈希冲突 如果要让高16位也参与进路由寻址 需要进行一些运算，在这里也就是^异或运算 让高16位的特征也能参与到低16位中 让高16位也参与运算，可以使哈希值更加散列，可以减小哈希冲突。*/}putvalue()
我们可以根据图片来理解代码：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // tab 引用当前的hashMap的散列表 // p 表示散列表当前位置的元素 // n 表示散列表数组的长度 // i 表示路由寻址得到的结果（下标） Node<K,V>[] tab; Node<K,V> p; int n, i; // 成员属性table赋值给局部变量tab判断是否为null 或者是将tab的长度赋值给n判断是否为0 表示当前hashMap中还没有创建table if ((tab = table) == null || (n = tab.length) == 0) // 延迟初始化：第一次调用putval()方法 才会调用resize()扩容方法 创建散列表 // 有时候我们把hashMap new出来之后 并不往里面放数据 如果我new的时候就把最占内存的散列表创建出来 那就会浪费内存了 // 调用resize()扩容算法 创建散列表 再把新扩容的长度赋值给n n = (tab = resize()).length; // 计算hash值的下标 (n - 1) & hash => 路由算法 // &运算 对二进制进行运算（会计算的快一些）其实就是取余%操作 hash % (n - 1) 得到下标赋值给i if ((p = tab[i = (n - 1) & hash]) == null) // 情况1.如果当前寻址找到的桶位为null 则new一个新链表结点 k,v=>node 直接扔到下标为i的散列表tab tab[i] = newNode(hash, key, value, null); else { // 如果值已经存在 // e：不为null的话，则找到了一个与当前要插入的key-value一致的key的元素node // k：临时的一个key Node<K,V> e; K k; // 情况2.表示桶位中的元素 与你当前插入的元素key完全一致，表示后续需要进行覆盖操作 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 将p赋值给e // 情况3.此时已经树化 else if (p instanceof TreeNode) // 按照红黑树的结构去存 如果存储时发生了覆盖 则赋值给e e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 情况4.此时还是链表结构 而且链表的头元素与我们要插入的key不一致 else { // 遍历链表里的所有数据 for (int binCount = 0; ; ++binCount) { // 当迭代到null时 说明已在链表的末尾 且在该链表也没有找到一个与你插入的key一致的node元素 if ((e = p.next) == null) { // 将该结点添加到p.next位置 也就是链表的末尾 p.next = newNode(hash, key, value, null); // 此时需要进行判断 未插入p时的结点数是否已经达到了8个 // 如果已经达到了8个 那么插入p.next时链表长度就变成了9 > 8 就需要对链表进行树化操作 // 循环从0开始 binCount >= TREEIFY_THRESHOLD - 1 => 7 此时链表已经有8个元素 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); // 树化操作 后期会更新红黑树的文章 break; } // 此时e.hash也就是p.next.hash与当前插入的hash相同 且key一致 说明找到了一个相同元素 则break出外面操作 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; // 一步一步往后迭代 } } // 条件成立说明 找到了一个与你插入元素key完全一致的数据 需要执行覆盖操作 e赋上了值就代表要覆盖 e不赋值就代表存上了 if (e != null) { // existing mapping for key:密钥的现有映射 V oldValue = e.value; // 先取出旧值 // !onlyIfAbsent = true if (!onlyIfAbsent || oldValue == null) e.value = value; // 然后把现在要存的值赋给e.value 新值替换旧值 afterNodeAccess(e); // 访问后回调 return oldValue; // 把旧的值返回 不执行后面的操作 } } ++modCount; // 表示散列表被修改的次数 插入新元素才会++ 替换在上面直接return了 不++ // ++size后 大于扩容阈值 触发扩容算法 if (++size > threshold) resize(); // 扩容算法 afterNodeInsertion(evict); // 插入后回调 return null;}put()方法总结
先通过hash()扰动计算出哈希值，然后调用putVal()方法：
- 延迟初始化：先判断哈希表是否创建过，如果未创建则创建
table - 通过路由算法
(n - 1) & hash寻址得到当前元素的下标 - 插入元素
- ① 当前桶位为空，直接放
- ② 当前位置有元素，且哈希值相同，key一致，则进行赋值，后续进行
value的覆盖操作 - ③ 当前位置已被树化，如果存储时发生了覆盖，则赋值，否则插入到树中
- ④ 当前位置是链表结构，遍历整个链表，如果找到哈希值相同，且key一致，后续进行
value的覆盖操作，否则插入到链表尾部，并判断当前链表长度是否达到了树化标准（链表长度达到8 并且数组长度达到64(这个判断条件在树化的treeifyBin()方法中)）
- 覆盖
value操作 - 插入元素后 更新变量，
++modCount，判断++size是否超过当前大小，如果超过则resize()扩容。
4. resize() 扩容(核心)
// 为什么需要扩容？为了解决哈希冲突导致的链化影响查询效率问题，扩容会缓解该问题。final Node<K,V>[] resize() { // oldTab：引用扩容前的哈希表 Node<K,V>[] oldTab = table; // oldCap：表示扩容之前table数组的长度 如果是null 则长度为0 int oldCap = (oldTab == null) ? 0 : oldTab.length; // oldThr：扩容之前的扩容阈值(数组长度)，触发本次的扩容阈值 int oldThr = threshold; // newCap：扩容之后达到的大小 // newThr：扩容之后，下次再次触发扩容的条件 int newCap, newThr = 0; // 条件成立 说明hashMap中的散列表已经初始化过了，是一次正常扩容 if (oldCap > 0) { // 扩容之前的table数组大小已经达到最大阈值后，则不扩容，且设置扩容条件为 int 最大值 if (oldCap >= MAXIMUM_CAPACITY) { // 生成这个int最大值就很难达到这个扩容阈值了 但这种情况很少见 threshold = Integer.MAX_VALUE; return oldTab; } // oldCap左移一位 实现数值翻倍 并赋值给newCap，newCap小于数组最大值限制 且 扩容之前的阈值 >= 16 // 这种情况下，则下一次扩容的阈值 等于当前阈值翻倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold:双倍阈值 } // oldCap == 0 说明hashMap中的散列表是null // 1.new HashMap(initCap, loadFactor); // 2.new HashMap(initCap); // 3.new HashMap(map); 并且这个map有数据 // 在这3中构造方法情况下，oldThr有值 else if (oldThr > 0) // initial capacity was placed in threshold:初始容量设置为阈值 // 第一次构建 直接赋值给newCap newCap = oldThr; // oldCap == 0，oldThr == 0 // new HashMap(); // 只有调用的是无参构造方法时 else { // zero initial threshold signifies using defaults:零初始阈值表示使用默认值 newCap = DEFAULT_INITIAL_CAPACITY; // 16 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 0.75 * 16 => 12 } // newThr为零时，通过newCap和loadFactor计算出一个newThr if (newThr == 0) { float ft = (float)newCap * loadFactor; // 判断newCap和ft是否合法 如果合法则将计算出的ft转为int 不合法则赋予int最大值 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; // 更新下一次的扩容阈值 @SuppressWarnings({"rawtypes","unchecked"}) // 注解作用：抑制编译器产生的多类型警告信息 // 根据newCap创建出一个更长的数组 也有可能是第一次创建数组 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; // 将新创建的node赋值给table // 说明，hashMap本次扩容之前 table不为null // 扩容操作 if (oldTab != null) { // 将每个旧哈希表中的数据都移动到新的散列表中 // 遍历旧哈希表中的每一个桶，重新计算桶里元素在新哈希表中的位置 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; // 当前node节点 // 说明当前桶位中有数据 但是数据具体是单个数据/链表/红黑树 暂时还未知 if ((e = oldTab[j]) != null) { // 原来的数据赋值为null 方便JVM GC时回收内存 oldTab[j] = null; // 情况1.说明该桶中未发生过哈希碰撞 只有一个元素 if (e.next == null) // 根据新length通过路由寻址算法得到新下标 插入到新位置 newTab[e.hash & (newCap - 1)] = e; // 情况2.当前节点已树化 else if (e instanceof TreeNode) // 红黑树处理 暂且跳过 后期会更新红黑树的文章 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 情况3.当前节点为链表 下方有图 else { // preserve order:维持秩序 // 低位链表：存放在扩容之后的数组的下标位置 与当前数组的下标一致 Node<K,V> loHead = null, loTail = null; // 高位链表：存放在扩容之后的数组的下标位置为 当前数组下标位置 + 扩容之前数组的长度 Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; /* 假设当前oldCap 也就是当前哈希表长度为16 => 0b 10000 且当前结点存放在下标为15的位置 则该节点哈希值的后4位一定是1111 第5位可能是0也可能是1 e.hash -> ... 0 1111 e.hash -> ... 1 1111 e.hash & oldCap == 0 说明该节点的下标为15 即放在原下标位置(低位链表) e.hash & oldCap == 16 => != 0 说明该节点的下标为31 即放在新下标位置(高位链表) */ // hash值 & 原长度 == 0 说明元素应该存至低位链表 if ((e.hash & oldCap) == 0) {if (loTail == null) loHead = e;else loTail.next = e;loTail = e; } // 存至高位链表 else {if (hiTail == null) hiHead = e;else hiTail.next = e;hiTail = e; } } while ((e = next) != null); // 低位链表有数据 if (loTail != null) { loTail.next = null; // 将末尾置为空 newTab[j] = loHead; // 放到原位置 } // 高位链表有数据 if (hiTail != null) { hiTail.next = null; // 将末尾置为空 newTab[j + oldCap] = hiHead; // 放到 原位置 + 扩容之前的table长度 } } } } return newTab; // 返回新散列表}扩容—链表处理
低位链表：存放在扩容之后的数组的下标位置 与当前数组的下标一致（蓝色）
高位链表：存放在扩容之后的数组的下标位置为 当前数组下标位置 + 扩容之前数组的长度（绿色）
resize()扩容方法总结
- 获取原哈希表的数据 并进行验证和计算后 得到新值
newCap（哈希表的新长度），newThr（哈希表的新扩容阈值） - 根据
newCap创建出新的哈希表 - 扩容操作
- ① 该桶中只有一个元素，直接通过路由寻址算法得到新下标 插入到新位置
- ② 当前节点已树化，由树化操作寻址插入
- ③ 当前节点为链表结构，分离链表(低位、高位)，根据位运算判断当前节点应存至低位/高位
- 存放操作
5. get() => getNode()
get()
public V get(Object key) { Node<K,V> e; // put经过hash()，取时肯定也要hash() 如果key为空则返回空 否则返回value return (e = getNode(hash(key), key)) == null ? null : e.value;} // ↓getNode()
final Node<K,V> getNode(int hash, Object key) { // tab：引用当前hashMap的散列表 // first：桶位中的头元素 // e：临时node元素 // n：table数组长度 // k：key Node<K,V>[] tab; Node<K,V> first, e; int n; K k; // 如果哈希表的table存在 且桶中的第一个元素存在 但并不知道该元素是单个/链表/红黑树 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 情况1.定位的桶位首元素 即为我们要get的数据 直接把该元素返回 if (first.hash == hash && // always check first node:始终检查第一个节点 ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 当前桶位不是单个元素 可能是链表/红黑树 if ((e = first.next) != null) { // 情况2.桶位是红黑树结构 在树中寻找 if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); // 情况3.桶位是链表结构 遍历链表寻找 do { // 找到 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; // 没有数据直接返回空}6. remove() => removeNode()
remove()
单参
// 根据key删除public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;}双参
// 根据key和value删除@Overridepublic boolean remove(Object key, Object value) { return removeNode(hash(key), key, value, true, true) != null;}removeNode()
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {// matchValue参数 如果为true则需要对value也进行比较 参照上面的两个构造方法 只传key时 该参数为false // tab：引用当前hashMap中的散列表 // p：当前node元素 // n：表示散列表数组长度 // index：表示寻址结果 Node<K,V>[] tab; Node<K,V> p; int n, index; // 判断table中是否有元素 如果有则计算出当前元素位置并赋值给p if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { // node：查找到的结果 // e：当前Node的下一个元素 Node<K,V> node = null, e; K k; V v; // 进行查找操作 并删除 // 情况1.当前桶位中的元素 即为你要删除的元素 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; // p.next不为空 当前桶位可能是链表/红黑树 else if ((e = p.next) != null) { // 情况2.当前桶位已是红黑树 if (p instanceof TreeNode) // 红黑树的查找操作 node = ((TreeNode<K,V>)p).getTreeNode(hash, key); // 情况3.当前桶位为链表 else { // 遍历整个链表 查找元素 do { // 找到 赋值给node if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } // 对比查找到的key和value是否与传进来的匹配 // 删除操作 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { // 情况1.如果node是红黑树结构 则用树的操作删除 if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); // 情况2.当前桶位即为要删除的元素 else if (node == p) // 直接将当前结点指向next 即删除 tab[index] = node.next; // 情况3.将当前元素p的下一个元素 设置成 要删除元素的 下一个元素 else p.next = node.next; ++modCount; // 更新修改次数 --size; // 更新元素个数 afterNodeRemoval(node); return node; // 返回结果 } } return null; // 如果查询不到 则返回null}7. replace()
三参
@Overridepublic boolean replace(K key, V oldValue, V newValue) { Node<K,V> e; V v; // 根据key找到node结点 判断找到的value跟传进来的oldValue是否一致 如果一致则用新的newValue替换value if ((e = getNode(hash(key), key)) != null && ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) { e.value = newValue; afterNodeAccess(e); return true; } return false;}双参
@Overridepublic V replace(K key, V value) { Node<K,V> e; // 根据key找到node结点 做替换 把旧值返回 if ((e = getNode(hash(key), key)) != null) { V oldValue = e.value; e.value = value; afterNodeAccess(e); return oldValue; } return null;}据key找到node结点 判断找到的value跟传进来的oldValue是否一致 如果一致则用新的newValue替换value if ((e = getNode(hash(key), key)) != null && ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) { e.value = newValue; afterNodeAccess(e); return true; } return false;}文章参考：b站小刘讲源码视频