1. HashMap 的实现原理
底层是 bin 数组 和单向链表实现的.
当元素格式大于 容量 * 负载因子 时进行扩容, 扩容为 2 倍.
当 bin 中增加元素, 数量大于 8 个时, 且总容量大于等于 64 时, 将链表转换成红黑树; 当 bin 中减少元素, 数量小于 6 个时, 将红黑树转换成类别.
2. hash 算法
将 key 的 hashCode 分成高 16 位和低 16位, 高位与低位异或得出的值就是 hash 值.
这个算法的好处:
- 算法处于从速度, 效果和质量上的综合考虑
- 高位和低位都参与计算, 并使用异或运算, 任何一位变动都会影响 hash 值, 减少 hash 碰撞的可能.
3. 如果出现 hash 碰撞会有什么影响?
hash 碰撞即 2 个元素的 hash 值相同.
会影响 treeify() 和 putTreeVal() 两个方法.
红黑树中元素的结构需要根据 hash 来排列.
如果 key 实现了 Comparable 方法, 则根据 该方法比较顺序; 如果还是相同, 则使用 System.identityHashCode() 比较 (见 tieBreakOrder() 方法).
4. HashMap vs LinkedHashMap vs TreeMap
LinkedHashMap 保存了插入顺序
TreeMap 实现了 SortMap 接口, 可排序
5. HashMap vs HashTable
- HashMap 线程不安全; HashTable 线程安全, 但性能慢
- HashMap 允许 key 为 null, 但至多一个, 允许 value 为 null; HashTable 的 key 和 value 都不允许为 null
6. fast-fail 机制原理
HashMap 中有一个私有属性 modCount, 在 map 添加/移除元素时加 1, 用于记录 map 的修改次数
在调用 Iterator, Spliterator 遍历, 移除, 拆分元素时, 通过判断 modCount 是否有变化, 如果变化则说明有并发修改, 抛出 ConcurrentModificationException 异常.
7. JDK 7 中, 高并发下 HashMap 会产生死循环
当 HashMap 需要扩容时, 会调用 rehash() 方法, 该方法在构建新的链表时, 会将顺序倒置. 在高并发下, 这个方法会倒置链表回路, 从而在 get()
方法调用时产生死循环.
这个问题在 JDK 8 中修复.