【Java集合面试宝典】HashMap的put流程和特性？HashMap的扩容机制?原理— day08

傷城~ 2023-09-25 19:06 12阅读 0赞

## **目录** ##

数组和链表分别适用于什么场景，为什么？

数组

链表

List和Set的区别

List和Map、Set的区别

HashMap 、HashTable 和TreeMap有什么区别？

hashmap的特性

HashMap和HashTable有什么区别？（必会）

JDK1.7到1.8HashMap发生了什么变化(底层)

谈谈ConcurrentHashMap的扩容机制

hashMap 中什么时候需要进行扩容，扩容方法 resize()又是如何实现的？

HashMap的扩容机制原理

HashMap的put方法

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

## **数组和链表分别适用于什么场景，为什么？** ##

数组和链表都是数据结构中常见的数据类型，它们各自适用于不同的场景。

> #### **数组** ####

数组是一种基本的数据类型，它是一个有序的、固定大小的数据集合，其中每个元素都有一个唯一的索引。数组的优点在于它的随机访问速度非常快，因为它的元素在内存中是连续存储的，可以通过索引快速访问。

适用场景：

数组适合查询多，增删少的场景；

> #### 链表 ####

链表是一种基于指针的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表的优点在于它可以动态地添加、删除元素，不需要像数组一样预先分配固定大小的空间。

适用场景：

(1) 需要频繁插入或删除元素，因为链表的插入和删除操作只需要修改节点之间的指针，效率较高；

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

## **List和Set的区别** ##

List：有序 按对象进入的顺序保存对象 可重复 允许多个Null元素 可以使用迭代器取出所有的元素 然后再逐一遍历各个元素 还可以使用get获取指定下标的元素

Set：无序 不可重复 最多允许一个Null元素 只能使用迭代器取出所有的元素 然后在逐一遍历

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

## **List和Map、Set的区别** ##

List和Set是存储单列数据集合，Map是存储键值对这样的双列数据的集合

List中存储的数据是有序的，可以为空，并且值允许重复。

Map中存储的数据是无序的 它的键不允许重复的 但是值是允许重复的；可一个空键、多个空值。

Set中存储的数据是无顺序的，并且不允许重复，只有一个空元素。元素在集合的位置是由元素的hashcode决定 即位置是固定的（Set集合是根据hashcode来进行数据存储的 所以位置是

固定的但是这个位置不是用户可以控制的 所以对于用户来说set中的元素还是无序的）

####  ####

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

## **HashMap 、HashTable 和TreeMap有什么区别？** ##

![5cc4e122a391451facc74891b64c9a02.png][]

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

## **hashmap的特性** ##

1.  允许空键和空值（但空键只有一个，且放在第一位）
2.  元素是无序的，而且顺序会不定时改变
3.  key 用 Set 存放，所以想做到 key 不允许重复，key 对应的类需要重写 hashCode 和 equals 方法。
4.  底层实现是 链表数组，JDK 8 后又加了红黑树。

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

## **HashMap和HashTable有什么区别？（必会）** ##

区别：

（1）HashMap是非线程安全的，HashTable是线程安全的，内部的方法基本都经过synchronized修饰。

（2）因为同步、哈希性能等原因，HashMap的性能优于HashTable

（3） HashMap允许有null值的存在,在HashTable不允许有null值

（4）HashMap默认初始化数组的大小为16，HashTable为11。前者扩容时乘2，使用位运算取得哈希，效率高于取模。而后者为乘2加1，都是素数和奇数，这样取模哈希结果更均匀。

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

## **JDK1.7到1.8HashMap发生了什么变化(底层)** ##

1.7底层是数组+链表 1.8底层是数组+链表+红黑树 加入红黑树的目的是提高HashMap插入和查询的整体效率

1.7链表插入使用的是头插法 1.8链表插入使用的是尾插法 因为1.8插入key和value需要判断链表元素个数 所以需要遍历链表统计元素个数 正好使用尾插法

1.7的哈希算法比较复杂 存在各种右移和与运算 1.8进行了简化 因为复杂的哈希算法的目的是提高散列性 来提供HashMap的整体效率 而1.8中新增了红黑树 所以可以适当简化哈希算法 节省CPU资源。

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

## **谈谈ConcurrentHashMap的扩容机制** ##

1.7版本

1.  1.7版本的ConcurrentHashMap是基于Segment分段实现的
2.  每个Segment相当于一个小型的HashMap
3.  每个Segment内部会进行扩容 和HashMap扩容逻辑类似
4.  先生产新的数组 然后转移元素到新数组中
5.  扩容的判读也是每个Segment内部单独判断的 判断是否超过阈值

1.8版本

1.  1.8版本的ConcurrentHashMap不再基于Segment实现
2.  当某个线程进行put时 如果发现ConcurrentHashMap正在进行扩容那么该线程一起进行扩容
3.  如果某个线程put时 发现没有正在进行扩容 则将key-value添加到ConcurrentHashMap中 然后判断是否超过阈值 超过了则进行扩容
4.  扩容之前先生成一个新的数组
5.  在转移元素时 先将原数组分组 将每组分给不同的线程进行元素的转移 每个线程负责一组或多组元素转移工作

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

## **hashMap 中什么时候需要进行扩容，扩容方法 resize()又是如何实现的？** ##

**调用场景：**

1.初始化数组 table

2.当数组 table 的 size 达到阙值时进行扩容

**实现过程：**

通过判断旧数组的容量是否大于0来判断数组是否初始化过。

l如果小于0：进行初始化,判断是否调用无参构造器。

l如果大于0: 进行扩容，扩容成两倍(小于最大值的情况下)，之后在进行将元素重新进行与运算复制到新的散列表中。

**概括的讲：**

扩容需要重新分配一个新数组，新数组是老数组的2倍长，然后遍历整个老结构，把所有的元素挨个重新hash分配到新结构中去。

PS：可见底层数据结构用到了数组，到最后会因为容量问题都需要进行扩容操作。

####  ####

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

## **HashMap的扩容机制原理** ##

当new HashMap():底层没有创建数组，首次调用 put()方法示时，底层创建长度为 16 的数组，jdk8 底层的数组是：Node\[\],而非 Entry\[\]，用数组容量大小乘以加载因子得到一个值，一旦数组中存储的元素个数超过该值就会调用 rehash() 方法将数组容量增加到原来的两倍，专业术语叫做扩容。在做扩容的时候会生成一个新的数组，原来的所有数据需要重新计算哈希码值重新分配到新的数组，所以扩容的操作非常消耗性能. **默认的负载因子大小为 0.75**，数组大小为 16。也就是说，默认情况下，那么当 HashMap中元素个数超过 16\*0.75=12 的时候，就把数组的大小扩展为 2\*16=32，即扩大一倍。

在我们 Java 中任何对象都有 hashcode，hash 算法就是通过 hashcode 与自己进行向右位移 16 的异或运算。这样做是为了计算出来的 hash 值足够随机，足够分散，还有产生的数组下标足够随机。

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

## **HashMap的put方法** ##

HashMap是Java中常用的散列表数据结构，是基于 Hash 算法实现的。们通过 **put(key,value)存储**，get(key)来获取。当传入 key 时，HashMap 会根据 key.hashCode() 计算出 hash 值，根据 hash 值将 value 保存在 bucket里。当计算出的 hash 值相同时，我们称之为 hash 冲突，HashMap 的做法是用链表和红黑树存储相同 hash 值的 value。当 hash 冲突的个数比较少时，使用链表否则使用红黑树。

如果添加新节点后，桶中节点的**数量超过了阈值（默认为0.75）**，则需要进行扩容操作。扩容操作会将桶的数量翻倍，并将原来的节点重新分配到新的桶中。

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

[5cc4e122a391451facc74891b64c9a02.png]: https://img-blog.csdnimg.cn/5cc4e122a391451facc74891b64c9a02.png