听说你看过HashMap源码，来面试下这几个问题

小灰灰 2023-06-25 10:26 14阅读 0赞

**HashMap源码解析系列文章**  
[JDK8 HashMap源码行级解析 史上最全最详细解析][JDK8 HashMap_]  
[JDK8 HashMap源码行级解析 红黑树操作 史上最全最详细图解][JDK8 HashMap_ _]  
[JDK8 HashMap源码 putMapEntries解析][JDK8 HashMap_ putMapEntries]  
[JDK8 HashMap源码 clone解析][JDK8 HashMap_ clone]  
[深入理解HashMap：那些巧妙的位操作][HashMap]  
[听说你看过HashMap源码，来面试下这几个问题][HashMap 1]

# HashMap的主要成员都有哪些？ #

1.  `Entry<K,V>[] table`。这个Entry类型的数组存储了HashMap的真正数据。
2.  `size`大小。代表HashMap内存储了多少个映射。
3.  `capacity`容量。实际上HashMap没有一个成员叫capacity，它是作为table这个数组的大小而隐式存在。
4.  `threshold`阈值和`loadFactor`装载因子。threshold是通过capacity \* loadFactor得到的。当size超过threshold时（刚好相等时不会扩容），HashMap会扩容再哈希。
5.  `entrySet`、`keySet`和`values`这三个都是一种视图，真正的数据都来自`table`。

# HashMap的底层原理？ #

*  底层使用数组+链表+红黑树的数据结构来存储映射，每一个数组元素代表一个哈希桶，一个哈希桶要么是单链表结构，要么是红黑树结构。
 *  由于数组可以随机存取（取下标操作）和key的hashCode()方法，使得一个映射我们可以快速定位到它所在的哈希桶位置。这正是HashMap快的原因。
 *  对数组取下标会得到该哈希桶的第一个节点，由于哈希桶内所有节点都用next指针串联了起来，所以得到了第一个节点就代表可以遍历桶内所有节点。
 *  添加新元素时，如果哈希桶里没有元素，那么直接放置。如果哈希桶里已经有元素了，则代表此时发生了哈希碰撞：新元素会与桶内所有元素进行equals比较，如果与所有元素都不相等，那么则添加该新元素；如果发现了equal的元素，那么执行替换操作。

# 为什么HashMap的容量是2的幂？ #

这是为了能够通过`&`位操作来得到一个映射的所在table数组下标。

正常来说，通过`key的hash值 % table.length`可以得到key所应该在的数组下标，但如果这个容量是2的幂，那么 数组下标可以通过`key的hash值 & (table.length-1)`得到。位操作肯定比取余操作快多了。

# HashMap的特性？ #

1.  通过hash实现了对映射的快速存取。key可以有一个null，value可以重复。
2.  非同步，是线程不安全的。单线程下，使用HashMap相比使用Hashtable效率更高。
3.  底层是hash表，所以不保证顺序。因为每次resize都会重新分配元素到各个哈希桶。

# hashMap中put是如何实现的？ #

1.  首先判断table成员是否初始化，如果没有，则调用resize。
2.  通过传入键值对的`key`的hashCode和容量，马上得到了该映射所在的table数组下标。并通过数组的取下标操作，得到该哈希桶的头节点。
3.  如果没有发生哈希碰撞（头节点为null），那么直接执行**新增操作**。
4.  如果发生了哈希碰撞（头节点不为null），那么分为两种情况：
    
    1.  如果与桶内某个元素`==`返回true，或者equals判断相同，执行**替换操作**。
    2.  如果与桶内所有元素判断都不相等，执行**新增操作**。
5.  **新增操作**做完后会有两个判断：
    
    1.  如果哈希桶是单链表结构，且桶内节点数量超过了TREEIFY\_THRESHOLD(8)，且size大于等于了MIN\_TREEIFY\_CAPACITY(64)，那么将该哈希桶转换为红黑树结构。
    2.  如果新增后size大于了threshold，那么调用resize。

# hashMap中resize是如何实现的？ #

1.  当table还没初始化时，使用默认容量16或者通过用户给定容量算出一个2的幂，来作为table的大小。
2.  当table已经初始化了，那么扩容成旧容量的2倍。如果新容量为最大容量，则将阈值设为int最大值。
3.  当table已经初始化，且旧容量已经是最大容量，那么table不再进行扩容。

哈希桶内的各个元素，经过扩容后，它的可能的table下标要么在`原table下标`，要么在`原table下标 + 旧容量`。正是因为容量永远为2的幂，才使得扩容操作如此简单。

# hashMap中get是如何实现的？ #

1.  通过传入映射的`key`的hashCode和容量，马上得到了该映射所在的table数组下标。并通过数组的取下标操作，得到该哈希桶的头节点。
2.  如果头节点为null，那么代表没有该映射。
3.  如果头节点不为null，且传入映射与桶内某个映射`==`返回true，或者equals判断相同，那么代表找到了该映射。
4.  如果头节点不为null，且传入映射与桶内每个映射都判定不相等，那么代表没有该映射。

# HashMap中hash函数是怎么实现的？为什么这么实现？ #

将`key`的hashCode与该hashCode的无符号右移16位，异或起来得到的。

因为当table的size比较小时，能影响到table下标的，只有哈希值几个低位bit，这很可能会加剧哈希碰撞。但这样实现后，哈希值的高16位bit保持不变，低16位则受到高16位的“扰动”而发生改变，这样就**使得高位bit也能影响table下标，减少哈希碰撞。**

## 为什么hash函数使用异或 ##

`key`的hashCode只要有一个bit发生变化，hash函数的返回值也会跟着变化，用以减少哈希碰撞。

# HashMap的key应该如何设计？不这么设计的后果是什么？ #

如果key重写了hashCode方法，那么也应该重写equals方法。

如果key只重写了hashCode方法，却没有重写equals方法。那么会造成map里会存在重复的我们认为“相同”的键值对在里面（一般是指，两个对象的成员是相同的）。因为如果添加了相同元素，根据put过程则发生哈希碰撞，本来这个相同元素不应该新增，但由于原始Object的equals方法逻辑使用`==`判断，所以只要地址值不同就肯定能添加进去。

如果key只重写了equals方法，却没有重写hashCode方法。那么也会造成map里会存在重复的我们认为“相同”的键值对在里面。因为使用了原始的hashCode了，有些该发生的哈希碰撞也就不会发生了，都不在一个哈希桶了，即使我们认为是“相同”的，也不会去调用你重写的equals方法的。

# 传统hashMap的缺点(为什么引入红黑树？) #

*  JDK8以前，hashMap的底层实现是数组+链表。即使key的hash函数做的再好，也很难做到元素均匀分布到各个哈希桶里，更何况有时候你自己重写的hashCode方法还很烂。
 *  当一个桶内有大量元素时，那么查找效率则为 O ( n ) O(n) O(n)。但如果这个哈希桶的结构是红黑树，那么查找效率为 O ( l o g 2 n ) O(log\_2n) O(log2n)，查找效率得到优化。

# 在使用HashMap的过程中应该注意些什么问题? #

*  resize扩容操作是很影响效率的，所以你能提前知道将要存入的映射的数量，那么最好直接在构造器中传入你想好的这个容量。
 *  自定义的类作为key，hashCode方法和equals方法要么都不重写，要么都重写。这两个方法的重写逻辑应该都依靠同样的成员变量。
 *  自定义的类作为key，作为hashCode方法和equals方法的逻辑依赖的成员变量，应该设为final，来防止属性被改变。
 *  尽量使用String、Integer 这样的包装类来作为key，因为它们有标准的hashCode和equals重写实现

# 其他 #

本文基于JDK1.8的HashMap源码。

[JDK8 HashMap_]: https://blog.csdn.net/anlian523/article/details/103435732
[JDK8 HashMap_ _]: https://blog.csdn.net/anlian523/article/details/103649200
[JDK8 HashMap_ putMapEntries]: https://blog.csdn.net/anlian523/article/details/103639094
[JDK8 HashMap_ clone]: https://blog.csdn.net/anlian523/article/details/103797056
[HashMap]: https://blog.csdn.net/anlian523/article/details/103812105
[HashMap 1]: https://blog.csdn.net/anlian523/article/details/103745773