请你说说HashMap底层原理和扩容机制。_

十七_

在1.8之前，HashMap的底层是数组加链表，在1.8之后是数组+链表+红黑树；它的put流程是：基于哈希算法来确定元素位置，当我们向集合存入数据时，他会计算传入的key的哈希值，并利用哈希值取绝对值再根据集合长度取余来确定元素的位置，如果这个位置已经存在其他元素了，就会发生哈希碰撞，则hashmap就会通过链表将这些元素组织起来，如果链表的长度达到8时，就会转化为红黑树，从而提高查询速度。扩容机制：HashMap中数组的默认初始容量为16，当达到默认负载因子0.75时，会以2的指数倍进行扩容。 Hashmap时非线程安全的，在多线程环境下回产生循环死链，因此在多线程环境下建议使用ConcurrentHashMap。

发表于 2022-04-26 15:14:50 回复(9)

测试失败

HashMap的底层是数组+链表+红黑树实现的。集合put时，通过计算key键的哈希值来放入元素。若有key值相同的哈希值时，会通过链表进行存放，链表长度达到8时会开辟红黑树进行存放，以此提高查询效率

发表于 2022-05-03 13:48:16 回复(0)

牛客461097395号

一、数据结构：JDK8后,HashMap底层是采用“数组+链表+红黑树”来实现的，（HashMap是基于哈希算法来确定元素的位置，当我们向集合中存入数据时,它会计算传入的Key的哈希值,并利用哈希值取余来确定位置。若碰撞进一步加剧会创建红黑树来代替这个链表,从而提高对数据的查找速度二、put（）：1. 判断数组,若发现数组为空,则进行首次扩容。 2. 判断头节点,若发现头节点为空,则新建链表节点,存入数组。 3. 判断头节点,若发现头节点非空,则将元素插入槽内。 4. 插入元素后,判断元素的个数,若发现超过阈值则再次扩容。三、触发扩容行为三个条件： 1. 如果数组为空,则进行首次扩容。 2. 将元素接入链表后,如果链表长度达到8,并且数组长度小于64,则扩容。 3. 添加后,如果数组中元素超过阈值,即比例超出限制（默认为0.75）,则扩容。并且,每次扩容时都是将容量翻倍,即创建一个2倍大的新数组,然后再将旧数组中的数组迁移到新数组里。

编辑于 2022-05-11 23:05:36 回复(3)

你看起来很好吃0

在JDK8中,HashMap底层是采用“数组+链表+红黑树”来实现的。 HashMap是基于哈希算法来确定元素的位置（槽）的,当我们向集合中存入数据时,它会计算传入的Key的哈希值,并利用哈希值取余来确定槽的位置。如果元素发生碰撞,也就是这个槽已经存在其他的元素了,则HashMap会通过链表将这些元素组织起来。如果碰撞进一步加剧,某个链表的长度达到了8,则HashMap会创建红黑树来代替这个链表,从而提高对这个槽中数据的查找的速度。 HashMap中,数组的默认初始容量为16,这个容量会以2的指数进行扩容。具体来说,当数组中的元素达到一定比例的时候HashMap就会扩容,这个比例叫做负载因子,默认为0.75。 Put()方法的执行过程中,主要包含四个步骤： 1. 判断数组,若发现数组为空,则进行首次扩容。 2. 判断头节点,若发现头节点为空,则新建链表节点,存入数组。 3. 判断头节点,若发现头节点非空,则将元素插入槽内。 4. 插入元素后,判断元素的个数,若发现超过阈值则再次扩容。其中,第3步又可以细分为如下三个小步骤： 1. 若元素的key与头节点一致,则直接覆盖头节点。 2. 若元素为树型节点,则将元素追加到树中。 3. 若元素为链表节点,则将元素追加到链表中。追加后,需要判断链表长度以决定是否转为红黑树。若链表长度达到8、数组容量未达到64,则扩容。若链表长度达到8、数组容量达到64,则转为红黑树。扩容机制向HashMap中添加数据时,有三个条件会触发它的扩容行为： 1. 如果数组为空,则进行首次扩容。 2. 将元素接入链表后,如果链表长度达到8,并且数组长度小于64,则扩容。 3. 添加后,如果数组中元素超过阈值,即比例超出限制（默认为0.75）,则扩容。并且,每次扩容时都是将容量翻倍,即创建一个2倍大的新数组,然后再将旧数组中的数组迁移到新数组里。由于HashMap中数组的容量为2^N

发表于 2022-05-07 19:45:06 回复(0)

慕小言

在jdk1.8之前，Hashmap的底层实现是数组+链表的形式，在jdk1.8之后，底层实现在原来的数组+链表的基础上增加了红黑树，当向hashmap中put元素的时候，底层数组进行初始化，默认初始化值为16，负载因子为0.75，当数组需要扩容的时候，长度变为原来的2倍，然后使用自定义的哈希算法来计算传入的key值的哈希值，对该哈希值进行位运算以获取当前元素的位置并且返回，如果该位置已经存在的话，则将这些元素放到该位置的桶中形成链表，如果桶中的元素超过8，就会对链表进行树形化，使其成为红黑树，如果数组的长度超过64，也会进行树形化，成为红黑树。hashmap的键和值都可以为空，是线程不安全的。

发表于 2022-08-29 21:48:04 回复(0)

G1ng3r

在1.7中，hashmap底层采用数组+链表的形式实现，在1.8中底层采用数组+链表+红黑树的数据结构实现。hashmap的put方法流程： 1.根据key的hashcode进行移位和按位与操作计算二次hash。这里用移位和按位与操作计算二次hash最主要的原因是使得高位也参加运算，使hash分布更均匀，进而减少hash冲突概率，同事移位和与操作本身是很高效的运算。 2.得到key的二次hash之后，就可以确定key在数组中的索引下标。这时候先判断数组是否为空，也就是说hashmap中的数组是惰性初始化的（有点懒汉式的意思）。如果数组不为空，且没有发生hash冲突，创建Node节点放到数组对应下标。 3.如果发生了hash冲突，就意味着当前节点要挂到链表上或者红黑树上，遍历链表或者红黑树，如果遍历的节点和当前插入的节点一样，覆盖掉原来的节点。 4.如果链表长度大于8且数组容量小于64，触发扩容机制。 5.如果链表长度大于8且数组容量大于64，将链表树化。另外：1.7中put到链表时采用头插法，多线程并发扩容会形成循环死链。在1.8中采用尾插法，扩容时移动元素保证了原链表的节点顺序，解决了扩容死链问题。但1.7和1.8中都存在多线程put导致先put的元素丢失问题。还存在put和get并发执行导致get为null的问题，这个问题主要是由于一个线程put方法刚好触发了扩容导致了元素的桶下标变化，那么另一个线程再按照原来的桶下标去拿肯定拿到的是null。

发表于 2022-08-27 01:56:23 回复(0)

逗号201901211502851

jdk1.7的hashmap底层是数组加链表，1.8的话是数组加链表加红黑树的形式。put方法首先会判断数组是否为空，为空的话则出创建容量为16的一个数组，然后继续哈希算法根据key来定位元素的位置，通过二次哈希值对数组长度取余来确定元素的位置，若该位置上有元素则发生了哈希碰撞，会将改元素存入的已有元素的列表中（1.7头插法，1.8尾插法），如果没有也则创建一个链表，当长度超过8并且数组长度超过64链表就会树化。hashmap扩容因子为0.75，当元素数量超过数组长度的0.75时会进行扩容，每次扩容为原来的2倍，扩容会创建一个新的数组，重新计算桶下标，两元素复制到新的数组，完成扩容；还有链表长度达到8，数组长度未到64也会发生扩容。

发表于 2023-05-10 13:00:33 回复(1)

牛客793464225号

HashMap的底层的数据结构为“数组+链表+红黑树”。map.put(key,value)的实现原理：1.将key和value封装到node中。2.利用hashCode()方法得出key对应的hash值。3.利用hash算法将hash值转化为对应的数组下标，然后根据数组下标找到对应的槽，如果槽为空，就将node节点直接加入。如果不为空，将key和链表中节点key值使用equals方法进行逐个对比，如果返回false，直接将node节点加入链表末尾，如果返回true，直接将原来节点的value值进行覆盖。map.get(key)的实现原理：1.利用hashCode方法获取key值对应的hash值，2.利用hash算法将hash值转化为对应的数组下标。3.如果这个数组下标位置什么也没有，直接返回null，否则的话，拿着key值和链表中节点的key进行比较，如果为true，说明找到对应节点，这个节点的value值就是要找的值，否则，返回null。HashMap的初始容量为16，负载因子为0.75，如果存储的数据达到负载因子允许的容量，就会以2的指数进行扩容。只有当链表长度达到8，数组容量达到64时，链表才会转化为红黑树。转化为红黑树的目的是：进一步提高检索效率。HashMap是非线程安全的，所以在高并发的情况下推荐使用ConCurrentHashMap。

发表于 2022-05-25 19:56:00 回复(0)

涂图被offer砸中

在1.8之前，HashMap的底层为数组＋链表，1.8之后就是数组＋链表＋红黑树。集合put时：当我们向集合存入数据时，哈希函数会通过Key的Hashcode()方法获取哈希值并对其进行扰动处理，对处理后的哈希值与数组长度进行按位与计算（hash & n-1）来确定元素的位置。(前提是数组容量为2的幂）当此位置有其他元素时就会产生哈希冲突，则HashMap会以链表的形式存储这些元素，当链表长度>8且数组长度>=64时链表转为红黑树。扩容机制：数组的容量默认为16，当HashMap中元素的个数>负载因子(默认0.75) * 数组容量时,触发扩容，新数组的容量为原容量的2倍。 HashMap本身非线程安全，多线程场景下建议使用ConcurrentHashMap，这是Java集合框架的基本特性。

发表于 2025-11-02 16:52:29 回复(0)

说等下个版本吧的熊熊很有担当

1.8之前是数组+链表 1.8之后是数组+链表在将数据放入map中是会先调用哈希算法来确定元素的位置这个位置已经有数据了那么会发生哈希碰撞那么就把这些元素放入数组下标位置组成链表数组长度大于64 链表长度大于8 那么链表会前置转化为红黑树扩容因子0.75 以2的倍数扩展也就是16大小的数组 12时候会变为32

发表于 2025-10-28 16:08:12 回复(0)

纱霾的纱雾

HashMap是一种基于哈希表的高效键值对存储结构，它通过数组和链表（红黑树）来组织数据。存储键值对时，首先会通过键的hashcode()方法计算哈希值，然后通过哈希函数将哈希值映射到数组的索引位置，即桶当中。如果多个键映射到同一个桶当中，则这些键值对以链表的形式存储在桶当中，为了优化性能当链表长度大于8时链表就会转为红黑树，从而将插入，查找和删除的时间复杂度从O(n)变为O(logn) HashMap的扩容机制是其优化性能的关键环节，当哈希表中的元素数量达到数组长度和负载因子（默认0.75）的乘积时就会触发扩容机制，会生成一个长度为原来数组长度两倍的新数组并且将原本原来数组的键值对哈希到新数组上，这样做虽然会耗时但是会减少哈希冲突的概率，我们可以通过设置合理初始数组长度和负载因子来减少扩容频率进一步提高HashMap的效率。

发表于 2025-09-26 10:43:08 回复(0)

acodebird

JDK1.8之前HashMap数据结构是数组+链表，JDK1.8开始数据结构变为数组+链表+红黑树。HashMap默认负载因子是0.75，扩容有两个场景：1.在数组实际大小超过length*0.75的时候会进行扩容；2.链表长度超过8且数组长度小于64的时候会进行扩容。每次扩容都是将数组扩大2倍，数组的length总是等于2^n。HashMap定位元素的位置是有两个步骤，1计算key的hash值；2通过与数组长度进行位运算得到位置hash&(length-1)，在lenght是2^n时等同于hash%length，位运算更快，所以保持2^n可以利用位运算的便利，做到均匀分布元素、减少hash冲突，快速定位元素位置、提高扩容效率等（扩容无需重新计算hash值，元素位置要么保持不变，要么index+n）此外当出现hash冲突时且链表长度等于8，数组长度大于64时，HashMap会将链表转成红黑树

编辑于 2025-07-23 15:32:35 回复(0)

bbq了的垂耳兔很淘气

在jdk1.8之后，hashmap是数组+链表+红黑树的结构。当存入元素时，会计算元素的哈希值，然后hashmap进行二次哈希，目的是使哈希值的高位也参与运算，让哈希分布的更加均匀。然后对获得的值与数组长度进行与运算，得到索引如果索引没有被占用，创建节点返回，如果被占用且是普通的节点，进行链表的添加或更新操作，如果链表长度超过阈值，走树化的逻辑，如果是树节点，走红黑树的添加逻辑。返回前检查容量是否超过阈值，超过就进行扩容，扩容为原来的两倍。容量是2的n次幂目的是在计算索引时进行优化。如果没有超过阈值就直接返回

发表于 2022-10-21 18:17:34 回复(0)

哒哒哒嘿嘿

HashMap底层在JDK1.7是由数组、链表实现的，JDK1.8则是数组、链表/红黑树实现的。底层的数据结构不一样，是为了改变查询效率和插入效率。当链表上的节点大于8或数组长度超过64时，就会转化为红黑树结构。

发表于 2022-08-21 11:39:49 回复(0)

牛客36639102号

HashMap:数据结构：在JDK1.7：Entry数组+链表（采用头插法）；在JDK1.8：Node数组+链表+红黑树（采用尾插法）；当链表上的元素个数超过8个且数组长度>=64时转化红黑树。扩容机制：俩倍扩容。底层原理：当向数组添加key-value时，会判断数组的元素个数。当元素个数>=length*负载因子（0.75），会创建一个Entry数组，长度为原来的俩倍。遍历原来的数组，把所有的Entry重新hash到新数组上（原因长度变了，索引值也会发生该表）。底层原理：先hash=（h=key.hashcode())^(h>>>16) 在进行index=hash&(length-1)确定索引值。线程安全问题：hashMap非线程安全的。原因：hashMap的resize分为扩容和rehash俩步，rehash在并发的情况下可能会形成链表环（具体形成过程请自行查阅）。解决方案：采用currentHashMap，采用分段锁技术将整个hash桶进行了分段segment，每个segment都有锁，以此来保证线程安全。

发表于 2022-07-18 09:03:53 回复(0)

ttccq

在JDK8中，hashmap的底层数据结构是数组+链表+红黑树，它是基于哈希算法来确定元素的位置的，当我们往集合中存入数据的时候，它会计算传入的数据的哈希值并取余，然后将其放入槽中，如果放入元素的哈希值产生碰撞，则hashmap会通过链表将它们连接起来，如果链表的长度到达8，则HashMap就会创建红黑树来代替链表。从而提高对槽中数据的查找速度。HashMap的默认初始容量为16，这个容量会以2的指数进行扩容，当其内元素达到容量的0.75时，便会进行扩容。

发表于 2022-07-03 16:14:48 回复(0)

gwyn1

在1.8以前，hashmap底层是数组加链表，在1.8以后是数组加链表加红黑树。通过put方法存入数据：计算传入数据key的哈希值，通过取绝对值再根据集合长度取余来确定元素位置。如果该位置已经存在元素就会发生哈希碰撞，则hashmap就会通过链表将这些元素组织起来，如果链表的长度达到8时，就会转化为红黑树，从而提高查询速度。扩容机制：HashMap中数组的默认初始容量为16，当达到默认负载因子0.75时，会以2的指数倍进行扩容。 Hashmap时非线程安全的，在多线程环境下回产生循环死链，因此在多线程环境下建议使用ConcurrentHashMap。

发表于 2022-06-19 14:40:13 回复(0)

卡农变骤

HashMap的底层是一个entry对象数组，我们在进行put操作的时候，先根据key和value计算出该对象在数组中的位置，然后再插入。那么插入的这个方式也有所不同。如果是JDK1.7的话，底层采用了数组+链表的结构，当插入的位置已经有元素的话，就会开启链表结构，将该对象通过头插法连接到当前位置中，当元素达到阈值之后，数组会进行扩容操作，扩容为当前的1.5倍，扩容的过程首先创建出一个1.5倍的新数组，然后计算原来数组中各个元素所在的位置，那么将元素以此插入之后，把HashMap中的table的指针指向这个新的数组。而在JDK1.8之后，底层结构变成了数组+链表+红黑树，那么插入的方式和JDK1.7的一致，也是先计算，然后插入，因为引进了红黑树，所以插入的时候有可能是红黑树的结构，插入的方法也从头插法变成了尾插法，扩容的时候也相似，也是1.5倍，不过计算位置的时候要多考虑一个红黑树。

发表于 2022-06-11 17:04:46 回复(0)

石皮流水

1.8之前HashMap底层是数组加链表，链表为了解决哈希冲突问题，1.8之后在此基础上增加了红黑树，当链表长度大于一定长度（默认是8）且数组长度≥64时链表转为红黑树，这是为了解决链表长度过长查询性能变低的问题。扩容机制：默认初始容量16，负载因子0.75，当元素数量超过（容量×负载因子）时触发扩容。扩容时创建双倍容量新数组。

发表于 2025-12-17 15:34:24 回复(0)

rlllloot

1.8以前是数组+链表，之后是hashmap底层是数据+链表+红黑树，扩容机制是在数组容量达到初始化容量的0.75之后，数组容量会变为之前的两倍

发表于 2025-12-09 19:04:47 回复(0)

请你说说HashMap底层原理和扩容机制。

问题信息

热门推荐

相关试题