关于java:HashMap

6次阅读

共计 1715 个字符，预计需要花费 5 分钟才能阅读完成。

HashMap 的数据结构是数组 + 链表。数组中存储的是 Entry 对象，数组中的每一个 Entry 元素，又是一个链表的头节点。

1. 在 JDK1.7 中，当并发执行扩容操作时会造成环形链和数据失落的状况。

2. 在 JDK1.8 中，在并发执行 put 操作时会产生数据笼罩的状况。
put 操作时会判断是否呈现 hash 碰撞，假如两个线程 A、B 都在进行 put 操作，并且 hash 函数计算出的插入下标是雷同的，当线程 A 执行完判断是否呈现 hash 碰撞后因为工夫片耗尽导致被挂起，而线程 B 失去工夫片后在该下标处插入了元素，实现了失常的插入，而后线程 A 取得工夫片，因为之前曾经进行了 hash 碰撞的判断，所有此时不会再进行判断，而是间接进行插入，这就导致了线程 B 插入的数据被线程 A 笼罩了，从而线程不平安。

线程平安的有 HashTable 还有 Collections.synchronizedMap, 两种汇合保障线程平安的计划都是整个汇合加锁。保障线程平安的状况下也升高了效率。
ConcurrentHashMap 在保障线程平安的状况下进步运行效率。

ConcurrentHashMap 的根本构造是 Segment 数组，每一个 Segment 是一个独立的 HashMap, 当咱们在操作数据时，会对每个独立的 Segment 加锁，并不影响其余的 Segment 读取操作。

Get 办法：

1. 为输出的 Key 做 Hash 运算，失去 hash 值。

2. 通过 hash 值，定位到对应的 Segment 对象

3. 再次通过 hash 值，定位到 Segment 当中数组的具体位置。

Put 办法：

1. 为输出的 Key 做 Hash 运算，失去 hash 值。

2. 通过 hash 值，定位到对应的 Segment 对象

3. 获取可重入锁
4. 再次通过 hash 值，定位到 Segment 当中数组的具体位置。
5. 插入或笼罩 HashEntry 对象。
6. 开释锁。

JDK1.8 的实现曾经摒弃了 Segment 的概念，而是间接用 Node 数组 + 链表 + 红黑树的数据结构来实现，并发管制应用 Synchronized 和 CAS 来操作，整个看起来就像是优化过且线程平安的 HashMap，尽管在 JDK1.8 中还能看到 Segment 的数据结构，然而曾经简化了属性，只是为了兼容旧版本.

JDK1.8 版本的 ConcurrentHashMap 的数据结构曾经靠近 HashMap，相对而言，ConcurrentHashMap 只是减少了同步的操作来管制并发，从 JDK1.7 版本的 ReentrantLock+Segment+HashEntry，到 JDK1.8 版本中 synchronized+CAS+HashEntry+ 红黑树, 相对而言，总结如下思考

JDK1.8 的实现升高锁的粒度，JDK1.7 版本锁的粒度是基于 Segment 的，蕴含多个 HashEntry，而 JDK1.8 锁的粒度就是 HashEntry（首节点）
JDK1.8 版本的数据结构变得更加简略，使得操作也更加清晰晦涩，因为曾经应用 synchronized 来进行同步，所以不须要分段锁的概念，也就不须要 Segment 这种数据结构了，因为粒度的升高，实现的复杂度也减少了
JDK1.8 应用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑树的遍历效率是很快的，代替肯定阈值的链表，这样造成一个最佳拍档
JDK1.8 为什么应用内置锁 synchronized 来代替重入锁 ReentrantLock，我感觉有以下几点
1. 因为粒度升高了，在相对而言的低粒度加锁形式，synchronized 并不比 ReentrantLock 差，在粗粒度加锁中 ReentrantLock 可能通过 Condition 来管制各个低粒度的边界，更加的灵便，而在低粒度中，Condition 的劣势就没有了
2.JVM 的开发团队素来都没有放弃 synchronized，而且基于 JVM 的 synchronized 优化空间更大，应用内嵌的关键字比应用 API 更加天然
3. 在大量的数据操作下，对于 JVM 的内存压力，基于 API 的 ReentrantLock 会开销更多的内存，尽管不是瓶颈，然而也是一个抉择根据。

正文完