HashMap 学习笔记

HashMap是 Java 开发中常用的一种数据接口，常用于完成key:value结构的存储。而同时，HashMap又是HashSet、HashTable、ConcurrentHashMap这三种数据结构的基础。

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用NULL 值和 NULL 键。(除了非同步和允许使用 NULL 之外，HashMap 类与 Hashtable 大致相同。)
此类不保证映射的顺序，特别是它不保证该顺序恒久不变。此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作(get 和 put)提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的"容量"(桶的数量)及其大小(键-值映射关系数)成比例。
所以，如果迭代性能很重要，则不要将初始容量设置得太高(或将加载因子设置得太低)。

基本结构

HashMap 的基本结构是一个可以扩容的动态数组。该动态数组有着以下属性：

属性值	默认值	属性说明
capacity	$16$	目前数组的长度。为了实现高效的扩容，其值为 $2$ 的幂次方
loadFactor	$0.75$	负载因子，该值与`threshold`配合控制扩容
threshold	$capacity \times loadfactor$	扩容的阈值，即当数组内达到这么多元素时，会触发数组的扩容

数组元素

哈希表看作一个可扩容动态数组，而数组中的每个元素是一个Node，它的属性有：

元素名称	意义
hash	当前位置值的 hash 值
key	当前位置的键
value	当前位置存储的值
next	下一个 Node

链表与树

对于每个 Node 元素，我们发现它有一个next属性。而通过它，挂载到数组同一个位置的多个 Node 就组成了链表或者树。

在JAVA1.7阶段，不使用红黑树解决哈希冲突，即发生冲突的多个 Node 构成了一个单向链表(拉链法解决哈希冲突)

而在JAVA 1.8中，当单项链表中元素大于等于 $8$ 时，单项列表会变为一棵红黑树，链表的查找时间复杂度为 $O(N)$ ，而红黑树查找的时间复杂度为 $O(logN)$ 。因此，在数组的同一位置挂载的节点较多时，JAVA 1.8的设计会降低时间复杂度。

该转化操作是由以下函数实现的

1	final void treeifyBin(Node<K,V>[] tab, int hash)

官方对于红黑树与链表之间转化的说明，翻译自 JDK 官方文档
因为 TreeNode(红黑树)的大小约为链表节点的两倍，所以我们只有在一个拉链已经拉了足够节点的时候才会转为 tree(参考TREEIFY_THRESHOLD)。并且，当这个 hash 桶的节点因为移除或者扩容后 resize 数量变小的时候，我们会将树再转为拉链。如果一个用户的数据的 hashcode 值分布得很均匀的话，就会很少使用到红黑树。
理想情况下，我们使用随机的 hashcode 值，加载因子为 $0.75$ 情况，尽管由于粒度调整会产生较大的方差，节点的分布频率仍然会服从参数为 $0.5$ 的泊松分布。链表的长度为 8 发生的概率仅有 $0.00000006$

泊松分布，是一种统计与概率学里常见到的离散概率分布，由法国数学家西莫恩·德尼·泊松在 1838 年时提出。它会对随机事件的发生次数进行建模，适用于涉及计算在给定的时间段、距离、面积等范围内发生随机事件的次数的应用情形(来自维基百科)
泊松分布公式如下，P 表示概率，N表示某种函数关系，t 表示时间，n 表示数量。
$P(N(t)=n)= \frac{(\lambda t)^ne^{-\lambda t}}{n!}$

关于 LoadFactor 默认值 0.75 的说明

参考链接：
HashMap 的负载因子为什么是 0.75 - segmentfault

由于哈希表的物理结构限制，存在以下的问题:

数组的容量过小，更容易出现哈希冲突
数组的容量过大，空间利用率不高

为了解决以上提出的两个问题，我们引入了loadFactor来控制 hash 表的扩容操作

但是同样的，loadFactor也有相对的值大小问题

loadFactor越小，填满所需的数据就越少，哈希冲突的几率减少，但浪费了空间，而且还会提高扩容的触发几率，扩容相对于哈希表其他操作来说极度消耗系统性能。
loadFactor越大，填满所需的数据就越多，空间利用率提高，但发生哈希冲突的几率就变大了。

这就必须在"哈希冲突"与"空间利用率"两者之间有所取舍，尽量保持平衡

数学证明如下

前提：hash 值计算服从二项分布

假设插入数据没有倾向性，为全随机数据，则插入时数据的概率分布服从二项分布，具体理由如下：

实验的结果只有两种状态
向 hash 表内添加数据只有冲突与不冲突两种情况
每次进行 hash 值计算的时候概率相互独立
插入 hashmap 的 hash 值是随机的，并且他们经过 hash 运算都会映射到 hash 表的长度的地址空间上，那么这个结果也是随机的。所以，每次 put 的时候的概率是相互独立的
每次执行 hash 计算，成功的概率都是一样的
对于一组完全无序的数据，执行完 hash 值函数，hash 值发生冲突的理论概率是相等的

则根据二项分布的定义，可以认定在数据随机的情况下，可以认为 hash 值的分布是一个二项分布

对于一次元素插入，一般意义上我们需要追求插入发生哈希碰撞的概率尽可能的低

n 次事件里面，碰撞为 0 的概率，由二项分布公式得：

$\begin{aligned} binom(n,0) & = C_n^0 \times (\frac{1}{s})^0 \times (1 - \frac{1}{s})^{n - 0} = (1 - \frac{1}{s})^n & \end{aligned}$

这个概率值需要大于 0.5，我们认为这样的 hashmap 可以提供很低的碰撞率。所以： $(1 - \frac{1}{s})^n \ge \frac{1}{2}$

这时候，我们对于该式需求：当长度为 s 的时候，n 为多少次就应该进行扩容了？

又因为 $LoadFactor=n/s$ ，所以推导如下：

$\begin{aligned} n\ln(1 - \frac{1}{s}) & \ge -\ln2 \\ n & \le \frac{-\ln2}{\ln(1 - \frac{1}{s})} \rightarrow n \le \frac{\ln2}{\ln\frac{s}{s-1}} \\ \frac{n}{s} & \le \frac{\ln2}{s\ln\frac{s}{s-1}} \end{aligned}$

所以可以得到

$\begin{aligned} loadfactor & = \lim_{s \to \infty}\frac{\ln2}{s\ln\frac{s}{s-1}} \end{aligned}$ ,其中有 $\begin{aligned} \lim_{s \to \infty}s\ln\frac{s}{s-1} \end{aligned}$

即问题转换为求 $\infty \cdot 0$ 函数极限问题，令 $s = m+1(m \to \infty)$ ,则转化为

$\begin{aligned} \lim_{m \to \infty}(m+1)\ln(1+\frac{1}{m}) \end{aligned}$

再令 $x = \frac{1}{m} (x \to 0)$ ，则有:

$\begin{aligned} \lim_{s \to \infty}s\ln\frac{s}{s-1} & = \lim_{x \to 0}(\frac{1}{x}+1)\ln(1+x) \\ &= \lim_{x \to 0} (\frac{1}{x}+1) x \\&=\ln(1 + x) \sim x \\ &= \lim_{x \to 0}(1+x) \ \sim 1 \end{aligned}$

所以，最佳理论加载因子的值为:

$\begin{aligned} loadfactor & = \lim_{s \to \infty}\frac{\ln2}{s\ln\frac{s}{s-1}} \sim \ln2 \\ & \sim 0.693 \end{aligned}$

考虑到 HashMap 的容量有一个要求：它必须是 $2$ 的 $n$ 次幂。当加载因子选择了 $0.75$ 就可以保证它与容量的乘积为整数。

1 2	160.75=12 320.75=24

除了 $0.75$ 以外， $0.5\sim 1$ 之间且向 $0.693$ 靠近的，满足条件的数还有 $0.625(5/8)$ 、 $0.875(7/8)$ 可选，从中位数的角度，挑 $0.75$ 比较完美。

另外，根据维基百科上数学证明，拉链法的加载因子最好限制在 $0.7 \sim 0.8$ 以下，因为加载因子一旦超过 $0.8$ ，查表时的 CPU 缓存不命中(cache missing)会按照指数曲线上升。

综上， $0.75$ 是个比较完美的选择。