Author 2020-03-18
PDF
基本实现1阅读笔记：HashMap刨根问底探索分析Contents基本实现 ............................................................................................... 1哈希映射负载因子和（阈值）树化（红黑树） ....................................................................................... 3（树化阈值）（树化）尾插入fail-fast机制 .......................................................................................... 4性能分析 ............................................................................................... 4可以算是最常用的数据结构了，而它的实现没想到还挺有学问在里面。基本实现哈希映射在中使用数组来存储元素，根据元素的值一一映射到一个节点上。其中使用的哈希方法为：static final int hash(Object key) { int h; // 将哈希值无符号右移16位是因为取index使用了length作为掩码，这样当哈希值在掩码外的部分相同的时候就会发生冲突 // 这样将高位混杂到低位上，可以尽可能将这种影响消除 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}举例来说对于容量为的，插入、、、后在数组中的分布就是："a".hashCode() = 97 = 00000000000000000000000001100001hash("a") = 00000000000000000000000001100001 ^ 00000000000000000000000000000000 = 00000000000000000000000001100001index = hash("a") & (4 - 1) = 00000000000000000000000001100001 & 00000000000000000000000000000011 = 00000000000000000000000000000001如此则数组中对应的序号为，，，。 基本实现2Load Factor(负载因子)和Threshod（阈值）因为的底层实际上是使用数组进行存储，那么始终存在着一个动态内存分配的问题：数组的大小是固定的，但是实际存储多少数据是未知的（可以一直向中进行插入），那么当数组塞满了（实际上还有一个问题是发生哈希冲突）之后如何处理？解决这个问题最简单的做法就是，一旦数组满了之后，就对数组进行扩容。扩容也很简单，重新申请一个大一点的数组，再把原来数组里面的数据复制过去即可。这里涉及到另外一个问题就是，扩容的时候选择一个怎么样的容量进行扩容呢？这个操作是有代价的，如果频繁的扩容就涉及到频繁的数组复制操作，性能上会受到影响；如果一次扩容选择一个很大的空间，但实际之后这些空间又没有使用到，那么久造成了资源浪费。怎么解决这一个问题呢？在的构造中有两个关键的参数：initialCapacity初始化容量，即可以装多少条数据loadFactor：负载因子，用来描述中可以变得多满（到达什么程度开始扩容）实际上，并不会根据你提供的initial capacity来初始化一个数组，而是找到一个值并满足（比如对应得到，对应得到），并在第一次插入的时候进行初始化。为什么数组在初始化的时候一定是的倍数？这是因为方便扩容的时候直接将数组大小变成原来的二倍，同时也简化了一些其他的操作，比如如何定位到一个值所在的索引int index = (length - 1) & hash/*final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { ...*/ 树化（红黑树）3正常的做法是，abs(hash) % SIZE像这样取余操作。但是如果除数是的次幂，则可以简化为位运算操作。而至于为什么默认的负载因子是，有人根据二项式分布算出最佳的是，然后拍脑袋给出的（乘以容量还可以得个整数。树化（红黑树）TREEIFY_THRESHOLD（树化阈值）所以使用作为负载因子，那么出现的情况是如果当前容量达到这个值的时候就会到原来的两倍。对于一个容量为的来说，理想情况下元素均匀分布，是这样：最好情况 极端情况bucket | elements bucket | elements -------+--------- -------+--------- 0 | Z 0 | 1 | X 1 | Z -> X -> Y 2 | 2 | 3 | Y 3 | 理想状况下（假设基于随机算法节点在桶中均匀分布，且节点的个数占桶的，那么单个节点出现在桶中的概率为），节点在桶中的出现的频率遵循泊松分布（意味着在的情况下，桶中出现个节点（冲突）的概率大致为：* 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可见哈希冲突导致一个桶中出现个节点情况已经几乎小之又小的事情了，这是TREEIFY_THRESHOLD = 8的原因，当大于的时候转换为红黑树。Treeify（树化）通常情况下，当哈希冲突产生的时候，会被当成链表存储。这个改变是通过引入的。在下面的情况下，会转换为红黑树：链表中的节点数达到（）容量至少达到（），否则只是单纯扩容到到原来的两倍 性能分析4现实中哈希冲突的场景并不多，不过如果非要测试这种场景也很容易。比如Aa和字符串BB就拥有相同的哈希值，把他们随机组合到一起，还是一样。于是我们构建了很多个哈希值相同的值，来演示哈希冲突的场景：尾插入从上面的图可以注意到：哈希冲突的节点在链表中是插入到链表尾部的在之前是插入到前面的，但是改成插入到尾部了，这样做的原因（据说）是因为扩容时会改变链表的顺序，在多线程条件下会导致形成闭环（从而可能引起死循环）。fail-fast机制在中存在一个变量记录修改的次数modCount当这个次数和期待的不一致的时候就会抛出ConcurrentModificationException。这种机制被称之为，意味着出现错误的时候尽早结束。通常在java.util下面的迭代器都是这类的，如果在迭代的中途数据被其他线程修改了，那么就会（尽可能的，当然并不能保证）触发这个检测。而java.util.concurrent包下的迭代器是的，例如、等。性能分析对于get和put操作的复杂度是常数级，在最坏的情况下，因为使用了红黑树进行查找，复杂度为。

HTML view coming soon.

Download PDF for the full formatted version.