HashMap 的数据结构
? hashMap 初始的数据结构如下图所示 OA 现金盘平台出租 QQ2952777280[话仙源码论坛] hxforum.com[木瓜源码论坛] papayabbs.com, 内部维护一个数组, 然后数组上维护一个单链表, 有个形象的比喻就是想挂钩一样, 数组脚标一样的, 一个一个的节点往下挂.
hashMap 初始数据结构图
? 我们可以看源码来验证下, HashMap 的数据结构是不是真的是像上面所说是数组加链表的形式:
- // 此处略过其他代码, 只截取出了 hashMap 的数组结构相关的数组与链表
- public class HashMap<K,V> extends AbstractMap<K,V>
- implements Map<K,V>, Cloneable, Serializable {
- private static final long serialVersionUID = 362498820763181265L;
- /* ---------------- Fields -------------- */
- /**
- * The table, initialized on first use, and resized as
- * necessary. When allocated, length is always a power of two.
- * (We also tolerate length zero in some operations to allow
- * bootstrapping mechanics that are currently not needed.)
- */
- // 这个是 hashMap 内部维护的数组
- transient Node<K,V>[] table;
- /**
- * Basic hash bin node, used for most entries. (See below for
- * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
- */
- // 这个是数组元素的节点类, next 的属性表示下一个节点, 即数组的节点元素维护的下一个节点的元素, 那不是就是链表吗
- static class Node<K,V> implements Map.Entry<K,V> {
- final int hash; // 数组的脚标值, 下面会详细描述这个内容
- final K key; //map 的 key
- V value; //map 的 value
- Node<K,V> 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;
- }
- 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;
- }
- }
? 通过源码可知, HashMap 的数据结构正如上文所述, 是一个数组加链表的形式存储数组, 那么数组的角标是怎么计算的呢? 如果是你来设计, 你会怎么去设计这个角标的计算方式呢?
? 在没看源码之前, 我做了一个猜想, 就是数组的角标我猜想是按照下面的计算方式计算的:
既然是 HashMap, 那肯定有个 hashCode
然后通过 key 值的 hashCode 与数组的长度取模
取模之后, 数值一样的, 就往数组的节点上面往下挂
上面是我的猜想, 但是 HashMap 的数组角标的实现真的是这样吗? 我们进入下一节去探究
hash 值的计算
? 既然要看脚标值的计算, 那我们肯定要看 HashMap 的 put 方法, 因为在 put 方法里面肯定要计算出脚标的值, 然后才能把数据存放到数组里面去嘛, 所以我们直接看 put 的源码:
- /**
- * Associates the specified value with the specified key in this map.
- * If the map previously contained a mapping for the key, the old
- * value is replaced.
- *
- * @param key key with which the specified value is to be associated
- * @param value value to be associated with the specified key
- * @return the previous value associated with <tt>key</tt>, or
- * <tt>null</tt> if there was no mapping for <tt>key</tt>.
- * (A <tt>null</tt> return can also indicate that the map
- * previously associated <tt>null</tt> with <tt>key</tt>.)
- */
- // 此处是 HashMap 的 put 方法的源码, 这个 put 方法又调了另一个 putVal 的方法, 我们看一下 putVal 的方法
- public V put(K key, V value) {
- return putVal(hash(key), key, value, false, true);
- }
- /**
- * Implements Map.put and related methods
- *
- * @param hash hash for key
- * @param key the key
- * @param value the value to put
- * @param onlyIfAbsent if true, don't change existing value
- * @param evict if false, the table is in creation mode.
- * @return previous value, or null if none
- */
- final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
- boolean evict) {
- Node<K,V>[] tab; Node<K,V> p; int n, i;
- if ((tab = table) == null || (n = tab.length) == 0)
- n = (tab = resize()).length;
- if ((p = tab[i = (n - 1) & hash]) == null)
- tab[i] = newNode(hash, key, value, null);
- else {
? 这里我们关注 tab[i] = newNode(hash, key, value, null); 这句代码, 前面我们看到了 tab 就是数组, 那说明这句代码就是给节点赋值, 那么 i 就是数组的角标那这个 i 是怎么计算的呢?
? 看他上面的一句判断 (p = tab[i = (n - 1) & hash] 即这个 i 是通过 (n - 1) & hash 计算出来的, n = tab.length 这个 n 是数组的长度, 就是说数组的角标是通过数组的长度 - 1 与上这个 hash, 这个跟我们之前猜想的然后通过 hashCode 与数组的长度取模就不一致了, 那这里我们先保留着这个问题, 先看一下 hash 的计算, 从上面代码中, 可以知道, hash 值是通过调用 hash(key) 方法调用得到.
? 这里我将计算 hash 的方法, 单独抽离出来外面写, 如下:
- static final int hash(Object key) {
- int h;
- return (key == null) ? 0 : (h = key.hashCode()) ^ (h>>> 16);
- }
? key 就是 map 调用 put 方法, put 进来的 key 值, 看上面这个方法, 前面判空之后返回 0 的大家一眼就看明白了, 主要关注后面的内容,(h = key.hashCode()) ^ (h>>> 16)这句代码前半部分很明白, 就是取 key 的 hashCode 值赋给 h,(^ 这个符号表示异或,>>>表示无符号右移), 然后与 h 右移 16 位后的值进行异或操作.
? 为什么要这样计算去计算 hash 呢? 这样计算 hash 又最终与数组的脚标有什么联系呢?
? 下面我来画张图, 来理顺这一块的计算, 看下图:
hashCode 异或运算计算 hash
? 这样做可以实现 hashCode 的值, 高低位更加均匀地混到一起, 结合上面数组脚标 (n - 1) & hash 的运算, 由于 HashMap 数组的大小总是 2^n, 即 (2^n-1) 得到的值转化为二进制, 如: 00001111,00011111 (舍弃前面高位) 等, 与 hash 的值进行与运算, 这样又保证每一个脚标 i 值都能在数组的长度内. 这里可能有点难理解, 举个例子来说明一下.
? 就是 hashMap 的数组初始大小是 16, 那 length-1 的值就为 15,15 的二进制值是.... 0000 1111, 此时上面 hash 值 363766277 的二进制位 0001 0101 1010 1110 1010 0010 0000 0101, 这两个数进行与运算时, 由于 15 的前面高位都为 0, 所以进行与运算的值最终都不可能大于 15, 像这个例子, 最终的值为 0101 为 9, 这样就保证了每一个脚标 i 值都能在数组的长度内.
? 那么这里就有一个疑问了, 为什么不直接采用与数组长度取模的方式, 直接取得脚标值, 而是先去异或, 再与运算去计算脚标值?
? 主要有两个原因:
? 1. 用位运算, 效率更高
? 2. hashCode 的高低位异或运算, 让高低位更加均匀的混合到一起, 可以使得在 put 元素时, 可以减少哈希碰撞
? 减少哈希碰撞才是最主要的原因. 那什么是哈希碰撞呢?
? 我们知道 HashMap 的数组结构不是数组加链表吗? 那数组跟链表有什么特点? 我们都知道数组是查询快, 增删慢, 链表是查询慢, 增删快.
? 这也很容易理解, 链表嘛, 只记录着下一个节点的值, 又没有脚标, 如果你这个链表很长(虽然在这里最长不会超过 8, 后面会讲到), 你查找的一个元素刚好在最后一个, 那不是在定位到数组脚标以后找到链表的第一个节点, 然后往下一直遍历查找到最后一个才找到我们要的元素, 这样效率不就很慢了吗, 所以如果我们直接对 hashCode 跟数组的长度进行取模, 计算出的 hash 值可能会碰撞高, 就会使得数组单个节点的链表很长很长, 而这样子 HashMap 的查询效率就很差, 而 hashCode 的高低位异或运算, 可以让高低位更加均匀的混合到一起, 减少哈希碰撞, 从而提高 HashMap 的查询效率.
? 一句话总结, 失败的 hashCode 算法会导致 HashMap 的性能由数组下降为链表, 所以想要避免发生碰撞, 就要提高 hashCode 结果的均匀性.
数组的扩容
数组的初始化长度
? 在上一节的时候, 我们讲到了 HashMap 的长度总是 2^n 这句话, 我们怎么知道呢, 我们可以从源码中找到这一设定, 那么我们首先先看一下, HashMap 数组初始的默认大小是多少呢, 源码中有这一句代码
- /**
- * The default initial capacity - MUST be a power of two.
- */
- static final int DEFAULT_INITIAL_CAPACITY = 1 <<4; // aka 16
? 但是, 我们不能光看这个常量值就说 HashMap 内数组的默认常量值就是 16 啊, 我们要继续找到初始化的方法代码, 看他是不是初始值为 16
- /**
- * Initializes or doubles table size. If null, allocates in
- * accord with initial capacity target held in field threshold.
- * Otherwise, because we are using power-of-two expansion, the
- * elements from each bin must either stay at same index, or move
- * with a power of two offset in the new table.
- *
- * @return the table
- */
- // 上面的英文中说到, 初始化或者翻倍数组的大小
- final Node<K,V>[] resize() {
- Node<K,V>[] oldTab = table;
- int oldCap = (oldTab == null) ? 0 : oldTab.length;
- int oldThr = threshold;
- int newCap, newThr = 0;
- if (oldCap> 0) {
- if (oldCap>= MAXIMUM_CAPACITY) {
- threshold = Integer.MAX_VALUE;
- return oldTab;
- }
- else if ((newCap = oldCap <<1) < MAXIMUM_CAPACITY &&
- oldCap>= DEFAULT_INITIAL_CAPACITY)
- newThr = oldThr <<1; // double threshold
- }
- else if (oldThr> 0) // initial capacity was placed in threshold
- newCap = oldThr;
- else { // zero initial threshold signifies using defaults
- newCap = DEFAULT_INITIAL_CAPACITY; // 当 oldTab 即为 table 数组的长度, 当 oldTab 长度为 0 时, 将 DEFAULT_INITIAL_CAPACITY 赋值给 newCap,newCap 即为数组的新长度
- newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
- }
? 我们可以查询下 resize()方法的调用者, 发现 putVal()方法里调用了这个方法
putVal 方法调用 resize()
? 截图中的代码已经很清楚了, 就是当 table 数组的长度为 null 或长度为 0 时, 调用初始化 resize()方法, 然后在 resize()方法中也做了判断, 当 table 数组的长度为 0 时, 将新数组的长度赋值为 DEFAULT_INITIAL_CAPACITY,
? 所以 HashMap 中数组的初始化长度就是 DEFAULT_INITIAL_CAPACITY, 等于 1 <<4, 等于 16
数组扩容的阈值
? 上一节我们知道数组的初始长度是 16, 然而 16 的长度显然不能满足我们普通应用的开发, 所以这里就涉及到了数组的扩容. 那要什么时候扩容, 怎么扩呢?
? 我们知道, 链表的查询效率肯定比数组的查询效率低, 所以要提高 HashMap 的查询效率, 我们肯定要数据尽可能多的往数组上存数据, 而不是延长链表的长度. 那是不是存满之后再做扩容呢? 比方说数组初始化 16, 等到存满 16 的时候或者第 17 个进来的时候, 开始扩容呢?
? 我们可以先分析一下, 然后再来看源码. 当数组的元素都放满了, 然后这时候来扩容, 扩容之后, 数组元素的脚标值就得重新计算, 即 rehash , 比如原来是计算 hash 用的数组长度 16, 扩容之后数组长度变成了 32, 这时候(n - 1) & hash 计算脚标的值就不正确了, 那你数组都存满了, 那不是数组的每个元素都得重新计算脚标 i 值, 所以这种做法是不是不合理?
hashMap 初始数据结构图
? 所以这里就有一个数组扩容的阈值, 就是说, 当数组的长度达到某个值或某个条件时, 数组就开始扩容, 而这里的某个值或某个条件就是我们所说的数组扩容的阈值.
? 那么这个阈值具体是多少呢? 下面我们来探究源码, 既然要找到扩容的阈值, 那我们不外乎要从两个方法入手去找, 一个就是 put()操作的时候, 一个就是扩容 resize()的时候. 因为我已经找过了, 我就直接去 put()方法里面找了, resize()方法后面会细讲, 这里就讲 put()方法.
- // 这里 put 方法只调用了 putVal 方法, 那我们就直接看 putVal 方法
- public V put(K key, V value) {
- return putVal(hash(key), key, value, false, true);
- }
- // 我解释下这个方法里面, 大概的操作
- final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
- boolean evict) {
- Node<K,V>[] tab; Node<K,V> p; int n, i;
- if ((tab = table) == null || (n = tab.length) == 0)
- n = (tab = resize()).length; // 这一步之前分析过了, 就是判断数组为 null 或长度为 0 时, 对数组进行扩容
- if ((p = tab[i = (n - 1) & hash]) == null)
- tab[i] = newNode(hash, key, value, null); // 这一步其实也很清楚了, 就是根据 hash 值计算出数组的脚标, 然后判断数组的该脚标的元素是否为空, 为空的话就把 put 进来的数据封装成节点赋值进数组
- else {
- // 根据上面的两个判断, 那么走到这里的代码就是说, 数组不为空, 而且 put 进来的 key 计算所得的脚标节点也不为空, 走这一块逻辑(实际上这块逻辑也跟扩容的阈值无关, 只是单纯的判断然后加节点的操作, 但是我还是解释下这里的代码)
- Node<K,V> e; K k;
- if (p.hash == hash &&
- ((k = p.key) == key || (key != null && key.equals(k))))
- e = p;// 这里的意思是说, 如果 hash 值相同, key 值也相同, 那么就说明此时 put 操作的元素在数组从存在, 这覆盖该节点
- else if (p instanceof TreeNode)
- e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 这里是判断节点类型是否是树类型, 为什么会是树类型呢? 不是说是 HashMap 是数组加链表吗? 后面的章节会详细讲到, 这里暂且跳过
- else {
- // 代码走到这里, 就说明此时 put 进来的元素, 对应的数组脚标是个链表
- for (int binCount = 0; ; ++binCount) {
- // 此处的代码后面讲链表时会细讲, 这里暂且跳过
- if ((e = p.next) == null) {
- p.next = newNode(hash, key, value, null);
- if (binCount>= TREEIFY_THRESHOLD - 1) // -1 for 1st
- treeifyBin(tab, hash);
- break;
- }
- // 这里判断 hash 值与 key 值是否都相同, 如果是即说明 map 中存在该 key-value, 此时跳出循环
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- break;
- p = e;
- }
- }
- // 此逻辑是判断 hash 值与 key 值是否都相同跳出循环后, 将新值覆盖旧值, 然后将旧值返回出去
- if (e != null) { // existing mapping for key
- V oldValue = e.value;
- if (!onlyIfAbsent || oldValue == null)
- e.value = value;
- afterNodeAccess(e);
- return oldValue;
- }
- }
- ++modCount;//hashMap 内部维护的一个修改的次数, 有兴趣了解的话可以看源码里面对这个属性的翻译
- if (++size> threshold)
- resize();// 扩容, 在此之前的代码, 都是判断之后进行添加覆盖节点的操作, 此处是插入新节点之后判断是否扩容, 所以这里的条件就是我们找了这么久的扩容的阈值!!!
- afterNodeInsertion(evict);
- return null;
- }
? 走读完上面的代码, 我们可以得知 if (++size> threshold), 如下代码可知 size 实际上就是 HashMap 集合的键值对数, 即长度, 所以就是说, 当 size 的大小超过 threshold 时, 开始进行扩容, 也即 threshold 就是进行扩容的阈值. 那么这个阈值的大小是多少呢?
- /**
- * The number of key-value mappings contained in this map.
- */
- transient int size;
- /**
- * Returns the number of key-value mappings in this map.
- *
- * @return the number of key-value mappings in this map
- */
- public int size() {
- return size;
- }
? 继续走读源码, 找到 resize()方法处,
resize 方法初始化数组长度与阈值
- /**
- * The load factor used when none specified in constructor.
- */
- static final float DEFAULT_LOAD_FACTOR = 0.75f;
- /**
- * The default initial capacity - MUST be a power of two.
- */
- static final int DEFAULT_INITIAL_CAPACITY = 1 <<4; // aka 16
? 当 HashMap 数组为 null 或长度为 0 时, 初始化 threshold 的值, DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY,DEFAULT_INITIAL_CAPACITY 为数组的初始长度, DEFAULT_LOAD_FACTOR 是阈值的计算因子, 他的值是 0.75f, 意思就是当 HashMap 的 size 超过数组长度的 75% 的时候, 就进行扩容.
? 我们可以继续走读源码来验证是否数组长度超过 75% 就进行扩容, 还是上面那张图的源码, 我把其中一段给抽离出来, 如下:
- if (oldCap> 0) {
- if (oldCap>= MAXIMUM_CAPACITY) {
- threshold = Integer.MAX_VALUE;
- return oldTab;
- }
- // 此处的意思是说, 当数组的长度是大于 0 的时候, 而且数组扩容一倍之后, 小于默认配置的最大值时, 并且大于初始化数组的长度, 则执行 if 下面的代码, 那就是说, 扩容之后如果没超过最大值, 就走这个逻辑
- else if ((newCap = oldCap <<1) < MAXIMUM_CAPACITY &&
- oldCap>= DEFAULT_INITIAL_CAPACITY)
- // 而这个逻辑的代码意思, 就是阈值 threshold 增大一倍(左移一位)
- newThr = oldThr <<1; // double threshold
- }
? 那么, 我们就知道了, 当数组扩容时, threshold 的值也会增大一倍, 那么下一次扩容时, 也是 HashMap 的 size 超过数组长度的 75% 的时候, 就进行扩容.
扩容
? HashMap 内数组的扩容是将数组的长度左移一位, 在二进制运算中, 左移一位实际上就是将数值扩大一倍. 而且我们也知道, 扩容的源码就是 resize()这个方法, 所以这一章节就来重点解读 resize()方法的源码
- /**
- * Initializes or doubles table size. If null, allocates in
- * accord with initial capacity target held in field threshold.
- * Otherwise, because we are using power-of-two expansion, the
- * elements from each bin must either stay at same index, or move
- * with a power of two offset in the new table.
- *
- * @return the table
- */
- final Node<K,V>[] resize() {
- Node<K,V>[] oldTab = table; //oldTab 就是扩容前数组对象
- int oldCap = (oldTab == null) ? 0 : oldTab.length; //oldCap 就是扩容前数组的长度
- int oldThr = threshold; //oldThr 就是扩容前的阈值
- int newCap, newThr = 0; // 声明 newCap - 扩容后的数组长度, newThr - 扩容后的阈值
- if (oldCap> 0) {
- // 这一部分逻辑其实上一节已经讲过了, 在这里我就大致说一下, 就是如果这是扩容前数组长度已经达到了默认配置的最大值时, 那么就不扩容了, 直接返回原数组, 否则, 数组扩容一倍, 阈值也增大一倍
- if (oldCap>= MAXIMUM_CAPACITY) {
- threshold = Integer.MAX_VALUE;
- return oldTab;
- }
- else if ((newCap = oldCap <<1) < MAXIMUM_CAPACITY &&
- oldCap>= DEFAULT_INITIAL_CAPACITY)
- newThr = oldThr <<1; // double threshold
- }
- else if (oldThr> 0) // initial capacity was placed in threshold
- newCap = oldThr; // 这个判断不是正常创建 Map 集合走的逻辑, 这里可以跳过这句代码
- else { // zero initial threshold signifies using defaults
- // 这一步的代码前面也解释过了, 就是当数组长度为 0, 初始化数组长度与扩容的阈值
- newCap = DEFAULT_INITIAL_CAPACITY;
- newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
- }
- if (newThr == 0) {
- float ft = (float)newCap * loadFactor;
- newThr = (newCap <MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
- (int)ft : Integer.MAX_VALUE);
- }
- // 将新的扩容后的阈值赋值给 threshold
- threshold = newThr;
- @SuppressWarnings({"rawtypes","unchecked"})
- Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 创建新的数组
- table = newTab;
- if (oldTab != null) {
- for (int j = 0; j <oldCap; ++j) {
- // 遍历旧的数组, 下面的内容就是将旧数组重新散列将数据保存到新数组
- Node<K,V> e;
- if ((e = oldTab[j]) != null) {
- oldTab[j] = null;
- // 如果节点下没有下一个节点, 就是说不是链表仅是单个节点走这个逻辑
- if (e.next == null)
- newTab[e.hash & (newCap - 1)] = e; // 根据 hash 值与新数组的长度进行与操作, 获取新数组的脚标值, 将节点存储到新数组
- else if (e instanceof TreeNode) // 如果节点是树节点, 走这个逻辑, 后面讲链表的红黑树的时候会做解释, 这里先跳过
- ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
- else { // 所以这一部分的逻辑, 就是如果节点是链表, 走这里
- Node<K,V> loHead = null, loTail = null;
- Node<K,V> hiHead = null, hiTail = null;
- Node<K,V> next;
- do {
- // 遍历链表
- next = e.next; // 链表中的节点
- if ((e.hash & oldCap) == 0) {
- // 这个判断是理解这整个链表遍历的关键, 这里也涉及到了前面讲到的 2^n-1 对应二进制是 0111xxxx 的内容, 我们知道数组的长度总是 2^n, 所以 oldCap 的值实际上就是 1000xxxx, 然后 hash & oldCap 的操作, 就是判断 oldCap 高位的 1 与对应 hash 那一位的值是否是 1, 如果是 0 走这个逻辑, 如果是 1 走下面的 else 代码
- // 这里, 前面声明的 4 个变量 loHead, loTail, hiHead, hiTail 中, lo 的指的是低位, hi 的指的是高位, 走完这个 do 里面的逻辑, 就是将 oldCap 高位的 1 与对应 hash 那一位的值是 0 的存到 loTail 这个链表中, 高位是 1 的存到 hiTail 这个链表中!!!!
- 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 存放到新数组的原脚标处
- loTail.next = null;
- newTab[j] = loHead;
- }
- if (hiTail != null) {
- // 将上面遍历之后高位的 hiTail 存放到新数组的扩容后的脚标处
- hiTail.next = null;
- newTab[j + oldCap] = hiHead;
- }
- }
- }
- }
- }
- return newTab;
- }
? 在上面的源码解读中, 我们可能会留有一个问题, 就是为什么扩容后, 对数组中的链表还要做 (e.hash & oldCap) == 0 的判断?
? 实际上这部分逻辑是为了提高 HashMap 的查询性能, 因为数组扩容后, 节点要重新散列, 那么节点上面的链表当然也最好要做到均匀的分布, 减少单个数组节点上的链表长度, 变相的提高了查询性能. 所以, 源码的逻辑是在扩容后将低位的 loTail 存放到新数组的原脚标处, 高位的 hiTail 存放到新数组的扩容后的脚标处(jdk1.8 新设计)
jdk1.8 hashMap 扩容例图
? 注: 有同学可能会纠结于, 为什么代码中高位的链表是直接 j + oldCap 的脚标, 不需要重新计算 hash 与上新数组长度计算吗? 其实这是一个简单的数学问题而已, 你自己举个例子计算一下就可以明白, 结果是一样的
链表的 "扩容"
? 前面的章节已经对 HashMap 数组的扩容及其重新散列的内容讲完了, 这一章节的内容来讲一讲链表的 "扩容". 根据前面的内容, 我们了解到, 如果链表的长度越来越长, HashMap 的查询效率也会随之降低. 所以单纯的对链表长度的增加, 显然是不可取的.
? 所以在 HashMap 中, 对于链表实际上并没有扩容操作. 在本文开头列出的 Node 节点的源码中也可以看到, 内部并没有维护一个 size 或者 length 的属性, 也没有一个去获取 length 或 size 相关的方法, 所以本章节主要阐述的内容, 是链表结构向树状结构的转化.
单链表 -->红黑树
? 在前面 "数组扩容的阈值" 章节的时候, 我曾解读过 putVal 方法的代码, 在解读过程中, 我跳过了两次代码逻辑, 在这一章节我就来详细的解读这两处逻辑
putVal 方法未解读的两处逻辑
? 我们先看 for 循环遍历处的代码, 此处的遍历的内容是 HashMap 是 put 操作节点是为链表时的逻辑: 首先这里先判断链表的 next 节点是否为空, 为空则将 put 操作的 key-value 封装为 node 对象, 赋值给 next 节点, 然后下一步的判断 if (binCount>= TREEIFY_THRESHOLD - 1)是这里的关键, TREEIFY_THRESHOLD 这个是什么呢? THRESHOLD 这个单词是不是看着有点眼熟, 在前面将数组扩容的阈值的时候, 是不是用的这个单词, 那在这里的 TREEIFY_THRESHOLD 会不会就是链表结构转树状结构的阈值呢?
? 通过上面这段代码的上下文, 我们知道 binCount 就是链表的长度(注意: 这里是从 0 开始的), 而 TREEIFY_THRESHOLD 看下面的源码, 默认值是 8, 意思就是说当链表的长度, 大于等于 8 时, 就执行 treeifyBin(tab, hash);
- /**
- * The bin count threshold for using a tree rather than list for a
- * bin. Bins are converted to trees when adding an element to a
- * bin with at least this many nodes. The value must be greater
- * than 2 and should be at least 8 to mesh with assumptions in
- * tree removal about conversion back to plain bins upon
- * shrinkage.
- */
- static final int TREEIFY_THRESHOLD = 8;
? treeifyBin(tab, hash); 方法的内容是做什么呢?
- /**
- * Replaces all linked nodes in bin at index for given hash unless
- * table is too small, in which case resizes instead.
- */
- // 翻译大概的意思就是, 在给定 hash 的节点处替换节点类型, 除非是数组的长度太小了, 才进行 resize 操作
- // 总结就是说, 并不是链表的长度超过了默认的阈值 8 时, 就一定转树状结构, 还要判断数组的长度是否已经经过了扩容
- final void treeifyBin(Node<K,V>[] tab, int hash) {
- int n, index; Node<K,V> e;
- // 这里就是上面翻译说的判断, MIN_TREEIFY_CAPACITY 的值是 64, 就是说如果你的数组没有经过扩容操作的情况下, 如果链表长度已经超过 8 了, 此时不转树状结构, 而是进行数组扩容, 数组扩容时会重新散列, 将链表的节点均匀的分布, 查询效率对比转树状结构也要好, 不得不佩服设计者的设计.
- if (tab == null || (n = tab.length) <MIN_TREEIFY_CAPACITY)
- resize();
- else if ((e = tab[index = (n - 1) & hash]) != null) {
- // 此处代码就是找到给定的 hash 的节点, 将此节点的链表转为红黑树, 下面的代码主要是数据结构代码的内容, 有兴趣的同学可以自己解读, 由于时间原因, 我就不解读这部分转红黑树的代码了
- TreeNode<K,V> hd = null, tl = null;
- do {
- TreeNode<K,V> p = replacementTreeNode(e, null);
- if (tl == null)
- hd = p;
- else {
- p.prev = tl;
- tl.next = p;
- }
- tl = p;
- } while ((e = e.next) != null);
- if ((tab[index] = hd) != null)
- hd.treeify(tab);
- }
- }
? 在上面的源码解读中, 我们知道, 并不是链表的长度超过了默认的阈值 8 时, 就一定转树状结构, 还要判断数组的长度是否已经经过了扩容, 就是说如果你的数组没有经过扩容操作的情况下, 如果链表长度已经超过 8 了, 此时不转树状结构, 而是进行数组扩容, 数组扩容时会重新散列, 将链表的节点均匀的分布, 查询效率对比转树状结构也要好.
? 那么在数组扩容后, 链表长度也超过了 8, 此时就进行转红黑树的操作, 那红黑树又是什么呢?
hashMap 链表转红黑树
? 我们知道链表的查询时间复杂度最坏的情况有可能是 O(n) , 当你想要找到节点刚好是在链表的最后一个时, 你就必须得遍历完链表中所有的节点才能找到你要的值, 查找效率太低. 而红黑树的本质其实是一棵平衡二叉查找树, 平衡二叉查找树的特点就是左子节点小于等于父节点, 右子节点大于等于父节点, 所以他的查询时间复杂度是 O(Log2n) , 比链表的 O(n) 效率就要高很多了.
? 本章开头说到的另一处未解读的 putVal 源码, 其实只是判断是树状结构时, 将节点按照红黑树的规则, put 进树中而已.
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
HashTable 的数据结构
? 在前面解读的 HashMap 中, 已经将 HashMap 的数据结构, 还有 put 操作, 扩容做了详细的解读, 而其实 HashTable, 只是在 HashMap 的基础上, 给各个操作都加上了 synchronized 关键字而已, 这就是我们常说的 HashTable 是线程安全的, 而 HashMap 是线程不安全的, 如下代码.
- public class Hashtable<K,V>
- extends Dictionary<K,V>
- implements Map<K,V>, Cloneable, java.io.Serializable {
- private transient Entry<?,?>[] table; // 数组
- private int threshold; // 数组扩容阈值
- private float loadFactor;
- // 链表实体类
- private static class Entry<K,V> implements Map.Entry<K,V> {
- final int hash;
- final K key;
- V value;
- Entry<K,V> next;
- //put 方法
- public synchronized V put(K key, V value) {
- // Make sure the value is not null
- if (value == null) {
- throw new NullPointerException();
- }
- //remove 方法
- public synchronized V remove(Object key) {
- Entry<?,?> tab[] = table;
- int hash = key.hashCode();
- int index = (hash & 0x7FFFFFFF) % tab.length;
- //get 方法
- public synchronized V get(Object key) {
- Entry<?,?> tab[] = table;
- int hash = key.hashCode();
- int index = (hash & 0x7FFFFFFF) % tab.length;
- for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
- if ((e.hash == hash) && e.key.equals(key)) {
- return (V)e.value;
- }
- }
- return null;
- }
? 内部也是维护了一个数组与链表, 然后在 put,get 等方法上都加上 synchronized 关键字, 那这样就能确保 HashTable 在任何场景都是线程安全的吗?
HashTable 是否在任何场景都是线程安全的?
? 这里有几个场景:
(1)若 key 不存在, 则添加元素
(2)若 key 存在, 则删除元素
我在这里画张图来描述下多线程环境下的这两个场景
hashtable 在复合操作下的线程安全问题
存在这样问题的原因是复合操作的场景下, HashTable 不是线程安全的, 因为 HashTable 只是保证单个方法操作是原子性的, 但在不保证原子性的复合操作下, HashTable 也存在线程安全问题.
ConCurrentHashMap 的数据结构
? 我们知道 HashTable 的性能比 HashMap 的差很多, 因为 HashTable 在每个操作方法上面都加了 synchronized 关键字, 而且在复合场景下还存在线程安全问题, 所以 HashTable 算是旧版本遗留下来的问题了, 现在的实际开发中一般也不会去使用到 HashTable, 但是在 jdk1.5 以后新增了 java.util.concurrent 包, 在这个包下提供了很多线程安全又高性能的集合, 其中就包含了本章的主角 ConCurrentHashMap
jdk1.7 分段锁
? 在 jdk1.5 以后到 jdk1.7 ,ConCurrentHashMap 在解决多线程场景下的线程安全问题, 采用的是分段锁的技术.
? 我们知道 HashTable 之所以性能低下, 是因为其在 public 方法的实现上都加上了 synchronized 的关键字, 即当任意一个 put 或 get 操作, 都将整个 map 对象锁住, 只有等待持有锁的线程操作结束, 才有机会获得锁进行操作.
? 这里有一种场景, 在 Map 的数组 table 中, 线程 1 对 table[0] 进行 put 操作, 而此时有线程 2 想对 table[1] 进行 put 操作, 实际上两者的 put 操作互不干涉, 而在 HashTable 的实现下, 线程 2 只能等待线程 1 操作完成之后才能执行. 那么, 我们是否可以这样实现, 当线程 1 对 table[0] 进行 put 操作时, 对 table[0] 下的链表进行加锁, 而操作 table[1] 时, 对 table[1] 的链表进行加锁, 各自那各自的锁, 这样线程 1 在操作 table[0] 时, 线程 2 也可以操作 table[1].
ConcurrentHashMap 分段锁结构图
? 分段锁采用的就是这种思想, 在 ConCurrentHashMap 中维护着 Segment[]的数组, 这种实现方式把原本 HashTable 粗粒度的锁实现, 拆分成一段一段的 Segment 锁.
- //jdk1.7 的 ConcurrentHashMap 的源码
- public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
- implements ConcurrentMap<K, V>, Serializable {
- /**
- Mask value for indexing into segments. The upper bits of a
- key's hash code are used to choose the segment.
- */
- final int segmentMask;
- /**
- Shift value for indexing within segments.
- */
- final int segmentShift;
- /**
- The segments, each of which is a specialized hash table.
- */
- //Segment 是继承了可重入锁的子类, 所以在 Segment 的操作方法中, 包含了 tryLock,unLock 等方法
- final Segment<K,V>[] segments;
- /**
- Segments are specialized versions of hash tables. This
- subclasses from ReentrantLock opportunistically, just to
- simplify some locking and avoid separate construction.
- */
- static final class Segment<K,V> extends ReentrantLock implements Serializable {
- /**
- * The per-segment table. Elements are accessed via
- * entryAt/setEntryAt providing volatile semantics.
- */
- transient volatile HashEntry<K,V>[] table;
- }
- }
? 简单理解就是, ConcurrentHashMap 维护一个 Segment 数组, Segment 通过继承 ReentrantLock 来进行加锁, 所以每次需要加锁的操作锁住的是一个 Segment, 这样只要保证每个 Segment 是线程安全的, 也就实现了全局的线程安全.
ConcurrentHashMap 的 Segment 结构
? 如下, 是 ConcurrentHashMap 的各个构造方法, 但是实际上只有 public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)该构造方法是真正完成初始化的方法, 其他的都是方法重载
- public ConcurrentHashMap(int initialCapacity,
- float loadFactor, int concurrencyLevel) {
- if (!(loadFactor> 0) || initialCapacity <0 || concurrencyLevel <= 0)
- throw new IllegalArgumentException();
- if (concurrencyLevel> MAX_SEGMENTS)
- concurrencyLevel = MAX_SEGMENTS;
- // Find power-of-two sizes best matching arguments
- int sshift = 0;
- int ssize = 1;
- // 计算并行级别 ssize, 因为要保持并行级别是 2 的 n 次方
- while (ssize <concurrencyLevel) {
- ++sshift;
- ssize <<= 1;
- }
- // 我们这里先不要那么烧脑, 用默认值, concurrencyLevel 为 16,sshift 为 4
- // 那么计算出 segmentShift 为 28,segmentMask 为 15, 后面会用到这两个值
- this.segmentShift = 32 - sshift;
- this.segmentMask = ssize - 1;
- if (initialCapacity> MAXIMUM_CAPACITY)
- initialCapacity = MAXIMUM_CAPACITY;
- // initialCapacity 是设置整个 map 初始的大小,
- // 这里根据 initialCapacity 计算 Segment 数组中每个位置可以分到的大小
- // 如 initialCapacity 为 64, 那么每个 Segment 或称之为 "槽" 可以分到 4 个
- int c = initialCapacity / ssize;
- if (c * ssize <initialCapacity)
- ++c;
- // 默认 MIN_SEGMENT_TABLE_CAPACITY 是 2, 这个值也是有讲究的, 因为这样的话, 对于具体的槽上,
- // 插入一个元素不至于扩容, 插入第二个的时候才会扩容
- int cap = MIN_SEGMENT_TABLE_CAPACITY;
- while (cap < c)
- cap <<= 1;
- // 创建 Segment 数组,
- // 并创建数组的第一个元素 segment[0]
- Segment<K,V> s0 =
- new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
- (HashEntry<K,V>[])new HashEntry[cap]);
- Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
- // 往数组写入 segment[0]
- UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
- this.segments = ss;
- }
- public ConcurrentHashMap(int initialCapacity, float loadFactor) {
- this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
- }
- public ConcurrentHashMap(int initialCapacity) {
- this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
- }
- public ConcurrentHashMap() {
- this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
- }
- public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
- this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
- DEFAULT_INITIAL_CAPACITY),
- DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
- putAll(m);
- }
? concurrencyLevel: 并行级别, 并发数, Segment 数, 怎么翻译不重要, 理解它. 默认是 16, 也就是说 ConcurrentHashMap 有 16 个 Segments, 所以理论上, 这个时候, 最多可以同时支持 16 个线程并发写, 只要它们的操作分别分布在不同的 Segment 上. 这个值可以在初始化的时候设置为其他值, 但是一旦初始化以后, 它是不可以扩容的.
? 再具体到每个 Segment 内部, 其实每个 Segment 很像前面介绍的 HashMap, 不过它要保证线程安全, 所以处理起来要麻烦些.
? initialCapacity: 初始容量, 这个值指的是整个 ConcurrentHashMap 的初始容量, 实际操作的时候需要平均分给每个 Segment.
? loadFactor: 负载因子, 之前我们说了, Segment 数组不可以扩容, 所以这个负载因子是给每个 Segment 内部使用的.
jdk1.8 的新特性: CAS
? 在 jdk1.8 以下版本的 ConcurrentHashMap 为了保证线程安全又要提供高性能的情况下, 采用锁分段的技术, 而在 java8 中对于 ConcurrentHashMap 的实现又变成了另外一种方式 ----CAS
? CAS 的全称是 compare and swap, 直译过来就是比较与替换. CAS 的机制就相当于这种(非阻塞算法),CAS 是由 CPU 硬件实现, 所以执行相当快. CAS 有三个操作参数: 内存地址, 期望值, 要修改的新值, 当期望值和内存当中的值进行比较不相等的时候, 表示内存中的值已经被别线程改动过, 这时候失败返回, 当相等的时候, 将内存中的值改为新的值, 并返回成功.
? 这里也不去细讲多线程, 锁, CAS 这些内容, 后续等有空再整理一篇文档出来做详细点的笔记, 这里只当做体会精神, 理解思想即可.
? 下面的代码是摘自网上一篇文章的对 java8 中 ConcurrentHashMap 的源码分析, 也是为了方便自己后续当笔记学习来看.
- public V put(K key, V value) {
- return putVal(key, value, false);
- }
- final V putVal(K key, V value, boolean onlyIfAbsent) {
- if (key == null || value == null) throw new NullPointerException();
- // 得到 hash 值
- int hash = spread(key.hashCode());
- // 用于记录相应链表的长度
- int binCount = 0;
- for (Node<K,V>[] tab = table;;) {
- Node<K,V> f; int n, i, fh;
- // 如果数组 "空", 进行数组初始化
- if (tab == null || (n = tab.length) == 0)
- // 初始化数组, 后面会详细介绍
- tab = initTable();
- // 找该 hash 值对应的数组下标, 得到第一个节点 f
- else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
- // 如果数组该位置为空,
- // 用一次 CAS 操作将这个新值放入其中即可, 这个 put 操作差不多就结束了, 可以拉到最后面了
- // 如果 CAS 失败, 那就是有并发操作, 进到下一个循环就好了
- if (casTabAt(tab, i, null,
- new Node<K,V>(hash, key, value, null)))
- break; // no lock when adding to empty bin
- }
- // hash 居然可以等于 MOVED, 这个需要到后面才能看明白, 不过从名字上也能猜到, 肯定是因为在扩容
- else if ((fh = f.hash) == MOVED)
- // 帮助数据迁移, 这个等到看完数据迁移部分的介绍后, 再理解这个就很简单了
- tab = helpTransfer(tab, f);
- else { // 到这里就是说, f 是该位置的头结点, 而且不为空
- V oldVal = null;
- // 获取数组该位置的头结点的监视器锁
- synchronized (f) {
- if (tabAt(tab, i) == f) {
- if (fh>= 0) { // 头结点的 hash 值大于 0, 说明是链表
- // 用于累加, 记录链表的长度
- binCount = 1;
- // 遍历链表
- for (Node<K,V> e = f;; ++binCount) {
- K ek;
- // 如果发现了 "相等" 的 key, 判断是否要进行值覆盖, 然后也就可以 break 了
- if (e.hash == hash &&
- ((ek = e.key) == key ||
- (ek != null && key.equals(ek)))) {
- oldVal = e.val;
- if (!onlyIfAbsent)
- e.val = value;
- break;
- }
- // 到了链表的最末端, 将这个新值放到链表的最后面
- Node<K,V> pred = e;
- if ((e = e.next) == null) {
- pred.next = new Node<K,V>(hash, key,
- value, null);
- break;
- }
- }
- }
- else if (f instanceof TreeBin) { // 红黑树
- Node<K,V> p;
- binCount = 2;
- // 调用红黑树的插值方法插入新节点
- if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
- value)) != null) {
- oldVal = p.val;
- if (!onlyIfAbsent)
- p.val = value;
- }
- }
- }
- }
- // binCount != 0 说明上面在做链表操作
- if (binCount != 0) {
- // 判断是否要将链表转换为红黑树, 临界值和 HashMap 一样, 也是 8
- if (binCount>= TREEIFY_THRESHOLD)
- // 这个方法和 HashMap 中稍微有一点点不同, 那就是它不是一定会进行红黑树转换,
- // 如果当前数组的长度小于 64, 那么会选择进行数组扩容, 而不是转换为红黑树
- // 具体源码我们就不看了, 扩容部分后面说
- treeifyBin(tab, i);
- if (oldVal != null)
- return oldVal;
- break;
- }
- }
- }
- //
- addCount(1L, binCount);
- return null;
- }
来源: http://www.bubuko.com/infodetail-2693903.html