HashMap的几个常考的[ 面试问题 ]和[ 回答思路，底层分析 ]

系统管理员 2023-09-28 19:56 9阅读 0赞

**目录**

1.哈希桶在扩容的时候要注意什么？

2.两个对象的hashcode一样，那么equals一定一样吗？

3.两个对象的equals一样，那么hashcode一定一样吗？

4.HashMap map = new HashMap<>();底层的数组多大？,>

5.HashMap map = new HashMap<>(25);底层的数组多大？,>

6.讲一下你知道或者了解的HashMap的源码（put 方法分析）？

7.拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？

8.如何解决 hash 冲突?

--------------------

### **1.哈希桶在扩容的时候要注意什么？** ###

思路：遍历每个key值下的每个链表，要注意对链表的每个结点都要**重新哈希**，再进行头插；

--------------------

### **2.两个对象的hashcode一样，那么equals一定一样吗？** ###

### **3.两个对象的equals一样，那么hashcode一定一样吗？** ###

思路（2，3问题统一思路）：问题2是不一定，问题3是一定，打个比方，假设你要在字典上查找“电脑”这个词（哈希桶），首先肯定要先找到“电”这个字（哈希桶的每个元素——hashcode），找到“电”这个字，下面肯定有很多词汇例如：电视，电极，电影，电脑......等等（哈希桶每个元素下的链表），而你需要要找到对应的“电脑”这个词汇（比较对应的结点——equals）

--------------------

### **4.HashMap<String, String> map = new HashMap<>();底层的数组多大？** ###

思路：数组大小为零，如下图，构造方法中并没有初始化数组大小，所以默认是0；

![7c2ae4a745324fc0b1af521cadd87bb0.png][]

第一次put时将容量变成了16，原因如下图:

![77884cdff7274d56aae21c880b1f47c6.png][]

如果第一次put，oldTab == null为真，使oldCap > 0条件为假，同时oldThr等于0不满足>0的条件，走了else，可以看到newCap被赋值为：DEFAULT\_INITIAL\_CAPACITY；大小是多少呢？如下图：

![2fd136f9a284473dac26ae4d9320bcb7.png][]

1 << 4也就是2的4次方为16，**所以回答上面问题：第一次put的容量为16。**

--------------------

### **5.HashMap<String, String> map = new HashMap<>(25);底层的数组多大？** ###

思路：如果源码不想一句一句给面试官分析，可以直接说一下下图中绿字的注释，意思是：返回给定目标容量的 2 个大小的幂；也就是说给定的容量是cap，你会返回一个这个容量大小的一个2个大小的幂，**注意求出的这个数的需要对cap向上取整**，（如果cap大小是10，2的3次方为8，2的4次方为16，按理来说8更接近10，但是需要向上取整，所以返回16）；

综上，此题底层数组大小为32。

![b93962000de84a609f4849d0404929b4.png][]

--------------------

### **6.讲一下你知道或者了解的HashMap的源码（put 方法分析）？** ###

思路：可以给面试官分析一下 put 的源码，如下图：

![0f51b6400f884186865b2b34850f95a7.png][]

记得对putVal展开分析：

//put源码分析：
    
    //这里通过putVal调用方法
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            //判断table是否初始化，若未初始化，则进行初始化
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            //计算存储索引的位置，若没有元素，直接赋值
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
                Node<K,V> e; K k;
                //若结点存在，则执行赋值操作
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                //判断链表是否为红黑树
                else if (p instanceof TreeNode)
                    //红黑树对象操作
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
                    //是链表
                    for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {
                            p.next = newNode(hash, key, value, null);
                            //如果链表长度大于等于(8 - 1)，则将链表转化为红黑树存储
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        //如果key值存在，直接覆盖
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            //记录修改次数
            ++modCount;
            //判断是否需要扩容
            if (++size > threshold)
                resize();
            //空操作
            afterNodeInsertion(evict);
            return null;
        }

具体的如下过程：

1.  首先获取底层数组对象和长度，若对象为 null 或 长度为 0，则调用 resize() 进行扩容，获取新的数组对象，并获取长度大小（第一次扩容大小为 2 的 4 次方，也就是 16）.
2.  判定数组指定索引下的结点是否为 null ，若为 null 则 new 出一个单向链表赋值给这个数组指定索引下的节点.
3.  若不为 null， 则继续做以下三个判断（a,b,c 三个判断）.
4.  (a) 首先对 key 值进行匹配，如果能找到这个 key 值，直接插入新对象数据.
5.  (b) 若匹配失败，则匹配类型是否为 TreeNode ，若判定成功，则在红黑树中查找符合条件的节点调用插入的相关方法(putTreeVal).
6.  (c) 若以上判断全部失败，则进行此操作，向单向链表中添加数据，若单向链表的长度大于等于一定数字的时候（在 jdk1.8 的时候是大于等于 8），则将其转化为红黑树保存。
7.  最后判定数组大小是否需要扩容，若需要，则继续调用 resize() 方法.

###  ###

--------------------

### 7.**拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？** ###

选择红黑树，是为了解决二叉搜索树缺陷，**二叉搜索树在特殊情况下回变成线性结构**，查找会很慢，而**红黑树插入新数据通过左旋，右旋、变色这些操作来保持平衡，大大加快了查找速率**，即使为了保持 “平衡” 是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

--------------------

### 8.如何解决 hash 冲突? ###

有以下两种方法：

**闭散列法：**也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以 把key存放到冲突位置中的“下一个” 空位置中去。

**开散列法（重点掌握）：**又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子 集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中，如下图

![7f706338d4834d8bab80344fba7e6c69.png][]

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。

![abc9827409c34dae807ce9cf0233d2ae.gif][]

[7c2ae4a745324fc0b1af521cadd87bb0.png]: https://img-blog.csdnimg.cn/7c2ae4a745324fc0b1af521cadd87bb0.png
[77884cdff7274d56aae21c880b1f47c6.png]: https://img-blog.csdnimg.cn/77884cdff7274d56aae21c880b1f47c6.png
[2fd136f9a284473dac26ae4d9320bcb7.png]: https://img-blog.csdnimg.cn/2fd136f9a284473dac26ae4d9320bcb7.png
[b93962000de84a609f4849d0404929b4.png]: https://img-blog.csdnimg.cn/b93962000de84a609f4849d0404929b4.png
[0f51b6400f884186865b2b34850f95a7.png]: https://img-blog.csdnimg.cn/0f51b6400f884186865b2b34850f95a7.png
[7f706338d4834d8bab80344fba7e6c69.png]: https://img-blog.csdnimg.cn/7f706338d4834d8bab80344fba7e6c69.png
[abc9827409c34dae807ce9cf0233d2ae.gif]: https://img-blog.csdnimg.cn/abc9827409c34dae807ce9cf0233d2ae.gif