HashMap 为什么线程不安全？
JDK1.7 及之前版本，在多线程环境下，HashMap 扩容时会造成死循环和数据丢失的问题。
数据丢失这个在 JDK1.7 和 JDK 1.8 中都存在 ，这里以 JDK 1.8 为例进行介绍。
JDK 1.8 后，在 HashMap 中，多个键值对可能会被分配到同一个桶（bucket），并以链表或红黑树的形式存储。多个线程对 HashMap 的 put 操作会导致线程不安全，具体来说会有数据覆盖的风险。
举个例子：
- 两个线程 1,2 同时进行 put 操作，并且发生了哈希冲突（hash 函数计算出的插入下标是相同的）。
- 不同的线程可能在不同的时间片获得 CPU 执行的机会，当前线程 1 执行完哈希冲突判断后，由于时间片耗尽挂起。线程 2 先完成了插入操作。
- 随后，线程 1 获得时间片，由于之前已经进行过 hash 碰撞的判断，所有此时会直接进行插入，这就导致线程 2 插入的数据被线程 1 覆盖了。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// ...
// 判断是否出现 hash 碰撞
// (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 桶中已经存在元素（处理hash冲突）
else {
// ...
}还有一种情况是这两个线程同时 put 操作导致 size 的值不正确，进而导致数据覆盖的问题：
- 线程 1 执行
if(++size > threshold)判断时，假设获得size的值为 10，由于时间片耗尽挂起。 - 线程 2 也执行
if(++size > threshold)判断，获得size的值也为 10，并将元素插入到该桶位中，并将size的值更新为 11。 - 随后，线程 1 获得时间片，它也将元素放入桶位中，并将 size 的值更新为 11。
- 线程 1、2 都执行了一次
put操作，但是size的值只增加了 1，也就导致实际上只有一个元素被添加到了HashMap中。public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // ... // 实际大小大于阈值则扩容 if (++size > threshold) resize(); // 插入后回调 afterNodeInsertion(evict); return null; }
ConcurrentHashMap 和 Hashtable 的区别？
ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。
- 底层数据结构： JDK1.7 的
ConcurrentHashMap底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。Hashtable和 JDK1.8 之前的HashMap的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的； - 实现线程安全的方式（重要）：
- 在 JDK1.7 的时候，
ConcurrentHashMap对整个桶数组进行了分割分段(Segment，分段锁)，每一把锁只锁容器其中一部分数据（下面有示意图），多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 - 到了 JDK1.8 的时候，
ConcurrentHashMap已经摒弃了Segment的概念，而是直接用Node数组+链表+红黑树的数据结构来实现，并发控制使用synchronized和 CAS 来操作。（JDK1.6 以后synchronized锁做了很多优化） 整个看起来就像是优化过且线程安全的HashMap，虽然在 JDK1.8 中还能看到Segment的数据结构，但是已经简化了属性，只是为了兼容旧版本； Hashtable(同一把锁) :使用synchronized来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。
- 在 JDK1.7 的时候，
下面，我们再来看看两者底层数据结构的对比图。
Hashtable :
Hashtable 的内部结构
JDK1.7 的 ConcurrentHashMap：
Java7 ConcurrentHashMap 存储结构
ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。
Segment 数组中的每个元素包含一个 HashEntry 数组，每个 HashEntry 数组属于链表结构。
JDK1.8 的 ConcurrentHashMap：
Java8 ConcurrentHashMap 存储结构
JDK1.8 的 ConcurrentHashMap 不再是 Segment 数组 + HashEntry 数组 + 链表，而是 Node 数组 + 链表 / 红黑树。不过，Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode。当冲突链表达到一定长度时，链表会转换成红黑树。
HashMap 的长度为什么是 2 的幂次方？
为了让 HashMap 存取高效并减少碰撞，我们需要确保数据尽量均匀分布。哈希值在 Java 中通常使用 int 表示，其范围是 -2147483648 ~ 2147483647前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但是，问题是一个 40 亿长度的数组，内存是放不下的。所以，这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。
这个算法应该如何设计呢？
我们首先可能会想到采用 % 取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1) 的前提是 length 是 2 的 n 次方）。” 并且，采用二进制位操作 & 相对于 % 能够提高运算效率。
除了上面所说的位运算比取余效率高之外，我觉得更重要的一个原因是：长度是 2 的幂次方，可以让 HashMap 在扩容的时候更均匀。例如:
- length = 8 时，length - 1 = 7 的二进制位
0111 - length = 16 时，length - 1 = 15 的二进制位
1111
这时候原本存在 HashMap 中的元素计算新的数组位置时 hash&(length-1)，取决 hash 的第四个二进制位（从右数），会出现两种情况：
- 第四个二进制位为 0，数组位置不变，也就是说当前元素在新数组和旧数组的位置相同。
- 第四个二进制位为 1，数组位置在新数组扩容之后的那一部分。
假设有一个元素的哈希值为 10101100 旧数组元素位置计算： hash = 10101100 length - 1 = 00000111 & ----------------- index = 00000100 (4) 新数组元素位置计算： hash = 10101100 length - 1 = 00001111 & ----------------- index = 00001100 (12) 看第四位（从右数）： 1.高位为 0：位置不变。 2.高位为 1：移动到新位置（原索引位置+原容量）。注意⚠️：这里列举的场景看的是第四个二进制位，更准确点来说看的是高位（从右数），例如
length = 32时，length - 1 = 31，二进制为11111，这里看的就是第五个二进制位。也就是说扩容之后，在旧数组元素 hash 值比较均匀（至于 hash 值均不均匀，取决于前面讲的对象的
hashcode()方法和扰动函数）的情况下，新数组元素也会被分配的比较均匀，最好的情况是会有一半在新数组的前半部分，一半在新数组后半部分。这样也使得扩容机制变得简单和高效，扩容后只需检查哈希值高位的变化来决定元素的新位置，要么位置不变（高位为 0），要么就是移动到新位置（高位为 1，原索引位置+原容量）。
最后，简单总结一下 HashMap 的长度是 2 的幂次方的原因：
- 位运算效率更高：位运算(&)比取余运算(%)更高效。当长度为 2 的幂次方时，
hash % length等价于hash & (length - 1)。 - 可以更好地保证哈希值的均匀分布：扩容之后，在旧数组元素 hash 值比较均匀的情况下，新数组元素也会被分配的比较均匀，最好的情况是会有一半在新数组的前半部分，一半在新数组后半部分。
- 扩容机制变得简单和高效：扩容后只需检查哈希值高位的变化来决定元素的新位置，要么位置不变（高位为 0），要么就是移动到新位置（高位为 1，原索引位置+原容量）。