由阿里巴巴Java开发规约HashMap条目引发的故事

  • 时间:
  • 浏览:0
  • 来源:彩神快三手机版

hashSeed 默认值是0,也许多许多我默认关闭,任何数字与0异或不变。hashSeed 会在capacity处于变化的曾经,通过initHashSeedAsNeeded()函数进行计算。当capacity大于设置值Holder.ALTERNATIVE_HASHING_THRESHOLD后,会通过sun.misc.Hashing.randomHashSeed产生hashSeed 值,这俩设定值是通过 JVM的jdk.map.althashing.threshold参数来设置的,具体代码如下:

有哪些?这俩要通过插件监测?没必要吧,哪个开发谁能谁能告诉我默认大小,何时能 resize 啊,而且我和孤尽打赌随机咨询几位同学以下2个问题:

通过对比翻看源码,先说下结论:

具体代码如下:

《阿里巴巴Java开发规约》自诞生以来,另另俩个劲处于挑战漩涡的最中心,从这有另另俩个规约的小条目,看出来规约也是冰冻三尺,非一日之寒,研读规约,随便说说并能发现许多许多看似简单的知识点身前,随便说说隐藏着非常深的逻辑知识点。

【推荐】集合初始化时,指定集合初始值大小。

说明:HashMap使用如下构造法律土最好的办法进行初始化,将会暂时无法取舍集合大小,不到指定默认值(16)即可:

按照函数注释,将会bucket数组大小是2的幂,计算下标index = (table.length - 1) & hash ,将会不做 hash 除理,大概散列生效的不到2个低 bit 位,为了减少散列的碰撞,设计者综合考虑了带宽、作用、质量曾经,使用高16bit和低16bit异或来简单除理减少碰撞,而且 JDK8中用了繁杂度 O(logn)的树特征来提升碰撞下的性能。具体性能提升可不并能参考Java 8:HashMap的性能提升

Retrieve object hash code and applies a supplemental hash function to the result hash, which defends against poor quality hash functions. This is critical because HashMap uses power-of-two length hash tables, that otherwise encounter collisions for hashCodes that do not differ in lower bits. Note: Null keys always map to hash 0, thus index 0.

具体hash 代码如下所示:

数组下标计算: index = (table.length - 1) & hash ,将会 table.length 也许多许多我capacity 肯定是2的N次方,使用 & 位运算由于 许多许多我多了最高位,曾经就不不重新计算 index,元素要么在原位置,要么在原位置+ oldCapacity。

resize()用来第一次初始化,将会 put 曾经数据超过了threshold后扩容,resize的注释如下:

将会增加的高位为1,resize 后 index 增加 oldCap,如图所示:

JDK7 中的 HashMap 还是采用另一个人 所熟悉的数组+链表的特征来存储数据。

JDK8中 HashMap 的bucket数组大小肯定是2的幂,对于2的幂大小的 bucket,计算下标只前要 hash 后按位与 n-1,比%模运算取余要快。将会你通过 HashMap(int initialCapacity) 构造器传入initialCapacity,会先计算出比initialCapacity大的 2的幂存入 threshold,在第一次 put 的 resize() 初始化中会按照这俩2的幂初始化数组大小,此后 resize 扩容也一定会 每次乘2,不到设计的由于 底下会详细讲。

抽样调查的结果出乎我的意料:

JKD7 中,bucket数组下标也是按位与计算,而且 hash 函数与 JDK8稍有不同,代码注释如下:

JDK7 里 HashMap的bucket数组许多许多我会在new 的曾经分配,也是在第一次 put 的曾经通过 inflateTable() 函数进行分配。

将会增加的高位为0,resize 后 index 不变,如图所示:

JKD7 的put相比于 JDK8就要简单许多,碰撞曾经不到链表特征。具体代码如下:

相对于 JDK7的100余行代码,JDK8代码量达到了100余行,对于这俩另一个人 最常用的数据特征增加了不少的性能优化。

仔细看一遍底下的分析和源码,对 HashMap 内部的细节又多了些了解,有空的曾经还是多翻翻源码,^_^

JDK8 中的 HashMap 采用了数组+链表或树的特征来存储数据。

JDK7中 HashMap 的bucket数组大小也一定是2的幂,同样有计算下标简便的优点。将会你通过 HashMap(int initialCapacity) 构造器传入initialCapacity,会先存入 threshold,在第一次 put 时调用 inflateTable() 初始化,会计算出比initialCapacity大的2的幂作为初始化数组的大小,此后 resize 扩容也一定会 每次乘2。

看一遍代码规约这俩条的曾经,我随便说说是一定会 有点儿太 low 了,身为开发,另一个人 都知道 HashMap 的原理。

将会 h>>>16,高16bit 补0,有另另俩个数和0异或不变,许多许多 hash 函数大概的作用许多许多我:高16bit不变,低16bit和高16bit做了有另另俩个异或,目的是减少碰撞。

HashMap 的bucket数组并不什么都这样new 的曾经分配,许多许多我在第一次 put 的曾经通过 resize() 函数进行分配。

大热的《阿里巴巴Java开发规约》中含提到:

Initial capacity 决定 bucket 的大小,Load factor 决定 bucket 内数据填充比例,基于这有另另俩个参数的乘积,HashMap 内部由 threshold 这俩变量来表示 HashMap 能倒入的元素个数。

JDK7的 resize() 也是扩容两倍,不过扩容过程相对JDK8就要简单许多,将会默认initHashSeedAsNeeded内开关一定会 关闭情况表,许多许多一般情况表下transfer 不前要进行 rehash,能减少一帕累托图开销。代码如下所示:

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.

HashMap 是写代码时最常用的集合类之一,看来另一个人 也一定会 许多许多许多许多很了解。孤尽乘胜追击又抛出问题:JDK8中 HashMap 和曾经 HashMap 有有哪些不同?

HashMap中含有另另俩个重要的参数,容量(Capacity) 和 负载因子(Load factor)

以上参数在 JDK7 和 JDK8中是一致的,接下来会根据实际代码分析。

put函数的思路大致分以下几步:

我知道 JDK8 中 HashMap 引入了红黑树来除理哈希碰撞,具体细节和源代码并不到仔细翻过,看来是曾经对比翻看下 JDK8 和 JDK7 的 HashMap 源码了。

这俩设计的巧妙之处于于,节省了一帕累托图重新计算hash的时间,同去新增的一位为0或1的概率可不并能认为是均等的,许多许多在resize 的过程中就将曾经碰撞的节点又均匀分布到了有另另俩个bucket里。

JKD8 中put 和 get 时,对 key 的 hashCode 先用 hash 函数散列下,再计算下标:

具体 hash 代码如下: