HashMap集合超详解（下）

转x33g5p2x  于2022-03-15 转载在 Java  
字(18.0k)|赞(0)|评价(0)|浏览(392)

1、HashMap构造方法

HashMap中的重要的构造方法如下：

  1. HashMap()

构造一个空的HashMap，默认初始容量（16）和默认负载因子（0.75）。

  1. public HashMap() {
  2.    this.loadFactor = DEFAULT_LOAD_FACTOR; // 将默认的负载因子0.75赋值给loadFactor，并没有创建数组
  3. }
  1. HashMap(int initialCapacity)

构造一个具有指定的初始容量和默认负载因子（0.75）HashMap 。

  1. // 指定“容量大小”的构造函数
  2. public HashMap(int initialCapacity) {
  3.     this(initialCapacity, DEFAULT_LOAD_FACTOR);
  4. }
  1. HashMap(int initialCapacity, float loadFactor)

构造一个具有指定的初始容量和负载因子的 HashMap。

  1. /*
  2. 	 指定“容量大小”和“负载因子”的构造函数
  3. 	 initialCapacity：指定的容量
  4. 	 loadFactor:指定的负载因子
  5. */
  6. public HashMap(int initialCapacity, float loadFactor) {
  7.     	// 判断初始化容量initialCapacity是否小于0
  8.         if (initialCapacity < 0)
  9.             // 如果小于0，则抛出非法的参数异常IllegalArgumentException
  10.             throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
  11.     	// 判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY
  12.         if (initialCapacity > MAXIMUM_CAPACITY)
  13.             // 如果超过MAXIMUM_CAPACITY，会将MAXIMUM_CAPACITY赋值给initialCapacity
  14.             initialCapacity = MAXIMUM_CAPACITY;
  15.     	// 判断负载因子loadFactor是否小于等于0或者是否是一个非数值
  16.         if (loadFactor <= 0 || Float.isNaN(loadFactor))
  17.             // 如果满足上述其中之一，则抛出非法的参数异常IllegalArgumentException
  18.             throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
  19.      	// 将指定的负载因子赋值给HashMap成员变量的负载因子loadFactor
  20.         this.loadFactor = loadFactor;
  21.         this.threshold = tableSizeFor(initialCapacity);
  22.     }
  23. // 最后调用了tableSizeFor，来看一下方法实现：
  24.      /*
  25.      	返回比指定初始化容量大的最小的2的n次幂
  26.      */
  27.     static final int tableSizeFor(int cap) {
  28.         int n = cap - 1;
  29.         n |= n >>> 1;
  30.         n |= n >>> 2;
  31.         n |= n >>> 4;
  32.         n |= n >>> 8;
  33.         n |= n >>> 16;
  34.         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  35.     }

说明：

对于 java源码中 this.threshold = tableSizeFor(initialCapacity); 疑问解答：

  1. tableSizeFor(initialCapacity)判断指定的初始化容量是否是2的n次幂，如果不是那么会变为比指定初始化容量大的最小的2的n次幂。
  2. 但是注意，在tableSizeFor方法体内部将计算后的数据返回给调用这里了，并且直接赋值给threshold边界值了。有些人会觉得这里是一个bug，应该这样书写：
  3. this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;
  4. 这样才符合threshold的意思（当HashMap的size到达threshold这个阈值时会扩容）。
  5. 但是请注意，在jdk8以后的构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算。
  1. HashMap(Map<? extends K, ? extends V> m)

其中使用到了另一个 “Map” 的构造函数

  1. // 构造一个映射关系与指定 Map 相同的新 HashMap。
  2. public HashMap(Map<? extends K, ? extends V> m) {
  3.     	// 负载因子loadFactor变为默认的负载因子0.75
  4.          this.loadFactor = DEFAULT_LOAD_FACTOR;
  5.          putMapEntries(m, false);
  6.  }

最后调用了 putMapEntries()，来看一下方法实现：

  1. final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
  2.     //获取参数集合的长度
  3.     int s = m.size();
  4.     if (s > 0) {
  5.         //判断参数集合的长度是否大于0，说明大于0
  6.         if (table == null) { // 判断table是否已经初始化
  7.                 // 未初始化，s为m的实际元素个数
  8.                 float ft = ((float)s / loadFactor) + 1.0F;
  9.                 int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
  10.                 // 计算得到的t大于阈值，则初始化阈值
  11.                 if (t > threshold)
  12.                     threshold = tableSizeFor(t);
  13.         }
  14.         // 已初始化，并且m元素个数大于阈值，进行扩容处理
  15.         else if (s > threshold)
  16.             resize();
  17.         // 将m中的所有元素添加至HashMap中
  18.         for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
  19.             K key = e.getKey();
  20.             V value = e.getValue();
  21.             putVal(hash(key), key, value, false, evict);
  22.         }
  23.     }
  24. }

注意：

float ft = ((float)s / loadFactor) + 1.0F;这一行代码中为什么要加 1.0F ？

s/loadFactor 的结果是小数，加 1.0F 与 (int)ft 相当于是对小数做一个向上取整以尽可能的保证更大容量，更大的容量能够减少 resize 的调用次数。所以 + 1.0F 是为了获取更大的容量，减少数组的扩容次数（因为数组频繁进行扩容会降低性能）。

例如：原来集合的元素个数是 6 个，那么 6/0.75 是8，是 2 的n次幂，那么新的数组大小就是 8 了。然后原来数组的数据就会存储到长度是 8 的新的数组中了，这样会导致在存储元素的时候，容量不够，还得继续扩容，那么性能降低了，而如果 +1 呢，数组长度直接变为16了，这样可以减少数组的扩容。

2、HashMap的成员方法

2.1、put()

put方法是比较复杂的，实现步骤大致如下：

  1. 先通过 hash 值计算出 key 映射到哪个桶；
  2. 然后比较插入的 key 和对应的已存在的 key 进行 hash 值的比较，如果桶上没有碰撞冲突，则直接插入；
  3. 如果出现碰撞冲突了，则需要处理冲突：

（a）、如果此时链表长度大于 8 并且数组长度大于 64 ，则该桶使用红黑树处理冲突，则调用红黑树的方法插入数据；

（b）、否则采用传统的链式方法插入。如果链的长度达到临界值，则把链转变为红黑树；

  1. 如果桶中存在重复的键，则为该键替换新值 value；
  2. 如果 size 大于阈值 threshold，则进行扩容；

put() 方法源码如下：

  1. public V put(K key, V value) {
  2.     return putVal(hash(key), key, value, false, true);
  3. }

说明：

  1. HashMap 只提供了 put 用于添加元素，putVal 方法只是给 put 方法调用的一个方法，并没有提供给用户使用。 所以我们重点看 putVal 方法。
  2. 我们可以看到在 putVal 方法中 key 在这里执行了一下 hash 方法,来看一下 hash 方法是如何实现的。
  1. static final int hash(Object key) {
  2. 	int h;
  3. 	/*
  4. 	1）如果key等于null：返回的是0.
  5. 	2）如果key不等于null：首先计算出key的hashCode赋值给h，然后与h无符号右移16位后的
  6. 		二进制进行按位异或得到最后的hash值
  7. 	*/
  8. 	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  9. }

从上面可以得知 HashMap 是支持 key 为 null 的，而 HashTable 是直接用 Key 来获取hashCode 所以 key 为空会抛异常。

解读上述 hash 方法：

我们先研究下 key 的哈希值是如何计算出来的。key 的哈希值是通过上述方法计算出来的。

这个哈希方法首先计算出 key 的 hashCode 赋值给 h，然后与 h 无符号右移 16 位后的二进制进行按位异或得到最后的 hash 值。计算过程如下所示：

  1. return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

在 putVal 函数中使用到了上述 hash 函数计算的哈希值：

  1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
  2. 	...
  3. 	if ((p = tab[i = (n - 1) & hash]) == null) // 这里的n表示数组长度16
  4. 	...
  5. }

说明：

  • key.hashCode()：返回散列值也就是 hashcode，假设随便生成的一个值。
  • n 表示数组初始化的长度是 16。
  • &（按位与运算）：运算规则：相同的二进制数位上，都是 1 的时候，结果为 1，否则为0。
  • ^（按位异或运算）：运算规则：相同的二进制数位上，数字相同，结果为 0，不同为 1。

计算过程如下所示：

  1. h = hashCode() : 1111 1111 1111 1111 1111 0000 1110 1010
  2. ----------------------------------------------------------
  3. h ：		1111 1111 1111 1111 1111 0000 1110 1010
  4. h >>> 16 ： 0000 0000 0000 0000 1111 1111 1111 1111
  5. -----------------------------------------------------------
  6. hash = h ^ (h >>> 16 ) 1111 1111 1111 1111 0000 1111 0001 0101
  8. （n - 1）： 0000 0000 0000 0000 0000 0000 0000 1111
  9. hash ：	   1111 1111 1111 1111 0000 1111 0001 0101
  10. ------------------------------------------------------------
  11. 0000 0000 0000 0000 0000 0000 0000 0101 （5）

简单来说就是：

高 16bit 不变，低 16bit 和高 16bit 做了一个异或（得到的 hashCode 转化为 32 位二进制，前 16 位和后 16 位低 16bit 和高 16bit 做了一个异或）。

问题：为什么要这样操作（就是将 h 右移 16 位之后再与 h 进行异或运算）呢？

如果当 n 即数组长度很小，假设是 16 的话，那么 n - 1 即为 1111 ，这样的值和 hashCode 直接做按位与操作，实际上只使用了哈希值的后 4 位。如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解决了这个问题（也就是减少 hash 冲突）。

2.2、putVal()

主要参数：

  • hash：key 的 hash 值
  • key：原始 key
  • value：要存放的值
  • onlyIfAbsent：如果 true 代表不更改现有的值
  • evict：如果为false表示 table 为创建状态

putVal 方法源代码如下所示：

  1. public V put(K key, V value) {
  2. 	return putVal(hash(key), key, value, false, true);
  3. }
  5. final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
  6.     Node<K,V>[] tab; Node<K,V> p; int n, i;
  7.     /*
  8.     	1）transient Node<K,V>[] table; 表示存储Map集合中元素的数组。
  9.     	2）(tab = table) == null 表示将空的table赋值给tab，然后判断tab是否等于null，第一次肯定是null。
  10.     	3）(n = tab.length) == 0 表示将数组的长度0赋值给n，然后判断n是否等于0，n等于0，由于if判断使用双或，满足一个即可，则执行代码 n = (tab = resize()).length; 进行数组初始化，并将初始化好的数组长度赋值给n。
  11.     	4）执行完n = (tab = resize()).length，数组tab每个空间都是null。
  12.     */
  13.     if ((tab = table) == null || (n = tab.length) == 0)
  14.         n = (tab = resize()).length;
  15.     /*
  16.     	1）i = (n - 1) & hash 表示计算数组的索引赋值给i，即确定元素存放在哪个桶中。
  17.     	2）p = tab[i = (n - 1) & hash]表示获取计算出的位置的数据赋值给结点p。
  18.     	3) (p = tab[i = (n - 1) & hash]) == null 判断结点位置是否等于null，如果为null，则执行代码：tab[i] = newNode(hash, key, value, null);根据键值对创建新的结点放入该位置的桶中。
  19.         小结：如果当前桶没有哈希碰撞冲突，则直接把键值对插入空间位置。
  20.     */ 
  21.     if ((p = tab[i = (n - 1) & hash]) == null)
  22.         // 创建一个新的结点存入到桶中
  23.         tab[i] = newNode(hash, key, value, null);
  24.     else {
  25.          // 执行else说明tab[i]不等于null，表示这个位置已经有值了
  26.         Node<K,V> e; K k;
  27.         /*
  28.         	比较桶中第一个元素(数组中的结点)的hash值和key是否相等
  29.         	1）p.hash == hash ：p.hash表示原来存在数据的hash值  hash表示后添加数据的hash值 比较两个hash值是否相等。
  30.                  说明：p表示tab[i]，即 newNode(hash, key, value, null)方法返回的Node对象。
  31.                     Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
  32.                         return new Node<>(hash, key, value, next);
  33.                     }
  34.                     而在Node类中具有成员变量hash用来记录着之前数据的hash值的。
  35.              2）(k = p.key) == key ：p.key获取原来数据的key赋值给k  key 表示后添加数据的key比较两个key的地址值是否相等。
  36.              3）key != null && key.equals(k)：能够执行到这里说明两个key的地址值不相等，那么先判断后添加的key是否等于null，如果不等于null再调用equals方法判断两个key的内容是否相等。
  37.         */
  38.         if (p.hash == hash &&
  39.             ((k = p.key) == key || (key != null && key.equals(k))))
  40.                 /*
  41.                 	说明：两个元素哈希值相等，并且key的值也相等，将旧的元素整体对象赋值给e，用e来记录
  42.                 */ 
  43.                 e = p;
  44.         // hash值不相等或者key不相等；判断p是否为红黑树结点
  45.         else if (p instanceof TreeNode)
  46.             // 放入树中
  47.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  48.         // 说明是链表结点
  49.         else {
  50.             /*
  51.             	1)如果是链表的话需要遍历到最后结点然后插入
  52.             	2)采用循环遍历的方式，判断链表中是否有重复的key
  53.             */
  54.             for (int binCount = 0; ; ++binCount) {
  55.                 /*
  56.                 	1)e = p.next 获取p的下一个元素赋值给e。
  57.                 	2)(e = p.next) == null 判断p.next是否等于null，等于null，说明p没有下一个元素，那么此时到达了链表的尾部，还没有找到重复的key,则说明HashMap没有包含该键，将该键值对插入链表中。
  58.                 */
  59.                 if ((e = p.next) == null) {
  60.                     /*
  61.                     	1）创建一个新的结点插入到尾部
  62.                     	 p.next = newNode(hash, key, value, null);
  63.                     	 Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
  64.                                 return new Node<>(hash, key, value, next);
  65.                          }
  66.                          注意第四个参数next是null，因为当前元素插入到链表末尾了，那么下一个结点肯定是null。
  67.                          2）这种添加方式也满足链表数据结构的特点，每次向后添加新的元素。
  68.                     */
  69.                     p.next = newNode(hash, key, value, null);
  70.                     /*
  71.                     	1)结点添加完成之后判断此时结点个数是否大于TREEIFY_THRESHOLD临界值8，如果大于则将链表转换为红黑树。
  72.                     	2）int binCount = 0 ：表示for循环的初始化值。从0开始计数。记录着遍历结点的个数。值是0表示第一个结点，1表示第二个结点。。。。7表示第八个结点，加上数组中的的一个元素，元素个数是9。
  73.                     	TREEIFY_THRESHOLD - 1 --》8 - 1 ---》7
  74.                     	如果binCount的值是7(加上数组中的的一个元素，元素个数是9)
  75.                     	TREEIFY_THRESHOLD - 1也是7，此时转换红黑树。
  76.                     */
  77.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  78.                         // 转换为红黑树
  79.                         treeifyBin(tab, hash);
  80.                     // 跳出循环
  81.                     break;
  82.                 }
  83.                  
  84.                 /*
  85.                 	执行到这里说明e = p.next 不是null，不是最后一个元素。继续判断链表中结点的key值与插入的元素的key值是否相等。
  86.                 */
  87.                 if (e.hash == hash &&
  88.                     ((k = e.key) == key || (key != null && key.equals(k))))
  89.                     // 相等，跳出循环
  90.                     /*
  91.                 		要添加的元素和链表中的存在的元素的key相等了，则跳出for循环。不用再继续比较了
  92.                 		直接执行下面的if语句去替换去 if (e != null) 
  93.                 	*/
  94.                     break;
  95.                 /*
  96.                 	说明新添加的元素和当前结点不相等，继续查找下一个结点。
  97.                 	用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
  98.                 */
  99.                 p = e;
  100.             }
  101.         }
  102.         /*
  103.         	表示在桶中找到key值、hash值与插入元素相等的结点
  104.         	也就是说通过上面的操作找到了重复的键，所以这里就是把该键的值变为新的值，并返回旧值
  105.         	这里完成了put方法的修改功能
  106.         */
  107.         if (e != null) { 
  108.             // 记录e的value
  109.             V oldValue = e.value;
  110.             // onlyIfAbsent为false或者旧值为null
  111.             if (!onlyIfAbsent || oldValue == null)
  112.                 // 用新值替换旧值
  113.                 // e.value 表示旧值  value表示新值 
  114.                 e.value = value;
  115.             // 访问后回调
  116.             afterNodeAccess(e);
  117.             // 返回旧值
  118.             return oldValue;
  119.         }
  120.     }
  121.     // 修改记录次数
  122.     ++modCount;
  123.     // 判断实际大小是否大于threshold阈值，如果超过则扩容
  124.     if (++size > threshold)
  125.         resize();
  126.     // 插入后回调
  127.     afterNodeInsertion(evict);
  128.     return null;
  129. }

2.3、treeifyBin()

  • treeifyBin()：将链表转换为红黑树

结点添加完成之后判断此时结点个数是否大于 TREEIFY_THRESHOLD 临界值 8，如果大于等于则将链表转换为红黑树，转换红黑树的方法 treeifyBin，整体代码如下：

  1. if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  2.    //转换为红黑树 tab表示数组名  hash表示哈希值
  3.    treeifyBin(tab, hash);

treeifyBin 方法如下所示：

  1. /*
  2. 	替换指定哈希表的索引处桶中的所有链接结点，除非表太小，否则将修改大小。
  3. 	Node<K,V>[] tab = tab 数组名
  4. 	int hash = hash表示哈希值
  5. */
  6. final void treeifyBin(Node<K,V>[] tab, int hash) {
  7.     int n, index; Node<K,V> e;
  8.     /*
  9.     	如果当前数组为空或者数组的长度小于进行树形化的阈值(MIN_TREEIFY_CAPACITY = 64)，就去扩容。而不是将结点变为红黑树。
  10.     	目的：如果数组很小，那么转换红黑树，然后遍历效率要低一些。这时进行扩容，那么重新计算哈希值，链表长度有可能就变短了，数据会放到数组中，这样相对来说效率高一些。
  11.     */
  12.     if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
  13.         //扩容方法
  14.         resize();
  15.     else if ((e = tab[index = (n - 1) & hash]) != null) {
  16.         /*
  17.         	1）执行到这里说明哈希表中的数组长度大于阈值64，开始进行树形化
  18.         	2）e = tab[index = (n - 1) & hash]表示将数组中的元素取出赋值给e，e是哈希表中指定位置桶里的链表结点，从第一个开始
  19.         */
  20.         // hd：红黑树的头结点   tl：红黑树的尾结点
  21.         TreeNode<K,V> hd = null, tl = null;
  22.         do {
  23.             // 新创建一个树的结点，内容和当前链表结点e一致
  24.             TreeNode<K,V> p = replacementTreeNode(e, null);
  25.             if (tl == null)
  26.                 hd = p; // 将新创键的p结点赋值给红黑树的头结点
  27.             else {
  28.                 p.prev = tl; // 将上一个结点p赋值给现在的p的前一个结点
  29.                 tl.next = p; // 将现在结点p作为树的尾结点的下一个结点
  30.             }
  31.             tl = p;
  32.             /*
  33.             	e = e.next 将当前结点的下一个结点赋值给e，如果下一个结点不等于null
  34.             	则回到上面继续取出链表中结点转换为红黑树
  35.             */
  36.         } while ((e = e.next) != null);
  37.         /*
  38.         	让桶中的第一个元素即数组中的元素指向新建的红黑树的结点，以后这个桶里的元素就是红黑树
  39.         	而不是链表数据结构了
  40.         */
  41.         if ((tab[index] = hd) != null)
  42.             hd.treeify(tab);
  43.     }
  44. }

小结：上述操作一共做了如下几件事：

  1. 根据哈希表中桶所对应的链表的元素个数以及数组长度（链表元素个数大于等于8并且数组长度大于等于64进行转换为红黑树）确定是扩容还是树形化。
  2. 如果是树形化遍历桶中的元素，创建相同个数的树形结点，复制内容，建立起联系。
  3. 然后让桶中的第一个元素指向新创建的树根结点，替换桶的链表内容为树形化内容。

2.4、resize()

（1）、扩容机制

  1. 什么时候才需要扩容
  • 当 HashMap 中的元素个数超过数组大小(数组长度)*loadFactor(负载因子)时，就会进行数组扩容，loadFactor 的默认值是 0.75。
  • 当某个桶所对应的链表的元素个数大于等于阈值 8 并且数组长度小于 64 的时候，我们需要对数组进行扩容。
  1. HashMap 的扩容是什么机制

进行扩容，会伴随着一次重新 hash 分配，并且会遍历 hash 表中所有的元素，是非常耗时的。在编写程序中，要尽量避免 resize。

HashMap 在进行扩容时，使用的 rehash 方式非常巧妙，因为每次扩容都是翻倍，与原来计算的 (n - 1) & hash 的结果相比，只是多了一个 bit 位，所以结点要么就在原来的位置，要么就被分配到 “原位置 + 旧容量” 这个位置。

例如我们从 16 扩展为 32 时，具体的变化如下所示：

  1. n = 16的时候 0000 0000 0000 0000 0000 0000 0001 0000
  2. n - 1 -> 15 0000 0000 0000 0000 0000 0000 0000 1111
  3. 假设对应的 hash值
  4. 	 key1： 1111 1111 1111 1111 0000 1111 0000 0101
  5. 	 key2： 1111 1111 1111 1111 0000 1111 0001 0101
  6. -------------------------------------------------------------
  7. 	   		0000 0000 0000 0000 0000 0000 0000 0101 5表示计算出来的索引是 5
  9. 扩容之后：16 * 2 = 32	   
  10. n = 32的时候 0000 0000 0000 0000 0000 0000 0010 0000
  11. n - 1 -> 15 0000 0000 0000 0000 0000 0000 0001 1111
  12. 假设对应的 hash值
  13. 	 key1： 1111 1111 1111 1111 0000 1111 0000 0101
  14. 	 key2： 1111 1111 1111 1111 0000 1111 0001 0101
  15. -------------------------------------------------------------
  16. 	  		 0000 0000 0000 0000 0000 0000 0000 0101 5表示计算出来的索引是 5
  17. 	  		 0000 0000 0000 0000 0000 0000 0001 0101 5 + 16表示计算出来的索引是 21

因此元素在重新计算 hash 之后，因为 n 变为 2 倍，那么 n - 1 的标记范围在高位多 1bit，因此新的 index 就会发生这样的变化。

说明：

5 是假设计算出来的原来的索引。这样就验证了上述所描述的：扩容之后所以结点要么就在原来的位置，要么就被分配到 “原位置 + 旧容量” 这个位置。

因此，我们在扩充 HashMap 的时候，不需要重新计算 hash，只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就可以了，是 0 的话索引没变，是 1 的话索引变成 “原位置 + 旧容量” 。可以看看下图为 16 扩充为 32 的 resize 示意图：

正是因为这样巧妙的 rehash 方式，既省去了重新计算 hash 值的时间，而且同时，由于新增的 1bit 是 0 还是 1 可以认为是随机的，在 resize 的过程中保证了 rehash 之后每个桶上的结点数一定小于等于原来桶上的结点数，保证了 rehash 之后不会出现更严重的 hash 冲突，均匀的把之前的冲突的结点分散到新的桶中了。

（2）、源码解读

下面是代码的具体实现：

  1. final Node<K,V>[] resize() {
  2.     // 得到当前数组
  3.     Node<K,V>[] oldTab = table;
  4.     // 如果当前数组等于null长度返回0，否则返回当前数组的长度
  5.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
  6.     //当前阀值点 默认是12(16*0.75)
  7.     int oldThr = threshold;
  8.     int newCap, newThr = 0;
  9.     // 如果老的数组长度大于0
  10.     // 开始计算扩容后的大小
  11.     if (oldCap > 0) {
  12.         // 超过最大值就不再扩充了，就只好随你碰撞去吧
  13.         if (oldCap >= MAXIMUM_CAPACITY) {
  14.             // 修改阈值为int的最大值
  15.             threshold = Integer.MAX_VALUE;
  16.             return oldTab;
  17.         }
  18.         /*
  19.         	没超过最大值，就扩充为原来的2倍
  20.         	1) (newCap = oldCap << 1) < MAXIMUM_CAPACITY 扩大到2倍之后容量要小于最大容量
  21.         	2）oldCap >= DEFAULT_INITIAL_CAPACITY 原数组长度大于等于数组初始化长度16
  22.         */
  23.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  24.                  oldCap >= DEFAULT_INITIAL_CAPACITY)
  25.             // 阈值扩大一倍
  26.             newThr = oldThr << 1; // double threshold
  27.     }
  28.     // 老阈值点大于0 直接赋值
  29.     else if (oldThr > 0) // 老阈值赋值给新的数组长度
  30.         newCap = oldThr;
  31.     else { // 直接使用默认值
  32.         newCap = DEFAULT_INITIAL_CAPACITY;//16
  33.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  34.     }
  35.     // 计算新的resize最大上限
  36.     if (newThr == 0) {
  37.         float ft = (float)newCap * loadFactor;
  38.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  39.                   (int)ft : Integer.MAX_VALUE);
  40.     }
  41.     // 新的阀值 默认原来是12 乘以2之后变为24
  42.     threshold = newThr;
  43.     // 创建新的哈希表
  44.     @SuppressWarnings({"rawtypes","unchecked"})
  45.     //newCap是新的数组长度--》32
  46.     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  47.     table = newTab;
  48.     // 判断旧数组是否等于空
  49.     if (oldTab != null) {
  50.         // 把每个bucket都移动到新的buckets中
  51.         // 遍历旧的哈希表的每个桶，重新计算桶里元素的新位置
  52.         for (int j = 0; j < oldCap; ++j) {
  53.             Node<K,V> e;
  54.             if ((e = oldTab[j]) != null) {
  55.                 // 原来的数据赋值为null 便于GC回收
  56.                 oldTab[j] = null;
  57.                 // 判断数组是否有下一个引用
  58.                 if (e.next == null)
  59.                     // 没有下一个引用，说明不是链表，当前桶上只有一个键值对，直接插入
  60.                     newTab[e.hash & (newCap - 1)] = e;
  61.                 //判断是否是红黑树
  62.                 else if (e instanceof TreeNode)
  63.                     // 说明是红黑树来处理冲突的，则调用相关方法把树分开
  64.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  65.                 else { // 采用链表处理冲突
  66.                     Node<K,V> loHead = null, loTail = null;
  67.                     Node<K,V> hiHead = null, hiTail = null;
  68.                     Node<K,V> next;
  69.                     // 通过上述讲解的原理来计算结点的新位置
  70.                     do {
  71.                         // 原索引
  72.                         next = e.next;
  73.                      	// 这里来判断如果等于true e这个结点在resize之后不需要移动位置
  74.                         if ((e.hash & oldCap) == 0) {
  75.                             if (loTail == null)
  76.                                 loHead = e;
  77.                             else
  78.                                 loTail.next = e;
  79.                             loTail = e;
  80.                         }
  81.                         // 原索引+oldCap
  82.                         else {
  83.                             if (hiTail == null)
  84.                                 hiHead = e;
  85.                             else
  86.                                 hiTail.next = e;
  87.                             hiTail = e;
  88.                         }
  89.                     } while ((e = next) != null);
  90.                     // 原索引放到bucket里
  91.                     if (loTail != null) {
  92.                         loTail.next = null;
  93.                         newTab[j] = loHead;
  94.                     }
  95.                     // 原索引+oldCap放到bucket里
  96.                     if (hiTail != null) {
  97.                         hiTail.next = null;
  98.                         newTab[j + oldCap] = hiHead;
  99.                     }
  100.                 }
  101.             }
  102.         }
  103.     }
  104.     return newTab;
  105. }

2.5、remove()

删除方法就是首先先找到元素的位置，如果是链表就遍历链表找到元素之后删除。如果是用红黑树就遍历树然后找到之后做删除，红黑树的节点个数小于 6 的时候要转换为链表。

删除 remove() 方法：

  1. // remove方法的具体实现在removeNode方法中，所以我们重点看下removeNode方法
  2. public V remove(Object key) {
  3.    Node<K,V> e;
  4.    return (e = removeNode(hash(key), key, null, false, true)) == null ?
  5.        null : e.value;
  6.  }

removeNode() 方法：

  1. final Node<K,V> removeNode(int hash, Object key, Object value,
  2.                            boolean matchValue, boolean movable) {
  3.     Node<K,V>[] tab; Node<K,V> p; int n, index;
  4. 	// 根据hash找到位置 
  5. 	// 如果当前key映射到的桶不为空
  6.     if ((tab = table) != null && (n = tab.length) > 0 &&
  7.         (p = tab[index = (n - 1) & hash]) != null) {
  8.         Node<K,V> node = null, e; K k; V v;
  9.         // 如果桶上的结点就是要找的key，则将node指向该结点
  10.         if (p.hash == hash &&
  11.             ((k = p.key) == key || (key != null && key.equals(k))))
  12.             node = p;
  13.         else if ((e = p.next) != null) {
  14.             // 说明结点存在下一个结点
  15.             if (p instanceof TreeNode)
  16.                 // 说明是以红黑树来处理的冲突，则获取红黑树要删除的结点
  17.                 node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
  18.             else {
  19.                 // 判断是否以链表方式处理hash冲突，是的话则通过遍历链表来寻找要删除的结点
  20.                 do {
  21.                     if (e.hash == hash &&
  22.                         ((k = e.key) == key ||
  23.                          (key != null && key.equals(k)))) {
  24.                         node = e;
  25.                         break;
  26.                     }
  27.                     p = e;
  28.                 } while ((e = e.next) != null);
  29.             }
  30.         }
  31.         // 比较找到的key的value和要删除的是否匹配
  32.         if (node != null && (!matchValue || (v = node.value) == value ||
  33.                              (value != null && value.equals(v)))) {
  34.             // 通过调用红黑树的方法来删除结点
  35.             if (node instanceof TreeNode)
  36.                 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
  37.             else if (node == p)
  38.                 // 链表删除
  39.                 tab[index] = node.next;
  40.             else
  41.                 p.next = node.next;
  42.             // 记录修改次数
  43.             ++modCount;
  44.             // 变动的数量
  45.             --size;
  46.             afterNodeRemoval(node);
  47.             return node;
  48.         }
  49.     }
  50.     return null;
  51. }

2.6、get()

查找方法，通过元素的 key 找到 value。

代码如下：

  1. public V get(Object key) {
  2.     Node<K,V> e;
  3.     return (e = getNode(hash(key), key)) == null ? null : e.value;
  4. }

get 方法主要调用的是 getNode 方法，代码如下：

  1. final Node<K,V> getNode(int hash, Object key) {
  2.     Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  3.     // 如果哈希表不为空并且key对应的桶上不为空
  4.     if ((tab = table) != null && (n = tab.length) > 0 &&
  5.         (first = tab[(n - 1) & hash]) != null) {
  6.         /* 
  7.         	判断数组元素是否相等
  8.         	根据索引的位置检查第一个元素
  9.         	注意：总是检查第一个元素
  10.         */
  11.         if (first.hash == hash && // always check first node
  12.             ((k = first.key) == key || (key != null && key.equals(k))))
  13.             return first;
  14.         // 如果不是第一个元素，判断是否有后续结点
  15.         if ((e = first.next) != null) {
  16.             // 判断是否是红黑树，是的话调用红黑树中的getTreeNode方法获取结点
  17.             if (first instanceof TreeNode)
  18.                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  19.             do {
  20.                 // 不是红黑树的话，那就是链表结构了，通过循环的方法判断链表中是否存在该key
  21.                 if (e.hash == hash &&
  22.                     ((k = e.key) == key || (key != null && key.equals(k))))
  23.                     return e;
  24.             } while ((e = e.next) != null);
  25.         }
  26.     }
  27.     return null;
  28. }

小结：

  1. get 方法实现的步骤：

a. 通过 hash 值获取该 key 映射到的桶
b. 桶上的 key 就是要查找的 key，则直接找到并返回
c. 桶上的 key 不是要找的 key，则查看后续的结点：

  1. 如果后续结点是红黑树结点，通过调用红黑树的方法根据 key 获取 value
  2. 如果后续结点是链表结点，则通过循环遍历链表根据 key 获取 value
  1. 上述红黑树结点调用的是 getTreeNode 方法通过树形结点的 find 方法进行查找：
  1. //	getTreeNode
  2.  final TreeNode<K,V> getTreeNode(int h, Object k) {
  3.       return ((parent != null) ? root() : this).find(h, k, null);
  4.  }
  5.  
  6.  //  find
  7. final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
  8.     TreeNode<K,V> p = this;
  9.     do {
  10.         int ph, dir; K pk;
  11.         TreeNode<K,V> pl = p.left, pr = p.right, q;
  12.         if ((ph = p.hash) > h)
  13.             p = pl;
  14.         else if (ph < h)
  15.             p = pr;
  16.         else if ((pk = p.key) == k || (k != null && k.equals(pk)))
  17.             return p; // 找到之后直接返回
  18.         else if (pl == null)
  19.             p = pr;
  20.         else if (pr == null)
  21.             p = pl;
  22.         else if ((kc != null ||
  23.                   (kc = comparableClassFor(k)) != null) &&
  24.                  (dir = compareComparables(kc, k, pk)) != 0)
  25.             p = (dir < 0) ? pl : pr;
  26.         // 递归查找
  27.         else if ((q = pr.find(h, k, kc)) != null)
  28.             return q;
  29.         else
  30.             p = pl;
  31.     } while (p != null);
  32.     return null;
  33. }
  1. 查找红黑树，由于之前添加时已经保证这个树是有序的了，因此查找时基本就是折半查找，效率更高。
  2. 这里和插入时一样，如果对比结点的哈希值和要查找的哈希值相等，就会判断key是否相等，相等就直接返回。不相等就从子树中递归查找。
  3. 若为红黑树，则在树中通过key.equals(k)查找，O(logn)。若为链表，则在链表中通过key.equals(k)查找，O(n)。

2.7、遍历HashMap集合的几种方式

  1. 分别遍历 Key 和 Values
  1. for (String key : map.keySet()) {
  2. 	System.out.println(key);
  3. }
  4. for (Object vlaue : map.values() {
  5. 	System.out.println(value);
  6. }
  1. 使用 Iterator 迭代器迭代
  1. Iterator<Map.Entry<String, Object>> iterator = map.entrySet().iterator();
  2. while (iterator.hasNext()) {
  3.     Map.Entry<String, Object> mapEntry = iterator.next();
  4.     System.out.println(mapEntry.getKey() + "---" + mapEntry.getValue());
  5. }
  1. 通过 get 方式（不建议使用）
  1. Set<String> keySet = map.keySet();
  2. for (String str : keySet) {
  3. 	System.out.println(str + "---" + map.get(str));
  4. }

说明：

根据阿里开发手册，不建议使用这种方式，因为迭代两次。keySet 获取 Iterator一次，还有通过 get 又迭代一次，降低性能。

  1. jdk8 以后使用 Map 接口中的默认方法
  1. default void forEach(BiConsumer<? super K,? super V> action) 
  2. // BiConsumer接口中的方法：
  3. 	void accept​(T t, U u) 对给定的参数执行此操作。  
  4. 		参数 
  5.             t - 第一个输入参数 
  6.             u - 第二个输入参数

遍历的代码：

  1. HashMap<String,String> map = new HashMap();
  2. map.put("001", "zhangsan");
  3. map.put("002", "lisi");
  4. map.forEach((key, value) -> {
  5.     System.out.println(key + "---" + value);
  6. });

3、设计 HashMap 的初始化容量

3.1、问题描述

如果我们确切的知道我们有多少键值对需要存储，那么我们在初始化 HashMap 的时候就应该指定它的容量，以防止 HashMap 自动扩容而导致 hash 表重建，进而严重影响使用效率。

默认情况下 HashMap 的容量是 16，但是，如果用户通过构造函数指定了一个数字作为容量，那么 Hash 会选择大于该数字的第一个 2 的幂作为容量（3->4、7->8、9->16）。这点我们在上述已经进行过讲解。

3.2、我们应该如何设计HashMap 的初始化容量？

《阿里巴巴Java开发手册》原文：

关于设置 HashMap 的初始化容量：

我们上面介绍过，HashMap 的扩容机制，就是当达到扩容条件时会进行扩容。HashMap 的扩容条件就是当 HashMap 中的元素个数（size）超过临界值（threshold）时就会自动扩容。所以，如果我们没有设置初始容量大小，随着元素的不断增加，HashMap 会有可能发生多次扩容，而 HashMap 中的扩容机制决定了每次扩容都需要重建 hash 表，是非常影响性能的。

但是设置初始化容量，设置的数值不同也会影响性能，那么当我们已知 HashMap 中即将存放的 KV 个数的时候，容量设置成多少为好呢？

关于设置 HashMap 的初始化容量大小：

可以认为，当我们明确知道 HashMap 中元素的个数的时候，把默认容量设置成 initialCapacity/ 0.75F + 1.0F 是一个在性能上相对好的选择，但是，同时也会牺牲些内存。

而 Jdk 并不会直接拿用户传进来的数字当做默认容量，而是会进行一番运算，最终得到一个 2 的幂。

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/weixin_56727438/article/details/123472639

内容来源于网络，如有侵权，请联系作者删除！

Java开发语言散列表jdk源码

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com