hashmap底层实现原理1.7
时间: 2023-11-11 21:56:47 浏览: 46
HashMap在JDK 1.7的底层实现原理是采用数组和链表的结合形式。它使用了一个Entry数组来存储键值对,并且每个Entry对象都是一个链表的头节点,用于解决哈希冲突。
具体实现过程如下:
1. 创建一个Entry数组用于存储键值对,初始化大小为默认值(16)或指定的初始容量。
2. 当添加一个键值对时,首先根据键的哈希值计算出在数组中的索引位置。
3. 如果该索引位置上没有任何元素,则直接将键值对作为一个新的Entry插入到该位置。
4. 如果该索引位置上已经存在元素,即发生了哈希冲突,使用链表的方式解决冲突。
- 遍历该位置上的链表,如果找到键与要插入的键相等的节点,则更新对应的值。
- 如果遍历完链表仍未找到相同键的节点,则将新的键值对插入到链表的末尾。
5. 当链表长度达到一定阈值(默认为8),或者数组大小达到扩容门槛(默认为75%),就会触发扩容操作。
6. 扩容操作会创建一个更大的Entry数组,并将旧数组中的元素重新计算索引,插入到新数组中。
7. 扩容后,所有键值对的索引位置都会发生变化,但链表结构不变。
8. 当需要获取某个键对应的值时,根据键的哈希值计算出在数组中的索引位置,并遍历该位置上的链表,找到对应的节点并返回值。
总结起来,JDK 1.7中的HashMap底层实现原理是使用数组和链表的组合结构,通过哈希值计算索引位置,并使用链表解决哈希冲突。但是这种实现方式在处理大量数据时会存在性能问题,因为链表的查询效率较低。
相关问题
HashMap1.7 底层实现原理
HashMap1.7 的底层实现原理主要基于数组和链表实现的,具体如下:
1. 数组:HashMap1.7 底层采用数组来存储数据,数组的长度是固定的,并且必须是2的幂次方,这是因为在计算元素在数组中的位置时,采用的是位运算,而2的幂次方可以使用位运算来代替取模运算,从而提高计算效率。
2. 链表:当多个元素的 hashcode 值相同时,它们会被存储在同一个数组位置上,这时就会形成一个链表来存储这些元素。在 HashMap1.7 中,采用的是单向链表,每个节点包含了 key、value 和指向下一个节点的指针。同时,每个数组位置上都有一个指向链表头部的指针,用来方便查找和添加元素。
3. hash 函数:HashMap1.7 中的 hash 函数采用了位运算的方式,先将 key 的 hashcode 值与 (length - 1) 进行与运算,得到的结果即为元素在数组中的位置。这种方式可以有效地避免 hash 冲突,提高查找和添加元素的效率。
4. 扩容:当 HashMap1.7 中元素的数量达到了负载因子(默认为0.75)乘以数组长度时,就会触发扩容操作。扩容时,会将数组长度扩大为原来的两倍,并重新计算每个元素在数组中的位置,将它们插入到新的数组中。同时,由于原来的链表可能会被拆分成多个链表,所以需要重新组织链表结构,使得每个链表只包含一个位置上的元素。
综上所述,HashMap1.7 底层实现原理主要基于数组和链表实现的,采用了位运算的方式来计算元素在数组中的位置,同时支持扩容操作,从而提高了查找和添加元素的效率。
jdk 1.7 与jdk 1.8 hashmap底层原理
jdk1.7和jdk1.8中HashMap底层实现的主要区别在于解决哈希冲突的方式不同。具体来说,jdk1.7中采用的是“数组+链表”的方式,而jdk1.8中则采用了“数组+链表/红黑树”的方式。
在jdk1.7中,当哈希冲突发生时,会将冲突的元素存储在链表中,这样就会导致在查找元素时需要遍历整个链表,时间复杂度为O(n)。而在jdk1.8中,当链表长度超过一定阈值时,会将链表转化为红黑树,这样就可以将查找元素的时间复杂度降低到O(logn)。
此外,jdk1.8中还引入了“红黑树”这种数据结构,用于优化哈希表的性能。当链表长度超过一定阈值时,会将链表转化为红黑树,这样就可以将查找元素的时间复杂度降低到O(logn)。
综上所述,jdk1.8中HashMap的底层实现相比于jdk1.7更加高效,能够更好地应对大规模数据的处理。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)