HashMap的底层数据结构及原理
时间: 2023-03-30 22:02:24 浏览: 78
HashMap 的底层数据结构是数组和链表(或红黑树)。当插入一个键值对时,首先根据键的 hashcode 计算出在数组中的位置,如果该位置为空,则直接插入;如果该位置已经有元素,则遍历链表(或红黑树),找到对应的键值对,如果找到则更新值,否则插入新的节点。当链表长度超过一定阈值时,链表会转换为红黑树,以提高查找效率。在查找时,首先根据键的 hashcode 计算出在数组中的位置,然后遍历链表(或红黑树),找到对应的键值对。
相关问题
hashmap底层数据结构
HashMap的底层数据结构在JDK 1.7及之前是数组+链表的形式,而在JDK 1.8中则是数组+链表/红黑树的形式。在JDK 1.7中,HashMap使用Entry类来存储键值对,底层数组中的每个位置都是一个链表,每个链表节点包含了键值对的信息。而在JDK 1.8中,HashMap使用Node类来存储键值对,底层数组中的每个位置可以是一个链表,也可以是一个红黑树,这取决于链表的长度是否满足一定的条件。HashMap通过计算键的hash值来确定键值对的存储位置。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *3* [HashMap 的底层结构和原理](https://blog.csdn.net/weixin_42814000/article/details/125035202)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *2* [HashMap的数据结构](https://blog.csdn.net/qq_72172339/article/details/130770915)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]
集合底层数据结构及原理
回答: 集合底层数据结构及原理取决于具体的集合类。对于Set集合来说,它的底层数据结构通常是基于哈希表实现的。哈希表是一种使用哈希函数将元素映射到桶中的数据结构。每个桶中存储一个链表或红黑树,用于解决哈希冲突。当哈希表中的元素数量超过一定阈值时,会进行扩容操作,创建更多的桶来存储元素。这样可以保持哈希表的装填因子在一个合理的范围内,以提高性能。对于HashMap来说,JDK1.8之前,哈希值相同的对象以链表形式存储在一个桶中,JDK1.8之后,当链表长度超过8,会从链表转换为红黑树结构,以提高查找效率。\[1\]\[2\]\[3\]
#### 引用[.reference_title]
- *1* *2* *3* [集合底层原理](https://blog.csdn.net/weixin_43472705/article/details/107049073)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insert_down28v1,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)