在1.8之前，HashMap的底层是数组加链表，在1.8之后是数组+链表+红黑树； 它的put流程是：基于哈希算法来确定元素位置，当我们向集合存入数据时，他会计算传入的key的哈希值，并利用哈希值取绝对值再根据集合长度取余来确定元素的位置，如果这个位置已经存在其他元素了，就会发生哈希碰撞，则hashmap就会通过链表将这些元素组织起来，如果链表的长度达到8时，就会转化为红黑树，从而提高查询速度。 扩容机制：HashMap中数组的默认初始容量为16，当达到默认负载因子0.75时，会以2的指数倍进行扩容。 Hashmap时非线程安全的，在多线程环境下回产生循环死链，因此在多线程环境下建议使用ConcurrentHashMap。
发表于 2022-04-26 15:14:50
回复(5)
在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)
一、数据结构：JDK8后,HashMap底层是采用“数组+链表+红黑树”来实现的，（HashMap是基于哈希算法来确定元素的位置，当我们向集合中存入数据时,它会计算传入的Key的哈希值,并利用哈希值取余来确定位置。若碰撞进一步加剧会创建红黑树来代替这个链表,从而提高对数据的查找速度 二、put（）：1. 判断数组,若发现数组为空,则进行首次扩容。 2. 判断头节点,若发现头节点为空,则新建链表节点,存入数组。 3. 判断头节点,若发现头节点非空,则将元素插入槽内。 4. 插入元素后,判断元素的个数,若发现超过阈值则再次扩容。 三、触发扩容行为三个条件： 1. 如果数组为空,则进行首次扩容。 2. 将元素接入链表后,如果链表长度达到8,并且数组长度小于64,则扩容。 3. 添加后,如果数组中元素超过阈值,即比例超出限制（默认为0.75）,则扩容。 并且,每次扩容时都是将容量翻倍,即创建一个2倍大的新数组,然后再将旧数组中的数组迁移到新数组里。
编辑于 2022-05-11 23:05:36
回复(3)
在jdk1.8之前，Hashmap的底层实现是数组+链表的形式，在jdk1.8之后，底层实现在原来的数组+链表的基础上增加了红黑树，当向hashmap中put元素的时候，底层数组进行初始化，默认初始化值为16，负载因子为0.75，当数组需要扩容的时候，长度变为原来的2倍，然后使用自定义的哈希算法来计算传入的key值的哈希值，对该哈希值进行位运算以获取当前元素的位置并且返回，如果该位置已经存在的话，则将这些元素放到该位置的桶中形成链表，如果桶中的元素超过8，就会对链表进行树形化，使其成为红黑树，如果数组的长度超过64，也会进行树形化，成为红黑树。hashmap的键和值都可以为空，是线程不安全的。
发表于 2022-08-29 21:48:04
回复(0)
在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)
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)
在jdk1.8之后，hashmap是数组+链表+红黑树的结构。当存入元素时，会计算元素的哈希值，然后hashmap进行二次哈希，目的是使哈希值的高位也参与运算，让哈希分布的更加均匀。然后对获得的值与数组长度进行与运算，得到索引如果索引没有被占用，创建节点返回，如果被占用且是普通的节点，进行链表的添加或更新操作，如果链表长度超过阈值，走树化的逻辑，如果是树节点，走红黑树的添加逻辑。返回前检查容量是否超过阈值，超过就进行扩容，扩容为原来的两倍。容量是2的n次幂目的是在计算索引时进行优化。如果没有超过阈值就直接返回
发表于 2022-10-21 18:17:34
回复(0)
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)
在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)
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)
在`HashMap`中，元素的存储位置是通过键的哈希值和哈希表的长度进行计算得到的。具体的计算方法是：`(n - 1) & hash`，其中`n`是哈希表的长度，`hash`是键的哈希值。 这里使用按位与运算符`&`而不是取余运算符`%`有两个主要原因： 1. 效率：位运算的效率要高于取余运算。在计算机内部，位运算只需要一次操作，而取余运算需要多次操作。 2. 哈希表长度的特性：在`HashMap`中，哈希表的长度总是2的幂。这是因为2的幂的特性，任何数与(2的幂-1)进行按位与运算，结果等价于对2的幂取余。例如，对于任何整数`x`，`x & (n - 1)`的结果等价于`x % n`，其中`n`是2的幂。 因此，`HashMap`选择使用按位与运算来计算元素的存储位置，既可以保证正确性，又可以提高效率。
发表于 2024-04-21 17:21:44
回复(0)
java 1.7 以下采用Segment数组+HashEntry链表实现 1.8之后采用数组+链表+红黑树实现，1.7的常用的put方法是通过key的hashcode定位到segment数组中的hashentry中，遍历hashentry，如何不为空就对比value值相等就覆盖vulue，为空就新建hashentry并且加入到对应的segment数组中。 在此之前要判断是否要扩容，最后获取当前segment的锁并解除。1.7get方法 通过后去key的hash值进行位运算和偏移量的相加获取去具体偏移量值u，通过偏移量u去segment数组中获取setment对象，不为空就进行链表循环segment对象，对比hashentry如果相等就返回值，否则返回null。java1.8的 put方法 先判断keyvalue是否为空。然后判断table数组是否为空，空则初始化。不为空就判断下标i是否存在值，不存在就进行cas方式更新。当下标i不为空，且准备扩容调用扩容方法，不扩容的时候则进行syn加锁操作给头节点加锁，同时判断当前偏移量的值是否与前面的值相等，判断头节点是否链表，是链表就进行链表循环判断当前位置与key是否相等，相等就覆盖值 不同就新建node节点放在链表最后，如果当前node节点为树节点，则进行树节点相关操作。当bincount大于8则节点链表转换为红黑树。 get方法根据key计算出hash值，判断数组是否为空，如果是首节点就直接返回 是红黑树结构就从红黑树里面查询 链表结构就链表循环判断。
发表于 2024-04-02 17:48:05
回复(0)
HashMap在1.8之前是数组加链表，1.8以后是数组+链表+红黑树，它是线程不安全的，它的put过程是先根据哈希算法来确定元素的位置，当我们向集合传入数据时，进行key的hash值进行确定，如果当前位置数据不存在，直接插入，如果存在，则发生了哈希冲突，此时就会将数据组织为链表，如果链表的长度达到8并且Map的容量到达64则此时会变为红黑树，为什么不是二叉搜索树，当为二叉搜索树时，依然会发生长链问题，那为什么不是平衡二叉树，平衡二叉树左右子树相差为1，如果大于1将会进行翻转，当插入操作频繁，就会多次翻转，性能不好，使用红黑树，我们不需要多次去翻转
发表于 2024-04-01 20:02:52
回复(0)
HashMap是一种数据结构，用与存储键值对，它基于哈希表实现，允许快速查找，插入和删除操作，在HashMap中每个键值对都映射到唯一的键上，这个键就是用来被计算存储位置，从而来实现高效的数据访问。 HashMap的特点 1. 键和值都可以为null; 2. 键是唯一的，如果插入了重复的键，会覆盖旧值。 3. 不是线程安全，如果多个线程同时修改HashMap,可能会导致数据不一致或者死锁。 4. 遍历时，元素的顺序不确定，不保证顺序与插入顺序一致。 5. HashMap的初始容量为16， 负载因子为0.75， 当哈希桶数组的实际大小超过容量乘以负载因子， 会自动扩容。 HashMap底层是 数组+链表+红黑树 1. 快速的查找： 数组提供了快速的随机访问的能力，可以通过键的哈希值直接计算出存储位置， 从而实现快速查找操作， 很多情况下，查找元素的时间复杂度为O(1); 2. 适应动态变化： 使用数组作为底层存储结构可以很好地的支持动态扩容和缩容，当HashMap中的元素增加时， 可以根据负载因子的设定自动扩容，将元素重新分布到更大的数组中，从而保持较低的哈希冲突率。 同样的当元素数量减少，也可以进行缩容操作 节省空间。 3. 解决哈希冲突： 哈希函数的值域可能大于数组的长度，不同的键可能哈希到同一个位置，就会产生哈希冲突。链表或红黑树的引入可以解决这个问题， 当发生哈希冲突时，新的键值对可以直接插入到链表(或红黑树)的头部， 形成一个链表(或红黑树)结构，不需要重新计算哈希值，在查找时，只需要在对应位置的链表(或红黑树)中进行遍历，保持较高的查找效率。 4. 性能平衡： 使用链表或(红黑树)而不是简单地将相同哈希值的键值对放在同一个位置， 可以保证在最坏的情况下的时间复杂度为 O(log n), 而不是简单O(n),这种设计在处理大量数据时能够提供更好的性能保证。 HashMap底层采用 数组+链表(或红黑树)的组合结构，能兼顾快速查找、动态化的和解决哈希冲突等方面的需求，从而在实际应用中保持了高效性能。
编辑于 2024-03-14 15:24:34
回复(0)
问题信息
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
