HashMap问题总结

忘是亡心i 2024-03-23 15:42 67阅读 0赞

**目录**

1.HashMap底层实现结构

2.HashMap特点

3.HashMap扩容机制

4.HashMap存取原理

5.HashMap内部的bucket数组长度为什么一直都是2的整数次幂？

6.HashMap默认的bucket数组是多大？

7.HashMap什么时候开辟bucket数组占用内存？

8.桶中的元素链表何时转换为红黑树，什么时候转回链表，为什么要这么设计？

9.Java 8中为什么要引进红黑树，是为了解决什么场景的问题？

10.HashMap如何处理key为null的键值对？

11.HashMap的hash函数为什么这么设计？

12.HashMap为什么线程不安全？

13.怎样使HashMap的线程安全？

14.ConcurrentHashMap是如何保证线程安全的？

15.HashTable和HashMap有什么区别？

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

HashMap，中文名哈希映射，HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。

#### 1.HashMap底层实现结构 ####

HashMap在Jdk1.7以前是基于数组+链表来实现，在Jdk1.8以后是基于数组+链表+红黑树来实现。

#### 2.HashMap特点 ####

key不能重复，可以为null，线程不安全。

#### 3.HashMap扩容机制 ####

HashMap的默认容量为16，默认的负载因子为0.75，当HashMap中元素个数超过容量乘以负载因子的个数时，就创建一个大小为前一次两倍的新数组，再将原来数组中的数据复制到新数组中。当数组长度到达64且链表长度大于8时，链表转为红黑树。

（1-3参考文章：[2023年春招必备Java八股文（通俗易懂）\_十八岁讨厌Java的博客-CSDN博客][2023_Java_Java_-CSDN]）

#### 4.HashMap存取原理 ####

1）通过[hash][](Object key)算法得到key的hash值；  
2）判断table是否为null或者长度为0，如果是执行resize()进行扩容；  
3）通过hash值以及table[数组长度][Link 1]（源码：(index=table.length - 1) & key.hash()）得到插入的数组索引i，判断数组table\[i\]是否为空或为null；  
4）如果table\[i\] == null，直接新建节点添加，转向 8），如果table\[i\]不为空，转向 5）；  
5）判断table\[i\]的首个元素是否和key一样，如果相同直接覆盖value，这里的相同指的是hashCode以及equals，否则转向 6）；  
6）判断table\[i\] 是否为treeNode，即table\[i\] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转7）；  
7）遍历table\[i\]，判断链表长度是否大于8，满足判断条件转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；  
8）插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

（4参考文章：[hashmap的存取原理\_hashmap存取原理\_DevenPhone的博客-CSDN博客][hashmap_hashmap_DevenPhone_-CSDN]）

#### 5.HashMap内部的bucket数组长度为什么一直都是2的整数次幂？ ####

这样做有两个好处，第一，可以通过(table.length - 1) & key.hash()这样的位运算快速寻址，第二，在HashMap扩容的时候可以保证同一个桶（桶指bucket数组）中的元素均匀地散列到新的桶中，具体一点就是同一个桶中的元素在扩容后一半留在原先的桶中，一半放到了新的桶中。

#### 6.HashMap默认的bucket数组是多大？ ####

默认是16，即时指定的大小不是2的整数次幂，HashMap也会找到一个最近的2的整数次幂来初始化桶数组。

#### 7.HashMap什么时候开辟bucket数组占用内存？ ####

在Jdk 1.8中，在调用new HashMap()的时候并没有分配数组堆内存，只是做了一些参数校验，初始化了一些常量。在第一次put元素的时候调用resize方法才开辟bucket数组占用内存。

#### 8.桶中的元素链表何时转换为红黑树，什么时候转回链表，为什么要这么设计？ ####

当同一个桶中的元素数量大于等于8的时候元素中的链表转换为红黑树，反之，当桶中的元素数量小于等于6的时候又会转为链表，这样做的原因是避免红黑树和链表之间频繁转换，引起性能损耗。

#### 9.Java 8中为什么要引进红黑树，是为了解决什么场景的问题？ ####

引入红黑树是为了避免hash性能急剧下降，引起HashMap的读写性能急剧下降的场景，即hash值相等的元素较多时，通过key值依次查找的效率较低。链表长度大于8时引入红黑树可以加快后面元素检索速度。正常情况下，一般是不会用到红黑树的，在一些极端场景下，假如客户端实现了一个性能拙劣的hashCode方法，可以保证HashMap的读写复杂度不会低于O(lgN)**。**

#### 10.HashMap如何处理key为null的键值对？ ####

放置在桶数组中下标为0的桶中。

#### 11.HashMap的hash函数为什么这么设计？ ####

java 8 HashMap的hash函数代码如下：

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

计算索引时，key的hash值要table.length - 1做与运算，那就意味着计算出来的hash值只有低位有效，这样会加大碰撞几率，因此在hash函数中让高16位与低16位做异或，可以使低位保留部分高位信息，减少哈希碰撞。java 7 中的hash函数使用更复杂的异或计算，但与java 8 hash函数的目的一样，为了使哈希值的低位保留部分高位信息，减少哈希碰撞。

（5-11参考文章：[HashMap底层实现原理概述\_fedorafrog的博客-CSDN博客][HashMap_fedorafrog_-CSDN]）

#### 12.HashMap为什么线程不安全？ ####

HashMap的线程不安全体现在会造成死循环、数据丢失、数据覆盖等问题。其中死循环和数据丢失是在JDK1.7中出现的问题，在JDK1.8中已经得到解决，但是JDK1.8中仍会有数据覆盖这样的问题。总之，HashMap的线程不安全主要体现在两个方面：

（1）在JDK1.7中，当并发执行扩容操作时会造成环形链和数据丢失的情况。

（2）在JDK1.8中，在并发执行put操作时会发生数据覆盖的情况。

（12参考文章：[HashMap为什么线程不安全？\_Heloise\_yangyuchang的博客-CSDN博客][HashMap_Heloise_yangyuchang_-CSDN]）

#### 13.怎样使HashMap的线程安全？ ####

使HashMap线程安全有三种方式：ConcurrentHashMap、Collections.SynchronizedMap、HashTable。

（1）HashTable的线程安全原理与Collections.SynchronizedMap的线程安全原理相似：所有方法都用Synchronized修饰。性能较差。

（2）ConcurrentHashMap安全原理：通过对头节点加锁来保证线程安全。性能较好。

（13参考文章：[Hashmap如何保证线程安全\_hashmap怎么保证线程安全\_马腾.♔的博客-CSDN博客][Hashmap_hashmap_._-CSDN]）

#### 14.ConcurrentHashMap是如何保证线程安全的？ ####

（1）ConcurrentHashMap在JDK 1.7中使用的数组+链表的结构，其中数组分为两类，大树组Segment 和 小数组 HashEntry，而加锁是通过给Segment添加ReentrantLock重入锁来保证线程安全的。

（2）ConcurrentHashMap在JDK1.8中使用的是数组+链表+红黑树的方式实现，它是通过 CAS 或者 synchronized 来保证线程安全的，并且缩小了锁的粒度，查询性能也更高。

（14参考文章：[ConcurrentHashMap是如何保证线程安全的？\_corrunthashmap线程安全\_Tom弹架构的博客-CSDN博客][ConcurrentHashMap_corrunthashmap_Tom_-CSDN]）

#### 15.HashTable和HashMap有什么区别？ ####

（1）HashTable的每个方法都用synchronized修饰，因此是线程安全的，但同时读写效率很低

（2）HashTable的Key不允许为null

（3）HashTable只对key进行一次hash，HashMap进行了两次Hash

（4）HashTable底层使用的数组加链表  
（15参考文章：[2023年春招必备Java八股文（通俗易懂）\_十八岁讨厌Java的博客-CSDN博客][2023_Java_Java_-CSDN]）

[2023_Java_Java_-CSDN]: https://blog.csdn.net/w20001118/article/details/125724647
[hash]: https://so.csdn.net/so/search?q=hash&spm=1001.2101.3001.7020
[Link 1]: https://so.csdn.net/so/search?q=%E6%95%B0%E7%BB%84%E9%95%BF%E5%BA%A6&spm=1001.2101.3001.7020
[hashmap_hashmap_DevenPhone_-CSDN]: https://blog.csdn.net/u010898585/article/details/105610242
[HashMap_fedorafrog_-CSDN]: https://blog.csdn.net/fedorafrog/article/details/115478407
[HashMap_Heloise_yangyuchang_-CSDN]: https://blog.csdn.net/qq_35958391/article/details/125015642
[Hashmap_hashmap_._-CSDN]: https://blog.csdn.net/weixin_42396189/article/details/128830923
[ConcurrentHashMap_corrunthashmap_Tom_-CSDN]: https://blog.csdn.net/gupaoedu_tom/article/details/124449788