Map及其实现类、锁

HashMap、HashTable、ConcurrentHashMap 区别

---

一.HashMap和HashTable的区别

1、两者父类不同

HashMap是继承自AbstractMap类，而Hashtable是继承自Dictionary类。不过它们都实现了同时实现了map、Cloneable（可复制）、Serializable（可序列化）这三个接口。

2、对外提供的接口不同

Hashtable比HashMap多提供了elments() 和contains() 两个方法。

• elments() 方法继承自Hashtable的父类Dictionnary。elements() 方法用于返回此Hashtable中的
  value的枚举。
• contains()方法判断该Hashtable是否包含传入的value。它的作用与containsValue()一致。事实上，contansValue() 就只是调用了一下contains() 方法。

3、对null的支持不同

• Hashtable：key和value都不能为null。
• HashMap：key可以为null，但是这样的key只能有一个，因为必须保证key的唯一性；可以有多个key值对应的value为null。

4、安全性不同

• HashMap是线程不安全的，在多线程并发的环境下，可能会产生死锁等问题，因此需要开发人员自己处理多线程的安全问题。
• Hashtable是线程安全的，它的每个方法上都有synchronized 关键字，因此可直接用于多线程中。
• 虽然HashMap是线程不安全的，但是它的效率远远高于Hashtable，这样设计是合理的，因为大部分的使用场景都是单线程。
• ConcurrentHashMap虽然也是线程安全的，但是它的效率比Hashtable要高好多倍。因为ConcurrentHashMap使用了分段锁(JDK1.7)，并不对整个数据进行锁定。当需要多线程操作的时候可以使用线程安全的ConcurrentHashMap。

5、初始容量大小和每次扩充容量大小不同

6、计算hash值的方法不同

---

二.ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的⽅式上不同。

1. 底层数据结构

• ConcurrentHashMap ： JDK1.7 的 ConcurrentHashMap 底层采⽤ 分段的数组+链表 实现，JDK1.8采⽤的数据结构跟 HashMap1.8 的结构⼀样，数组+链表+红⿊树。
• Hashtable ：JDK1.8 之前的 HashMap 的底层数据结构类似都是采⽤ 数组+链表 的形式，数组是HashMap 的主体，链表则是主要为了解决哈希冲突⽽存在的；

2.实现线程安全的⽅式（重要）

• ConcurrentHashMap ：在 JDK1.7 的时候， ConcurrentHashMap （分段锁）对整个桶数组进⾏了分割分段( Segment )，每⼀把锁只锁容器其中⼀部分数据，多线程访问容器⾥不同数据段的数据，就不会存在锁竞争，提⾼并发访问率。 到了 JDK1.8 的时候已经摒弃了 Segment 的概念，⽽是直接⽤ Node 数组+链表+红⿊树的数据结构来实现，并发控制使⽤ synchronized 和 CAS 来操作。
• Hashtable (同⼀把锁) :使⽤ synchronized 来保证线程安全，效率⾮常低下。当⼀个线程访问同步⽅法时，其他线程也访问同步⽅法，可能会进⼊阻塞或轮询状态，如使⽤ put 添加元素，另⼀个线程不能使⽤ put 添加元素，也不能使⽤ get，竞争会越来越激烈效率越低。

---

三.Map

• HashMap ：稍后详细介绍
• LinkedHashMap ： LinkedHashMap 继承⾃ HashMap ，所以它的底层仍然是基于拉链式散列结构即由数组+链表|红⿊树组成。另外， LinkedHashMap 在上⾯结构的基础上，增加了⼀条双向链表，使得上⾯的结构可以保持键值对的插⼊顺序。同时通过对链表进⾏相应的操作，实现了访问顺序相关逻辑。
• Hashtable ： 数组+链表组成的。
• TreeMap ： 红⿊树（⾃平衡的排序⼆叉树）

---

四.简述synchronized

1. 对于Synchronized来说，它是java语言的关键字，是原生语法层面的互斥，需要jvm实现。
2. 底层原理：Synchronized进过编译，会在同步块的前后分别形成monitorenter和monitorexit这个两个字节码指令。在执行monitorenter指令时，首先要尝试获取对象锁。如果这个对象没被锁定，或者当前线程已经拥有了那个对象锁，把锁的计算器加1，相应的，在执行monitorexit指令时会将锁计算器就减1，当计算器为0时，锁就被释放了。如果获取对象锁失败，那当前线程就要阻塞（悲观锁代表），直到对象锁被另一个线程释放为止。

---

五.SynchronizedMap和ConcurrentHashMap有什么区别？

• SynchronizedMap()和Hashtable一样，实现上在调用map所有方法时，都对整个map进行同步。所以，只要有一个线程访问map，其他线程就无法进入map，
• 而ConcurrentHashMap的实现却更加精细，它对map中的所有桶加了锁。而如果一个线程在访问ConcurrentHashMap某个桶时，其他线程，仍然可以对map执行某些操作。
• 所以，ConcurrentHashMap在性能以及安全性方面，明显比Collections.synchronizedMap()更加有优势。同时，同步操作精确控制到桶，这样，即使在遍历map时，如果其他线程试图对map进行数据修改，也不会抛出ConcurrentModificationException。

---

六.HashMap详解

1）基本数据结构

• 1.7 数组 + 链表
• 1.8 数组 + （链表 | 红黑树）

2）树化与退化

树化意义

• 红黑树用来避免 DoS 攻击，防止链表超长时性能下降，树化应当是偶然情况，是保底策略
• hash 表的查找，更新的时间复杂度是 $O(1)$，而红黑树的查找，更新的时间复杂度是 $O(lo{g}_{2}n)$，TreeNode 占用空间也比普通 Node 的大，如非必要，尽量还是使用链表
• hash 值如果足够随机，则在 hash 表内按泊松分布，在负载因子 0.75 的情况下，长度超过 8 的链表出现概率是 0.00000006，树化阈值选择 8 就是为了让树化几率足够小

树化规则

• 当链表长度超过树化阈值 8 时，先尝试扩容来减少链表长度，如果数组容量已经 >=64，才会进行树化

退化规则

• 情况1：在扩容时如果拆分树时，树元素个数 <= 6 则会退化链表
• 情况2：remove 树节点时，若 root、root.left、root.right、root.left.left 有一个为 null ，也会退化为链表

3）索引计算

索引计算方法

• 首先，计算对象的 hashCode()
• 再进行调用 HashMap 的 hash() 方法进行二次哈希
  • 二次 hash() 是为了综合高位数据，让哈希分布更为均匀
• 最后 & (capacity – 1) 得到索引

数组容量为何是 2 的 n 次幂

1. 计算索引时效率更高：如果是 2 的 n 次幂可以使用位与运算代替取模
2. 扩容时重新计算索引效率更高： hash & oldCap == 0 的元素留在原来位置 ，否则新位置 = 旧位置 + oldCap

注意

• 二次 hash 是为了配合 容量是 2 的 n 次幂 这一设计前提，如果 hash 表的容量不是 2 的 n 次幂，则不必二次 hash
• 容量是 2 的 n 次幂 这一设计计算索引效率更好，但 hash 的分散性就不好，需要二次 hash 来作为补偿，没有采用这一设计的典型例子是 Hashtable

4）put 与扩容

put 流程

1. HashMap 是懒惰创建数组的，首次使用才创建数组
2. 计算索引（桶下标）
3. 如果桶下标还没人占用，创建 Node 占位返回
4. 如果桶下标已经有人占用
   1. 已经是 TreeNode 走红黑树的添加或更新逻辑
   2. 是普通 Node，走链表的添加或更新逻辑，如果链表长度超过树化阈值，走树化逻辑
5. 返回前检查容量是否超过阈值，一旦超过进行扩容

1.7 与 1.8 的区别

1. 链表插入节点时，1.7 是头插法，1.8 是尾插法

2. 1.7 是大于等于阈值且没有空位时才扩容，而 1.8 是大于阈值就扩容

3. 1.8 在扩容计算 Node 索引时，会优化
   

扩容（加载）因子为何默认是 0.75f
4. 在空间占用与查询时间之间取得较好的权衡
5. 大于这个值，空间节省了，但链表就会比较长影响性能
6. 小于这个值，冲突减少了，但扩容就会更频繁，空间占用也更多

5）key 的设计

key 的设计要求

1. HashMap 的 key 可以为 null，但 Map 的其他实现则不然
2. 作为 key 的对象，必须实现 hashCode 和 equals，并且 key 的内容不能修改（不可变）
3. key 的 hashCode 应该有良好的散列性

---

补充

1.悲观锁和乐观锁 CAS

2.Synchronized ReentrantLock SynchronizedMap ConcurrentHashMap

3.wait sleep lock synchronized volatile

参考之前的文章