集合
集合
说说 HasMap 的实现？
HashMap 在 JDK1.7 版本是用数组 + 链表，在 JDK1.8 版本则是数组 + 链表 + 红黑树的结构。主要原因是提高查询效率，当链表长度大于 8，整体容量大于 64 的时候，会将链表转化成红黑树。
在 HashMap 中，比较关键的几个知识点是：
- 如何寻找下标？
- 扩容时链表移位的逻辑
- 链表树化的逻辑
- 红黑树链化的逻辑
寻找下标的逻辑。其本质上就是进行取余，但是 JDK 实现时将其转化成了 hash 值与 n-1 的与操作，这样可以提高运算效率。在获取哈希值的时候，为了避免发生哈希碰撞，其对 hash 值的高 16 位与低 16 位做了异或运算，提高了随机性。
扩容时链表移位。本质上就是利用 HashMap 扩容时是乘以 2 扩容的原理。因为 n 的大小变成了两倍，那么根据 (n-1) & hash 的运算结果，可以知道链表的位置要么就在原来的位置，要么就在 oldIndex + oldCapacity 的位置。例如我们从 8 的容量变为 16 的容量，那么 n-1 的值就从 7 变为 15，那么本质上就是 0111 变为了 1111，而 hash 值不变，那么就是第 4 位变成 1 了。那么如果 hash 值第 4 为为 1，那么下标就多加了 8（oldCapacity，2 的 3 次方）。
链表树化的逻辑。链表树化本质上是先转成双向链表，再将双向链表树化。将链表转成双向链表。 这个过程比较简单，其实就是循环链表，增加一个前后的引用（prev、next）。将双向链表树化。 这个步骤，其实就是将一个个节点插入红黑树中。
红黑树链化，因为保存了插入顺序，所以直接把红黑树转成链表，之后再重新映射链表即可。
HashMap 与 Hashtable 的区别？
HashMap 与 Hashtable 的区别是：HashMap 是线程不安全的，而 Hashtable 则是线程安全的，这是它们最大的区别。再内部实现上，她俩都是一样的，Hashtable 实现同步的方式，是在每个方法上使用 synchronized 关键字实现的。
聊聊 ConcurrentHashMap 的原理
ConcurrentHashMap 的原理，可以从底层数据结构及线程安全实现两方面来分析。
- 底层数据结构方面。 其底层结构与 HashMap 类似。在 JDK1.7 时都是采用「数组 + 链表」实现，在 JDK1.8 时都采用「数组+链表+红黑树」实现。
- 线程安全方面。 在 JDK1.7 时，其采用分段锁的方式对数组进行分割，每把锁只锁定容器里的部分元素，这样多线程访问不通数据段的数据，就不会存在锁竞争，提高并发访问率。而在 JDK1.8 时，则使用了 synchronized + CAS 操作来实现并发控制，提高了效率（JDK1.6 对 synchronized 锁做了非常多优化）。
聊聊 ConcurrentHashMap 与 Hashtable 的区别？
Hashtable 没有做分段锁的操作，每次锁定都是整个集合锁定，因此虽然其实线程安全的，但是其并发度是很低的。而 ConcurrentHashMap 做了分段锁操作，并且还用了 synchronized + CAS 的方式来优化提高效率，因此其不仅是线程安全的，还是高并发的。可以看到，他们两者最大的区别是锁的粒度，一个粗，一个细。
所以说，Hashtable 只适合用于低并发度的线程安全场景，而 ConcurrentHashMap 则可用于高并发的线程安全场景。