Java集合

Map

HashMap

实现原理/底层

Java1.8之前：数组加链表

Java1.8之后：当一个链表的长度超过8，且数组大小超过64时，会将链表转换成红黑树存储，查找效率更高，时间复杂度O(log n)。如果长度超过8，但是数组容量不足64，则会选择扩容数组。

定位算法

计算key的哈希值，并进行与运算

int index = hash & (table.length - 1);

扩容机制

HashMap扩容因子为0.75，当元素个数超过总容量的75%时，则会触发扩容。

主要分为两个步骤：

1. 对哈希表长度扩展成2倍

2. 将旧哈希表中的数据放入新的表中

为什么是2倍？如何放入新表？

通过将长度进行2次幂扩容，在重新计算hash值时，只需要看新增位是1还是0，是0则索引不变，是1则变成“原索引+oldCap”。这样既节省了重新计算hash的时间，同时也将冲突的节点均匀分散了。

put方法

• 根据要添加的键的哈希码计算在数组中的索引
• 判断对应位置是否有键值对

如果为空，则根据键值对直接创建Entry对象，把该对象存入相应位置。

• 如果该位置存在其他键值对，检查第一个键值对的哈希码和键是否与要添加的键值对相同(equals()和hashcode())

如果相同，说明添加的是同一个键，使用新值替换旧值，完成更新

• 如果不相同，则继续遍历链表或红黑树，查找是否有相同的键

如果有相同的值，则使用新值替换旧值，完成更新。

如果没有相同的值，则将新的键值对添加到链表或红黑树。

• 检查链表长度是否超过阈值(8)

如果链表长度超过8，且数组容量超过64，则会将链表转换成红黑树。

• 检查负载因子是否超过阈值(0.75)

如果键值对的数量与数组的长度大于阈值，则触发扩容。(链表长度>8，数组容量<64也会触发扩容)

• 扩容操作

• 完成添加操作

ConcurrentHashMap

底层实现：

Java1.8之前：底层实现是数组+链表的形式(Segment[]和HashEntry[])

使用分段锁，将整个哈希表分成多个段，每个段都维护自己的哈希表和锁。

Java1.8之后：底层实现是数组+链表/红黑树的形式

主要通过 volatile + CAS 或者 synchronized 来实现的线程安全的。

加锁机制：

分段锁：

将整个数据结构分为多个Segment后，每个Segment都有自己的锁，对不同Segment的操作互不影响，从而提升并发性能。

乐观锁/悲观锁

添加元素时，判断计算的hash是否有元素，如果没元素，则会使用乐观锁CAS，如果发生了hash碰撞则使用悲观锁synchronized。这是因为发生hash碰撞时，大概率是线程竞争比较激烈的时候，使用悲观锁保证线程安全。