HashMap 面试专题

1、HashMap 的底层结构

①JDK1.8 以前
JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的hashCode 函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
②JDK1.8
相比于之前的版本， JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

拉链法
Java中HashMap 是利用“拉链法”处理 HashCode 的碰撞问题。在调用 HashMap 的 put 方法或 get 方法时，都会首先调用 hashcode 方法，去查找相关的 key，当有冲突时，再调用 equals 方法。hashMap 基于 hasing 原理，我们通过 put 和 get 方法存取对象。当我们将键值对传递给 put 方法时，他调用键对象的 hashCode() 方法来计算 hashCode，然后找到 bucket（哈希桶）位置来存储对象。当获取对象时，通过键对象的 equals() 方法找到正确的键值对，然后返回值对象。HashMap 使用链表来解决碰撞问题，当碰撞发生了，对象将会存储在链表的下一个节点中。hashMap 在每个链表节点存储键值对对象。

2、HashMap 的 put 和 get 方法

map.put(k,v) 实现原理：
①先将键值对 k，v 封装到 Node 对象中；
②底层会调用 k 的 hashCode() 方法得出 hash 值；
③通过哈希函数，将 hash 值转换为数组的下标；
④进行比较：下标位置如果没有任何元素，就把 Node 添加到这个位置上；如果下标位置上有链表，此时会拿着 k 和链表上的每一个节点的 k 用 equals() 方法进行比较（因为 Map 是不可重复的），如果没有重复的新节点就会加到链表末尾，否则则会覆盖有相同 k 值的节点。

map.get(k) 实现原理：
①调用 k 的 hashCode() 方法得出 hash 值；
②通过哈希函数，将 hash 值转换为数组的下标；
③进行比较：下标位置如果没有任何元素，返回 null，如果下标位置上有链表，此时会拿着 k 和链表上的每一个节点的 k 用 equals() 方法进行比较，如果结果都是 false，则返回 null；如果有一个节点用了equals 方法后结果为 true，则返回这个节点的 value 值。

3、为什么重写 equals() 就一定要重写 hashCode() 方法？

如果两个对象相同（即用 equals 比较返回 true），那么它们的 hashCode 值一定要相同！！！！；
如果两个对象不同（即用 equals 比较返回 false），那么它们的 hashCode 值可能相同也可能不同；
如果两个对象的 hashCode 相同（存在哈希冲突），那么它们可能相同也可能不同(即 equals 比较可能是false 也可能是 true)；
如果两个对象的 hashCode 不同，那么他们肯定不同(即用 equals 比较返回 false)。

对于对象集合的判重，如果一个集合含有 10000 个对象实例，仅仅使用 equals() 方法的话，那么对于一个对象判重就需要比较 10000 次，随着集合规模的增大，时间开销是很大的。
但是同时使用哈希表的话，就能快速定位到对象的大概存储位置，并且在定位到大概存储位置后，后续比较过程中，如果两个对象的 hashCode 不相同，也不再需要调用 equals() 方法，从而大大减少了 equals()比较次数。
所以从程序实现原理上来讲的话，既需要 equals() 方法，也需要 hashCode() 方法。那么既然重写了equals()，那么也要重写 hashCode() 方法，以保证两者之间的配合关系。

我们在实际应用过程中，如果仅仅重写了 equals()，而没有重写 hashCode() 方法，会出现什么情况？
字段属性值完全相同的两个对象因为 hashCode 不同，所以在 hashMap 中的 table 数组的下标不同，从而这两个对象就会同时存在于集合中，所以重写 equals() 就一定要重写 hashCode() 方法。

4、HashMap 为什么线程不安全，想要线程安全怎么办？

HashMap 的线程不安全主要体现在下面两个方面：
①在 JDK1.7 中，当并发执行扩容操作时会造成环形链和数据丢失的情况。
②在 JDK1.8 中，在并发执行 put 操作时会发生数据覆盖的情况。

想要线程安全，可以使用 HashTable 或 ConcurrentHashMap。

5、HashMap 与 HashTable 的区别

①线程是否安全： HashMap 是非线程安全的，HashTable 是线程安全的,因为 HashTable 内部的方法基本都经过 synchronized 修饰。（如果要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
② 效率：因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
③对 Null key 和 Null value 的支持： HashMap可以存储 null 的key和value，但null作为键只能有一个，null作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
④初始容量大小和每次扩充容量大小的不同：1、创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16 。之后每次扩充，容量变为原来的 2 倍。2、 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的 tableSizeFor() 方法保证）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小，后面会介绍到为什么是 2 的幂次方。
⑤底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8，将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

6、HashMap 扩容

①首先判断 OldCap 有没有超过最大值；
②当 hashmap 中的元素个数超过 数组大小 * loadFactor 时，就会进行数组扩容，loadFactor 的默认值为 0.75，也就是说，默认情况下，数组大小为 16，那么当 hashmap 中元素个数超过 16 * 0.75=12 的时候，就把数组的大小扩展为 2 * 16=32，即扩大一倍；
③然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知 hashmap 中元素的个数，那么预设元素的个数能够有效的提高 hashmap 的性能。比如说，我们有 1000 个元素 new HashMap(1000), 但是理论上来讲 new HashMap(1024) 更合适，不过上面已经说过，即使是 1000，hashmap 也自动会将其设置为 1024；
但是 new HashMap(1024) 还不是更合适的，因为 0.75*1000 < 1000, 也就是说为了让 0.75 * size > 1000, 我们必须这样 new HashMap(2048)才最合适，既考虑了 & 的问题，也避免了 resize 的问题。

7、为什么是 2 的幂次方

我们首先可能会想到采用 % 取余的操作来实现。但是，重点来了 ：“取余 (%) 操作中如果除数是 2 的幂次则等价于与其除数减一的与 (&) 操作（也就是说 hash % length == hash & (length - 1)的前提是 length 是 2 的 n 次方）。” 并且采用二进制位操作 &，相对于 % 能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方。

8、为什么会产生 Hash 碰撞

key 值无界（任意的），计算出对应的 hash 值有界。

9、红黑树

①为什么使用红黑树，不使用其他的树？
因为红黑树不追求完美的平衡，只要求达到部分平衡，可以减少增删结点时的左旋转和右旋转的次数。

②为什么 JDK8 中 HashMap 底层使用红黑树？
因为链表查询的时间复杂度是 O（n）,红黑树的时间复杂度为 O（logn）。可以提升效率。

③为什么链表长度大于阈值 8 时才将链表转为红黑树？
因为树结点占用的存储空间是普通结点的两倍。因此红黑树比链表更加耗费空间。结点较少的时候，时间复杂度上链表不会比红黑树高太多，但是能大大减少空间。
当链表元素个数大于等于 8 时，链表换成树结构；若桶中链表元素个数小于等于 6 时，树结构还原成链表。因为红黑树的平均查找长度是 log（n）,长度为 8 的时候，平均查找长度为 3，如果继续使用链表，平均查找长度为 8/2=4，这才有转换为树的必要。

④当长度减小的时候红黑树还会转换为链表吗
如果 loHead 不为空，且链表长度小于等于 6 ，则将红黑树转成链表。

10、HashMap 的长度为什么是 2 的幂次方

“取余 (%) 操作中如果除数是 2 的幂次则等价于与其除数减一的与 (&) 操作（也就是说 hash % length == hash & (length - 1)的前提是 length 是 2 的 n 次方）。” 并且采用二进制位操作 &，相对于 % 能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方。

11、ConcurrentHashMap 和 HashTable 的区别

底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采用分段的数组+链表实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用数组+链表的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
实现线程安全的方式（重要）：
① 在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段 (Segment) ，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率,在读的过程中，是不会进行加锁的。 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后对 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；
② Hashtable(同一把锁)：使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈，效率越低。

JDK1.8 的 ConcurrentHashMap（TreeBin：红黑树结点，Node：链表节点）。ConcurrentHashMap 取消了 Segment 分段锁，采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）
synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。