常见的Map类

Hashtable、HashMap、LinkedHashMap、TreeMap

线程安全的Map类

Hashtable 、 Collections.synchronizedMap、ConcurrentHashMap

梳理关系

LinkedHashMap是HashMap添加双向链表以保证有序。TreeMap是红黑树实现的。HashMap和ConcurrentHashMap则是老生常谈了。Collections.synchronizedMap是方法中加锁。

HashMap 和 Hashtable 的区别

  • 线程是否安全： HashMap 是非线程安全的，HashTable 是线程安全的,因为 HashTable 内部的方法基本都经过synchronized 修饰。
  • 对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
  • 初始容量大小和每次扩充容量大小的不同 ： ① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 总是使用 2 的幂作为哈希表的大小。
  • 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

HashMap分析（1.7）

这里有部分源码，我就不记录了

1.存储结构

Entry[]数组加链表

2.发生冲突头插法

3.put方法

HashMap 使用第 0 个桶存放键为 null 的键值对。
过程：

  1. 键为 null 单独处理
  2. 确定桶下标
  3. 先找出是否已经存在键为 key 的键值对，如果存在的话就更新这个键值对的值为 value。（hash和equals两个方法判断key是否存在）
  4. 如果不存在就添加。添加时会判断size是否超过阈值，超过则扩容，然后重新计算hash值，然后放到新的位置（size为使用到的数组个数，而非整个Map的元素个数）。头插法。也就是说，是先扩容，再添加。这里的扩容时机，实际上，size并没有算上新添加的节点。比如现在size=11，添加一个节点后，size=12,那么下次再添加时，就扩容，然后再把节点加进来。

4.扩容机制及重要参数

n是容量，(n - 1) & hash以保证2倍扩容时，计算数组下标效果和取模一样。
初始容量16，装载因子0.75。
1.7扩容会重新计算新的hash,然后将元素放到扩容后的map中。

HashMap（1.8与1.7不同的地方）

1.JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。也就是说，需要满足两个条件才会红黑树。小于6时退化成链表。泊松分布就是回答为什么是8.
2.尾插法
3.在扩容机制上，原来的元素摆放在新的map中的算法不同。
4.在扩容上，是先添加，如果条件满足，再扩容。

put方法

  1. 判断当前桶是否为空，空的就需要初始化（resize 中会判断是否进行初始化）。
  2. 根据当前 key 的 hashcode 定位到具体的桶中并判断是否为空，为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。
  3. 如果当前桶有值（ Hash 冲突），那么就要比较当前桶中的 key、key 的 hashcode 与写入的 key 是否相等，相等就赋值给 e,值覆盖。冲突且key值唯一，则进行插入动作第4或5步
  4. 如果当前桶为红黑树，那就要按照红黑树的方式写入数据。
  5. 如果是个链表，就需要将当前的 key、value 封装成一个新节点写入到当前桶的后面（形成链表）。
  6. 接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树。（需要判断数组的长度）
  7. 最后判断是否需要进行扩容。

ConcurrentHashMap

1.7版本

ConcurrentHashMap 采用了分段锁（Segment），每个分段锁维护着几个桶（HashEntry），多个线程可以同时访问不同分段锁上的桶，从而使其并发度更高（并发度就是 Segment 的个数）。默认的并发级别为 16，也就是说默认创建 16 个 Segment。也就是初始数组的大小是16.

Segment 继承自 ReentrantLock。

put方法

  1. 首先是通过 key 定位到 Segment，之后在对应的 Segment 中进行具体的 put。

  2. 然后会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut() 自旋获取锁。

  3. 如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取，保证能获取成功。

  4. 将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。遍历该 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等则覆盖旧的 value。

  5. 为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容。

  6. 最后会释放所获取当前 Segment 的锁。

1.8版本

JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。1.8版本和1.8版本的HashMap实现类似。相当于只是在1.8版本的HashMap底层实现上，增加了并发。而1.7的ConcurrentHashMap底层实现不同，每个分段里面还有HashEntry数组。

什么是快速失败(fail-fast)？

快速失败(fail-fast) 是 Java 集合的一种错误检测机制。在使用迭代器对集合进行遍历的时候，我们在多线程下操作非安全失败(fail-safe)的集合类可能就会触发 fail-fast 机制，导致抛出 ConcurrentModificationException 异常。 另外，在单线程下，如果在遍历过程中对集合对象的内容进行了修改的话也会触发 fail-fast 机制。

简而言之，就是在遍历时进行了修改，或者进行了并发操作，就容易出现。

什么是安全失败(fail-safe)呢？

采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。所以，在遍历过程中对原集合所作的修改并不能被迭代器检测到，故不会抛 ConcurrentModificationException 异常。