Review - HashMap / ConcurrentHas

# HashMap

一直对HashMap里“桶”（bucket）的概念有些费解，不知道这个翻译是怎么来的。

HashMap底层是基于数组+链表组成的，不过它在 jdk1.7 和 1.8 中具体实现稍有不同。

1.7 中的数据结构图：

in 1.7

Entry 是 HashMap 中的一个内部类，从他的成员变量很容易看出：

key 就是写入时的键。

value 自然就是值。

开始的时候就提到 HashMap 是由数组和链表组成，所以这个 next 就是用于实现链表结构。

hash 存放的是当前 key 的 hashcode。

下图也许能更好理解为什么是个"bucket"的概念，可能是考虑到每个数组元素都包含一个链表型数据块，整个数组像是一组分别包含很多数据块的桶组成的。 >.<

1.7中有个很明显需要优化的地方

当 Hash 冲突严重时，在桶上形成的链表会变的越来越长，这样在查询时的效率就会越来越低；时间复杂度为 O(N)。

1.8 中重点优化了这个查询效率。

1.8 HashMap 结构图：

in 1.8

看看几个核心的成员变量：

Constants Fields

和1.7的区别：

TREEIFY_THRESHOLD 用于判断是否需要将链表转换为红黑树的阈值。

HashEntry 修改为 Node。

Node 的核心组成其实也是和 1.7 中的 HashEntry 一样，存放的都是 key value hashcode next 等数据。

---

# ConcurrentHashMap

同样也分为 1.7 、1.8 版，两者在实现上略有不同。

先来看看 1.7 的实现，下面是他的结构图：

如图所示，是由 Segment 数组、HashEntry 组成，和 HashMap 一样，仍然是数组加链表。

ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁。

Base 1.8

1.7 已经解决了并发问题，并且能支持 N 个 Segment 这么多次数的并发，但依然存在 HashMap 在 1.7 版本中的问题。

查询遍历链表效率太低。

1.8 做了一些数据结构上的调整。

首先来看下底层的组成结构：

## 面试的重点内容，通常的套路是：

谈谈你理解的 HashMap，讲讲其中的 get put 过程。

1.8 做了什么优化？

是线程安全的嘛？

不安全会导致哪些问题？

如何解决？有没有线程安全的并发容器？

ConcurrentHashMap 是如何实现的？ 1.7、1.8 实现有何不同？为什么这么做？

## 参考

https://blog.csdn.net/luanlouis/article/details/41576373

https://my.oschina.net/crossoverjie/blog/1861138