常见问题

Map 有哪些子类？分别有什么区别？一般用哪个？如何对 HashMap 的查找进行优化？

HashMap 数据结构，底层原理，扩容机制

  • 数组 + 链表 + 红黑树
  • JDK8 开始，链表高度 8、数组长度 64 之后，链表转为红黑树，元素以内部类 Node 节点存在。
    • 计算 key 的 hash 值，二次 hash 后对数组长度取模，对应到数组下标。
    • 如果没有产生 hash 冲突（下标位置没有元素），则直接创建 Node 存入数组。
    • 如果产生 hash 冲突，先进行 equals 比较，相同则取代该元素，不同则判断链表高度插入链表，链表高度达到 8，并且数组长度到 64 则转变为红黑树，长度低于 6 则将红黑树转回链表。
    • key 为 null，存在下标为 0 的位置。
  • 数组扩容

    HashMap 和 HashTable 区别

  1. HashMap 线程不安全，HashTable 全部方法都有 synchronized，线程安全但效率低，现在用 ConcurrentHashMap。
  2. HashMap 允许 key 和 value 为 null，而 HashTable 则不允许。

    HashMap key hash 的时间复杂度

    HashMap 线程安全问题

    ConcurrentHashMap 原理，如何解决线程安全问题

    HashTable 全局锁，CHM 是分段锁。
    JDK7：
    数据结构：ReentrantLock + Segment + HashEntry

    ConcurrentHashMap 在 JDK1.8 中为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock？

    ConcurrentHashMap 在 1.8 的时候有了很大的改动，当然，我这里要说的改动不是指链表长度大于 8 就转为红黑树这种常识，我要说的是 ConcurrentHashMap 在 1.8 为什么用 CAS + synchronized 取代 Segment + ReentrantLock 了。

首先，我假设你对 CAS，synchronized，ReentrantLock 这些知识很了解，并且知道 AQS，自旋锁，偏向锁，轻量级锁，重量级锁这些知识，也知道 synchronized 和 ReentrantLock 在唤醒被挂起线程竞争的时候有什么区别。

首先我们说下 1.8 以前的 ConcurrentHashMap 是怎么保证线程并发的。首先在初始化 ConcurrentHashMap 的时候，会初始化一个 Segment 数组，容量为16，而每个 Segment 都继承了 ReentrantLock 类，也就是说每个 Segment 类本身就是一个锁，之后 Segment 内部又有一个 table 数组，而每个 table 数组里的索引数据又对应着一个Node链表。

这样的好处是什么呢？先从老版本的添加流程说起吧，由于电脑里没有 JDK1.7 及以下的版本，我没法给你看代码，所以使用文字描述的方式。

首先，当我们使用 put 方法的时候，是对我们的 key 进行 hash 拿到一个整型，然后将整型对 16 取模，拿到对应的 Segment，之后调用 Segment 的 put 方法，然后上锁。请注意，这里 lock() 的时候其实是 this.lock()，也就是说，每个 Segment 的锁是分开的。

其中一个上锁不会影响另一个，此时也就代表了我可以有十六个线程进来，而 ReentrantLock 上锁的时候如果只有一个线程进来，是不会有线程挂起的操作的，也就是说只需要在 AQS 里使用 CAS 改变一个 state 的值为 1，此时就能对代码进行操作，这样一来，我们等于将并发量/16了。

说完了老版本的 ConcurrentHashMap，我们再说说新版本的，请看下面的图：
image.png

请注意 synchronized 上锁的对象，请记住，synchronized 是靠对象的对象头和此对象对应的 monitor 来保证上锁的。也就是对象头里的重量级锁标志指向了 monitor，而 monitor 内部则保存了一个当前线程，也就是抢到了锁的线程。

那么这里的这个 f 是什么呢？它是 Node 链表里的每一个 Node，也就是说，synchronized 是将每一个 Node 对象作为了一个锁，这样做的好处是什么呢？将锁细化了，也就是说，除非两个线程同时操作一个 Node，注意，是一个 Node，而不是一个 Node 链表，那么才会争抢同一把锁。

如果使用 ReentrantLock 其实也可以将锁细化成这样的，只要让 Node 类继承 ReentrantLock 就行了，这样的话调用 f.lock() 就能做到和 synchronized(f) 同样的效果，但为什么不这样做呢？

试想一下，锁已经被细化到这种程度了，那么出现并发争抢的可能性还高吗？还有就是，哪怕出现争抢了，只要线程可以在 30 到 50 次自旋里拿到锁，那么 synchronized 就不会升级为重量级锁，而等待的线程也就不用被挂起，我们也就少了挂起和唤醒这个上下文切换的过程开销。

但如果是 ReentrantLock 呢？它则只有在线程没有抢到锁，然后新建 Node 节点后再尝试一次而已，不会自旋，而是直接被挂起，这样一来，我们就很容易会多出线程上下文开销的代价。当然，你也可以使用 tryLock()，但是这样又出现了一个问题，你怎么知道tryLock的时间呢？在时间范围里还好，假如超过了呢？

所以，在锁被细化到如此程度上，使用 synchronized 是最好的选择了。这里再补充一句，synchronized 和 ReentrantLock 他们的开销差距是在释放锁时唤醒线程的数量，synchronized 是唤醒锁池里所有的线程 + 刚好来访问的线程，而 ReentrantLock 则是当前线程后进来的第一个线程 + 刚好来访问的线程。

如果是线程并发量不大的情况下，那么 synchronized 因为自旋锁，偏向锁，轻量级锁的原因，不用将等待线程挂起，偏向锁甚至不用自旋，所以在这种情况下要比 ReentrantLock 高效。