哈希表

哈希表是一种键值映射的数据结构。哈希表中，数据以数组格局存储，其中每个数据值都有本人惟一的索引值，索引值通过哈希表的哈希函数计算失去。

上面两步将键哈希值转化成哈希表的索引值。

  • 哈希值 = 哈希函数（键）
  • 索引值 = 哈希值 % 哈希表长度

抵触解决办法

无限长度下的哈希表，抵触不可避免。解决抵触的两种办法，拉链法和凋谢寻址。

拉链法

将抵触地位的元素结构成链表。增加数据发生冲突时，将元素追加到链表。如下图，当增加 "Sandra Dee"时，计算出索引值为152与“John Smith” 发生冲突，而后将它追加到链表。

凋谢寻址

以以后抵触地位为终点，依照肯定规定探测空地位把元素插进去。比较简单的形式是线性探测，它会依照固定的距离（通常是1）循环进行查找。

如下图，“Sandra Dee”增加时与 “John Smith” 相冲突，通过探测空地位插入到153，而后增加“Ted Baker”发现与“Sandra Dee”相冲突，往后探测154空地位插入。

性能

负载因子

负载因子的值是条目数占用哈希桶比例，当负载因子超过现实值时，哈希表会进行扩容。比方哈希表现实值 0.75，初始容量 16，当条目超过 12 后哈希表会进行扩容从新哈希。0.6 和 0.75 是通常正当的负载因子。

$${\displaystyle loadfactor\ (\alpha )={\frac {n}{k}}}$$

  • $n$ 哈希表中的条目数。
  • $k$ 桶的数量。

影响哈希表性能的两个次要因素

  • 缓存失落。随着负载因子的减少缓存失落数量回升，而搜寻和插入性能会因而大幅降落。
  • 扩容从新哈希。调整大小是一项极其耗时的工作。设置适合的负载因子能够管制扩容次数。

下图展现了随着负载因子减少，缓存失落的数量开始回升，0.8后开始迅速攀升。

HashMap

对于 HashMap 解读一下它的 hash 办法和抵触树化两个中央。

对于hash()

取key的hashCode值，而后将高16位与低16位进行异或、最初取模运算。

static final int hash(Object key) {   //jdk1.8 & jdk1.7     int h;     // h = key.hashCode()  取hashCode值     // h ^ (h >>> 16)      将高16位与低16位进行异或     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}// jdk1.7static int indexFor(int h, int length) {      return h & (length-1);}// jdk1.8(n - 1) & hash

高16位与低16位进行异或是为了加大低位的随机性。

对于随机性，网上有个测试例子：他随机选取了352个字符串，测试不同长度数组下的碰撞概率。

结果显示，当HashMap数组长度为 2^9 = 512 的时候，间接取hashCode抵触103次，进行高下异或后抵触92次。

https://www.todaysoftmag.com/...

抵触树化

HashMap解决抵触应用拉链法。jdk1.8 中，当一个桶链表节点超过TREEIFY_THRESHOLD=8后，链表会转换为红黑树，当桶中节点移除或从新哈希少于 UNTREEIFY_THRESHOLD=6时，红黑树会转变为一般的链表。

链表取元素是从头结点始终遍历到对应的结点，工夫复杂度是O(N) ，红黑树基于二叉树构造，工夫复杂度为O(logN) ，所以当元素个数过多时，用红黑树存储能够进步搜寻的效率。然而单个树节点须要占用的空间大概是一般节点的两倍，所以应用树和链表是时空衡量的后果。

树化阀值为什么是 8 ？

HashMap 文档有这么一段形容。大体意思是，哈希桶上的链表节点数量出现泊松散布。

Ideally, under random hashCodes, the frequency of* nodes in bins follows a Poisson distribution* (http://en.wikipedia.org/wiki/Poisson_distribution) with a* parameter of about 0.5 on average for the default resizing* threshold of 0.75, although with a large variance because of* resizing granularity. Ignoring variance, the expected* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /* factorial(k)). The first values are:** 0:    0.60653066* 1:    0.30326533* 2:    0.07581633* 3:    0.01263606* 4:    0.00157952* 5:    0.00015795* 6:    0.00001316* 7:    0.00000094* 8:    0.00000006* more: less than 1 in ten million

什么是泊松散布？

泊松散布就是形容某段时间内，事件具体的产生概率。柏松散布能够通过平均数估算出某个事件的呈现概率。

$$P(N(t) = n) = \frac{(\lambda t)^n e^{-\lambda t}}{n!}$$

  • $P$ 概率；
  • $N$ 某种函数关系；
  • $t$ 工夫；
  • $n$ 呈现的数量；

比方，一个程序员每天均匀写3个Bug，示意为\( P(N(1) = 3) \)。由此还能够失去上面：

他今天写1个Bug的概率：0.1493612051
他今天写2个Bug的概率：0.2240418077
他今天写3个Bug的概率：0.2240418077
他今天写10个Bug的概率：0.0008101512
/*** @param n 节点数量* @param r 均匀数量*/public static String poisson(int n, double r) {    double value = Math.exp(-r) * Math.pow(r, n) / IntMath.factorial(n);    return new BigDecimal(value).setScale(10, ROUND_HALF_UP).toPlainString();}

假如HashMap有 \( n \) 条数据，负载因子为 \( k \) ，那么HashMap长度最小值为 \( \frac{n}{k} \) ，最大约为 \( \frac{2n}{k} \) （容量必须是 2 的幂） 所以平均值是 \( \frac{3n}{2k} \)，每个桶的均匀节点数量为

$$n \div（\frac{3n}{2k}）= \frac{2k}{3} = \frac{2\times 0.75}{3} = 0.5$$

HashMap 默认负载因子为 0.75，所以每个桶的均匀节点数量 0.5，代入柏松公式失去上面数据

1个桶中呈现1个节点的概率:0.30326532991个桶中呈现2个节点的概率:0.07581633251个桶中呈现3个节点的概率:0.01263605541个桶中呈现4个节点的概率:0.00157950691个桶中呈现5个节点的概率:0.00015795071个桶中呈现6个节点的概率:0.00001316261个桶中呈现7个节点的概率:0.00000094021个桶中呈现8个节点的概率:0.0000000588

树化是哈希极度蹩脚下不得已而为之的做法，而一个桶呈现 8 个节点的概率不到千万分之一，所以将TREEIFY_THRESHOLD=8 。

小结

哈希表是一种键值映射的数据结构。解决抵触有两种办法拉链法和凋谢寻址。正当设置负载因子和初始容量防止过多的扩容操作和缓存失落。 了解HashMap的 hash 办法和抵触树化。