1. HashMap 的实现原理
底层是 bin 数组 和单向链表实现的.
当元素格式大于 容量 * 负载因子 时进行扩容, 扩容为 2 倍.
当 bin 中增加, 数量大于 8 个时, 将链表转换成红黑树; 当 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