Java面试题之HashMap

前言

本来想着给自己放松一下，刷刷博客，突然被几道面试题难倒！说说Hashtable 与 HashMap 的区别？HashMap 中的 key 我们可以使用任何类作为 key 吗？HashMap 的长度为什么是 2 的 N 次方呢？HashMap 与 ConcurrentHashMap 的异同？红黑树有哪几个特征？似乎有点模糊了，那就大概看一下面试题吧。好记性不如烂键盘

*** 12万字的java面试题整理 ***

说说Hashtable 与 HashMap 的区别

1. 都实现了 Map、Cloneable、Serializable（当前 JDK 版本 1.8）。
2. Hashtable 中大部分 public 修饰普通方法都是synchronized 字段修饰的，是线程安全的，HashMap 是非线程安全的。
3. Hashtable 的 key 不能为 null，value 也不能为 null，这个可以从 Hashtable 源码中的 put 方法看到，判断如果 value 为 null 就直接抛出空指针异常，在 put 方法中计算 key 的 hash 值之前并没有判断 key 为 null 的情况，那说明，这时候如果 key 为空，照样会抛出空指针异常。
4. HashMap 的 key 和 value 都可以为 null。在计算 hash 值的时候，有判断，如果key==null ，则其 hash=0 ；至于 value 是否为 null，根本没有判断过。
5. Hashtable 直接使用对象的 hash 值。hash 值是 JDK 根据对象的地址或者字符串或者数字算出来的 int 类型的数值。然后再使用除留余数法来获得最终的位置。然而除法运算是非常耗费时间的，效率很低。HashMap 为了提高计算效率，将哈希表的大小固定为了 2 的幂，这样在取模预算时，不需要做除法，只需要做位运算。位运算比除法的效率要高很多。
6. 默认情况下，初始容量不同，Hashtable 的初始长度是 11，之后每次扩充容量变为之前的2n+1（n 为上一次的长度）而 HashMap 的初始长度为 16，之后每次扩充变为原来的两倍。
   另外在 Hashtable 源码注释中有这么一句话：

Hashtable is synchronized. If a thread-safe implementation is not needed, it is
recommended to use HashMap in place of Hashtable . If a thread-safe highly-
concurrent implementation is desired, then it is recommended to useConcurrentHashMap in place of Hashtable

大致意思：Hashtable 是线程安全，推荐使用 HashMap 代替 Hashtable；如果需要线程安全高并发的话，推荐使用 ConcurrentHashMap 代替 Hashtable。
这个回答完了，面试官可能会继续问：HashMap 是线程不安全的，那么在需要线程安全的情况下还要考虑性能，有什么解决方式？
这里最好的选择就是 ConcurrentHashMap 了，但面试官肯定会叫你继续说一下ConcurrentHashMap 数据结构以及底层原理等。

HashMap 中的 key 我们可以使用任何类作为 key 吗？

平时可能大家使用的最多的就是使用 String 作为 HashMap 的 key，但是现在我们想使用某个自定义类作为 HashMap 的 key，那就需要注意以下几点：

• 如果类重写了 equals 方法，它也应该重写 hashCode 方法。
• 类的所有实例需要遵循与 equals 和 hashCode 相关的规则。
• 如果一个类没有使用 equals，你不应该在 hashCode 中使用它。
• 咱们自定义 key 类的最佳实践是使之为不可变的，这样，hashCode 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保 hashCode 和 equals 在未来不会改变，这样就会解决与可变相关的问题了。

HashMap 的长度为什么是 2 的 N 次方呢？

为了能让 HashMap 存数据和取数据的效率高，尽可能地减少 hash 值的碰撞，也就是说尽量把数据能均匀的分配，每个链表或者红黑树长度尽量相等。

我们首先可能会想到 % 取模的操作来实现。下面是回答的重点哟：

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

这就是为什么 HashMap 的长度需要 2 的 N 次方了。

HashMap 与 ConcurrentHashMap 的异同

1. 都是 key-value 形式的存储数据；
2. HashMap 是线程不安全的，ConcurrentHashMap 是 JUC 下的线程安全的；
3. HashMap 底层数据结构是数组 + 链表（JDK 1.8 之前）。JDK 1.8 之后是数组 + 链表 + 红黑树。当链表中元素个数达到 8 的时候，链表的查询速度不如红黑树快，链表会转为红黑树，红黑树查询速度快；
4. HashMap 初始数组大小为 16（默认），当出现扩容的时候，以 0.75 * 数组大小的方式进行扩容；
5. ConcurrentHashMap 在 JDK 1.8 之前是采用分段锁来现实的 Segment + HashEntry，Segment 数组大小默认是 16，2 的 n 次方；JDK 1.8 之后，采用 Node + CAS + Synchronized来保证并发安全进行实现

红黑树有哪几个特征？

红黑树是一种自平衡二叉查找树，它在每个节点上增加了一个存储位来表示节点的颜色（红色或黑色），通过颜色的约束和一些旋转操作来保持树的平衡。红黑树具有以下特征：

1. 节点是红色或黑色：每个节点都有一个颜色属性，可以是红色或黑色。
2. 根节点是黑色：树的根节点总是黑色的。
3. 所有叶子节点都是黑色：这里的“叶子”指的是空(null)节点，它们不包含数据，并且被认为是黑色的。
4. 红色节点的子节点必须是黑色：如果一个节点是红色的，则它的两个孩子节点都必须是黑色的。这意味着从任意节点到其子孙叶节点的所有路径上不会有两个连续的红色节点。
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点：这条规则保证了没有一条路径会比其他路径长出两倍以上，从而维持了大致的平衡。
   这些性质确保了红黑树的高度最多为2log(n+1)，其中n是树中节点的数量。因此，红黑树上的基本操作如插入、删除、查找的时间复杂度都是O(log n)，这使得红黑树成为一种高效的平衡二叉搜索树实现方式。

红黑树通过一系列的操作如左旋、右旋以及颜色变化来维护上述性质。当插入或删除节点时，可能会破坏红黑树的性质，这时需要通过调整来恢复这些性质，以确保树仍然满足红黑树的所有特征。