目录

1. 常用Map类和区别

2. HashMap工作原理

2.1 Put()执行过程

2.2 扩容机制

3. ConcurrentHashMap

3.1 工作原理

3.2 JDK7分段锁的优缺点

---

1. 常用Map类和区别

Map类包含：HashMap、HashTable、LinkedHashMap、TreeMap。

1) 从功能上区分。

• HashMap：在Map中插入，删除，定位元素。
• TreeMap：可以按照自定义顺序或自然顺序遍历。
• LinkedHashMap：要求输入顺序和输出顺序相同。

2) 内部数据结构。

• HashMap：数组+链表/红黑树。
• HashTable：数组+链表。
• LinkedHashMap：双向链表。
• TreeMap：红黑树。

3) 线程安全性。

• HashMap：非线程安全。
• HashTable：线程安全。
• LinkedHashMap：非线程安全。
• TreeMap：非线程安全。

2. HashMap工作原理

HashMap是基于哈希算法来确定元素的槽，当我们向集合中存入数据时，它会计算传入的Key的哈希值，并利用哈希值取余来确定槽的位置。

如果元素发生碰撞，也就是这个槽已经存在其他的元素了，则HashMap会通过链表将这些元素组织起来。如果碰撞进一步加剧，某个链表的长度达到了8，则HashMap会创建红黑树来代替这个链表，从而提高对这个槽中数据的查找的速度。

数组的默认初始容量为16，这个容量会以2的指数进行扩容，当数组中的元素达到一定比例的时候HashMap就会扩容，这个比例叫做负载因子，默认为0.75。

2.1 Put()执行过程

1) 判断数组,若发现数组为空，则进行首次扩容。

2) 判断头节点，若发现头节点为空，则新建链表节点，存入数组。

3) 判断头节点，若发现头节点非空，则将元素插入槽内。

• 若元素的key与头节点一致，则直接覆盖头节点。
• 若元素为树型节点，则将元素追加到树中。
• 若元素为链表节点,则将元素追加到链表中。（追加后，需要判断链表长度以决定是否转为红黑树。比如，若链表长度达到8、数组容量未达到64，则扩容。若链表长度达到8、数组容量达到64,则转为红黑树）
• 插入元素后,判断元素的个数，若发现超过阈值则再次扩容。

2.2 扩容机制

HashMap中添加数据时,有三个条件会触发它的扩容行为：

1) 如果数组为空，则进行首次扩容。

2) 将元素接入链表后，如果链表长度达到8，并且数组长度小于64，则扩容。

3) 添加后，如果数组中元素超过阈值，即比例超出限制（默认为0.75），则扩容。 并且每次扩容时都是将容量翻倍，即创建一个2倍大的新数组，然后再将旧数组中的数组迁移到新数组里。

3. ConcurrentHashMap

3.1 工作原理

JDK7 中的ConcurrentHashMap使用的是Segment和HashEntry。

JDK8 中的ConcurrentHashMap使用的是synchronized和CAS和HashEntry和红黑树。

ConcurrentHashMap和HashMap一样，使用了红黑树，而在ConcurrentHashMap中则是取消了Segment分段锁的数据结构，取而代之的是Node数组+链表+红黑树的结构，使用的 “读写锁”采用了CAS和Synchronized来保证线程的安全。

3.2 JDK7分段锁的优缺点

Segment继承了重入锁ReentrantLock，有了锁的功能，每个锁控制的是一段，当每个Segment越来越大时，锁的粒度就变得有些大了，具体分段数量由concurrencyLevel字段来控制。

1) 优点。

• 在于保证在操作不同段 map 的时候可以并发执行，操作同段 map 的时候，进行锁的竞争和等待。这相对于直接对整个map同步synchronized是有优势的。

2) 缺点。同时这也是为什么在 JDK8 不在继续使用分段锁的原因。

• 每个锁控制的是一段，当分段很多，并且加锁的分段不连续的时候，内存空间的浪费比较严重。

• 操作map时竞争同一个分段锁的概率非常小时，分段锁反而会造成更新等操作的长时间等待。

• 当某个段很大时，分段锁的性能会下降。