大数据，是一种新的思维方式

、环形链表会带来什么后果呢?

假设我现在要查询上述 HashMap 是否包含节点(7，x)，首先根 据 hash 运算得到目标 index 为 3，所以查找目标转到了 3 号链表，

然后根据 key 值为 11 判断与链表的头节点(7，x)的 key 恰好相等，再 判断它们的 value 也相等。说明该 HashMap 中包含了我们所要查询 的几点，返回 true。

假设我现在要查询节点(11，y),经过 hash 运算也将查找目标转 到了 3 号链表，然后根据 key 值为 11 判断与头节点(7，x)的 key 不 相等，则转向下一个节点。

通过对比，发现与下一个节点的 key 和 value 都相等，则直接返回 true。

这样看来似乎没什么问题，然后我们再查一个节点(15，m)，经 过 hash 运算也将查找目标转到了 3 号链表，首先与头节点(7，x)判断 不相等，然后与下一个节点(11，y)对比也不相等。再与下一个节点 判断，这时链表中节点为(7，x)其实就是重新回到了头节点，

它的下一 个节点又是(11，y)，这种搜索会一直无限循环下去，CPU 很快飙 升到 100%，后果很严重。其实不管你搜索什么节点，只要路由到 3 号链表，并且待搜索的 key 不是 7 或 11，都将发生死循环。
 

其中 e 表示当前线程正要迁移的节点，next 表示下一个需要迁移 的节点。如果 e 指向的节点迁移完成，则进入下一次循环，e 指针重新指 向节点(11，y)，next 指针重新指向节点(15，z)。

4)但是当线程 2 刚开始标记好 e 和 next 两个指针，正准备迁移第一 个节点时。线程 1 过来了，并完成了迁移。

5)前面我们说过，HashMap 进入链表是采用头插法，所以对三个元 素 rehash 迁移后的链表顺序为(15，z) —> (11，y) —> (7，x) 图中的 e 和 next 指针属于线程

2，它们还停留在原来的节点上， 这一阶段的结构如下图所示：
 

5、高并发下的扩容问题

HashMap 的这一结构和扩容机制可以保证，在大数据量情况 下，读写性能依然能保持优良。

插入时采用头插法会非常快速，读取 时，也不会因为链表过长而影响读取性能。看到这，会不会觉得 Hash 是个完美的设计，其实不是，因为 HashMap 并不是线程安全的数据结构。

尤其是在扩容时，如果并发量不大通常不会有什么问题，但在高 并发情况下，扩容可能导致很严重的问题。我们下面来模拟一个高并发情况下扩容的例子。

1)假设有一个 HashMap，它的负载因子为 1，有两个元素(7，x)和 (11，y)，它们 hash 运算的结果都为 1，所以都在 1 号链表(即 index 为 1 所指向的链表中，为便于描述，下面都简称)中，如下所 示。
 

为何要一直强调是 jdk1.7 版本，因为在 jdk1.8 的时候 HashMap 结构发生了较大的变化，1.8 版本的 HashMap 采用的是尾插法而且底 层结构也发生了变化。

4、扩容

java 工程师都清楚 jdk1.7 版本的 HashMap初始默认长度为 16，你也可以自己定义，但不管你是自定义还是选择默认长度，

随着 元素的增加并达到了一定的阈值，总是要扩容的。扩容时是按 2 倍来进行的，就是创建一个 2 倍大小的数组，将原 来的元素重新 Hash，计算新的 index 放入到新的数组+链表结构中。

（编辑：济南站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!