【面试必问】对比HashMap 和 HashTable

共同点

1. 都是K-V结构的集合类数据结构，支持范型 ；
2. 在1.2以后的版本中，都实现了 Map 接口；
3. 都是通过数组实现一个基本的table，添加数据的时候，通过计算key的hash值然后对table长度取模运算以得到对应的index，使用了模运算来保证尽可能均匀地添加到table里面。但是HashMap由于取模运算的特殊实现，使得只有在 table的长度是2的n次方时才是取模运算。

区别对比

1. 支持版本：

   • HashMap: 从1.2 开始
   • HashTable: 从1.0 开始

2. 线程安全

   • HashMap: 非线程安全
   • HashTable: 线程安全，通过给操作的方法添加 synchronized关键字实现的安全的访问控制，但是以此会牺牲一些效率，在很多场景并不需要所有的方法均添加同步锁

3. null 支持

   • HashMap: Key和Value均可以为null
   • HashTable: Key和Value均不为null

4. 实现原理

   • HashMap: 1.8版本前是数组+链表的结构；1.8之后，当链表长度过大（默认是长度达到8的时候）的时候，会转成红黑树。
   • HashTable: 通过Entry的数组实现，Entry是一个单向数组

5. 哈希算法

   • HashMap: 使用Object 的hashCode得到一个k，然后进一步运算，得到是高16位和低16位都参与到了运算的结果：

     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

   • HashTable: 直接使用Object自身的 hashCode() 方法

6. 容量

   • HashMap: 默认情况下，初始容量16，负载因子0.75，每次扩容都是2倍的扩容。
   • HashTable: 默认情况下，容量是11，负载因子0.75

7. 取模运算

   • HashMap: 默认情况下，HashMap的table长度都会是2的n次方，内部使用了或运算来代替%来提高性能，具体如下：

     // n 为 2^n 的时候，以下公式等价于 hash % n
     (n-1) & hash

   • HashTable: 直接使用 % 运算符进行取模运算

其他注意点

1. HashMap 里面的红黑树
   在java 1.8 以后，HashMap里面的链表长度达到一定值以后(TREEIFY_THRESHOLD = 8)，就会转成红黑树以实现更高的搜索性能

2. HashMap 的扩容

理论上，HashMap如果某一个位置上只有一个元素的时候，那么获取元素的速度是非常快的，只有 O(1) 的复杂度，但是哈希碰撞是不可避免的，那么使得哈希碰撞尽可能少得发生则是一个可能实现的有效途径了。这里就涉及到扩容了。

每一个HashMap有几个关键的属性：

1. 容量：capacity
2. 负载因子：loadFactor ，小于1
3. 阈值：threshold ，阈值等于 容量 * 负载因子

扩容会发生在以下场景：

1. 新增元素时发现达到阈值
2. 版本1.8以后，进行链表转树的时候 check 当前的容量小于 64 的时候（MIN_TREEIFY_CAPACITY = 64）