怎么做网站的代理商,济南比较好的网站建设公司,营销型网站建设合同,网站建设岗位工作职责JDK 1.8 对 HashMap 进行了一些优化#xff0c;主要包括以下几个方面的改进#xff1a; 红黑树#xff1a;在 JDK 1.8 中#xff0c;当哈希碰撞#xff08;多个键映射到同一个桶#xff09;达到一定程度时#xff0c;HashMap 会将链表转化为红黑树#xff0c;以提高查找…JDK 1.8 对 HashMap 进行了一些优化主要包括以下几个方面的改进 红黑树在 JDK 1.8 中当哈希碰撞多个键映射到同一个桶达到一定程度时HashMap 会将链表转化为红黑树以提高查找、插入和删除操作的性能。这个改进在处理大规模数据时特别有用因为红黑树的复杂度为 O(log n)。 桶的树化和解树化HashMap 在桶的树化和解树化过程中进行了优化以提高性能。桶的树化指的是当链表长度达到一定阈值时将链表转换为红黑树而桶的解树化指的是当红黑树的节点数小于一定阈值时将红黑树恢复成链表。这些优化可以减少树化和解树化的开销。 负载因子在 JDK 1.8 中负载因子默认值变为 0.75。负载因子表示在什么情况下 HashMap 应该进行扩容这个值的选择可以影响性能和空间利用率。0.75 是一个折衷的选择可以降低哈希冲突的可能性同时也不会浪费太多内存。 扩容机制JDK 1.8 中对 HashMap 的扩容机制进行了优化。在1.8之前扩容时会将每个元素都进行重新Hash再放入到新的桶中。1.8之后是怎么做的呢
首先我们需要明确HashMap中的Table是什么。 在HashMap源码中 /*** 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.)*/transient NodeK,V[] table;
table就是一个数组每一个元素相当于一个桶我们通过Node可以遍历出桶中的所有元素。
继续看看HashMap的源码 先找到put方法 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) {NodeK,V[] tab; NodeK,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 {NodeK,V e; K k;if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;else if (p instanceof TreeNode)e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount 0; ; binCount) {if ((e p.next) null) {p.next newNode(hash, key, value, null);if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}if (e ! null) { // existing mapping for keyV oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);return oldValue;}}modCount;if (size threshold)resize();afterNodeInsertion(evict);return null;}在n (tab resize()).length;表示每一次put都要就行扩容操作。 源码中对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.
Returns:
the table
初始化或加倍表大小。
如果为空则根据字段阈值中保持的初始容量目标进行分配。
否则因为我们使用的是二次幂展开所以每个bin中的元素必须保持在同一索引处或者在新表中以二次幂偏移量移动。当我们的HashMap不为空时我们就需要判断是否要进行扩容。 那么什么时候需要扩容呢 在HashMap中定义了一个值threshold 原文注释The next size value at which to resize (capacity * load factor).即现在的容量乘上负载因子默认0.75时扩容。 超过阀值一定扩容吗 if (oldCap MAXIMUM_CAPACITY) {threshold Integer.MAX_VALUE;return oldTab;}可以指导如果原先的容量已经是大于等于最大容量了则HahMap不可以再扩阀值threshold也变为 了小大整数不可以被超越。 如何扩容 当满足所有条件后终于可以扩容了。
newThr oldThr 1; // double threshold将新的阀值扩展为原先的两倍。在之后的代码中再将threshold更改为newThr即可。 在此之前都是对数值的修改从这之后才是正式的扩容操作 首先创建出新的table NodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab;当然再次之前老table的值已经保存在了oldTab中 NodeK,V[] oldTab table;之后是将oldTab数据转移到table的操作 当oldTab不为空则遍历oldTab
for (int j 0; j oldCap; j) {NodeK,V e; // 从旧哈希表中获取当前索引位置的节点if ((e oldTab[j]) ! null) { // 如果节点不为空oldTab[j] null; // 将旧哈希表中当前索引位置置为空便于垃圾回收// 如果节点没有下一个节点将其直接放入新哈希表if (e.next null)//最后一个节点newTab[e.hash (newCap - 1)] e;//目的是为将e散列减少hash冲突从而减少计算// 如果节点属于树节点红黑树节点调用split方法进行处理else if (e instanceof TreeNode)((TreeNodeK,V)e).split(this, newTab, j, oldCap);else { // 保持节点顺序NodeK,V loHead null, loTail null; // 低位链表的头和尾NodeK,V hiHead null, hiTail null; // 高位链表的头和尾NodeK,V next;do {next e.next;// 根据节点的哈希值与旧容量的与运算结果将节点分到低位或高位链表if ((e.hash oldCap) 0) {if (loTail null)loHead e;elseloTail.next e;loTail e;}else {if (hiTail null)hiHead e;elsehiTail.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;}}}
}
接下来我们对可能对可能发生的三种情况进行说明 e.next null时可以看到只有一步操作: newTab[e.hash (newCap - 1)] e;将e的值通过e的哈希值与新容量的与操作从而得到e在新table中的位置这个目的是为了让值更加的零散、而不是保持在原来的位置。由于值的数量是增多的如果还是继续保留在原来的位置那么哈希碰撞是难以避免的e instanceof TreeNode时表示这个桶是TreeNode类型的是一个红黑链表红黑数组的特性在我的博客中也有提到红黑树与B树红黑树split拆分操作的目的是防止红黑树变得过深要把一颗红黑树拆成两棵并继续分散塞到新Table中去。else中则表示这个节点是链表节点和红黑树的split类似这个操作也是为了链表过深从而拆成了lo和hi两段。
并发性能JDK 1.8 通过引入分段锁Segment来提高 HashMap 在多线程环境下的并发性能。每个 Segment 就是一个独立的 HashMap只锁定其中一个 Segment 而不是整个 HashMap这减少了锁的争用提高了并发性能。
这些优化使得 JDK 1.8 中的 HashMap 在处理大规模数据和多线程环境下表现更好同时也减少了哈希碰撞的影响提高了性能和稳定性。然而需要注意的是具体的实现可能因不同的 JDK 版本而有所不同因此在选择和使用 HashMap 时需要考虑 JDK 版本的影响。
