共计 3087 个字符，预计需要花费 8 分钟才能阅读完成。
哈希表
哈希表是一种键值映射的数据结构。哈希表中，数据以数组格局存储，其中每个数据值都有本人惟一的索引值，索引值通过哈希表的哈希函数计算失去。
上面两步将键哈希值转化成哈希表的索引值。
- 哈希值 = 哈希函数（键）
- 索引值 = 哈希值 % 哈希表长度
抵触解决办法
无限长度下的哈希表，抵触不可避免。解决抵触的两种办法，拉链法 和凋谢寻址。
拉链法
将抵触地位的元素结构成链表。增加数据发生冲突时，将元素追加到链表。如下图，当增加 “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.7
static 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.3032653299 1 个桶中呈现 2 个节点的概率:0.0758163325 1 个桶中呈现 3 个节点的概率:0.0126360554 1 个桶中呈现 4 个节点的概率:0.0015795069 1 个桶中呈现 5 个节点的概率:0.0001579507 1 个桶中呈现 6 个节点的概率:0.0000131626 1 个桶中呈现 7 个节点的概率:0.0000009402 1 个桶中呈现 8 个节点的概率:0.0000000588
树化 是哈希极度蹩脚下不得已而为之的做法，而一个桶呈现 8 个节点的概率不到千万分之一，所以将 TREEIFY_THRESHOLD=8。
小结
哈希表是一种键值映射的数据结构。解决抵触有两种办法 拉链法 和凋谢寻址。正当设置负载因子和初始容量防止过多的扩容操作和缓存失落。了解 HashMap 的 hash 办法和抵触树化。