HashMap存储原理

小灰灰 2022-02-20 15:29 220阅读 0赞

HashMap存储的数据存放在内存中，提高HashMap数据寻址速度是重点要解决的问题，所以HashMap底层的存储结构非常关键，如果使用数组存储，时间复杂度为Ｏ(1)，使用链表存储，时间复杂度为O(n)，如果使用二叉树存储，时间复杂度为O(lg(n))。所以HashMap优先使用数组存储，如果出现hash碰撞，采用链表存储，如果链表长度大于8，寻址速度明显下降，进一步采用红黑树存储，将寻址效率提高。  
如果下图为HashMap存储  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70]

## 元素分配Hash桶 ##

向HashMap中put(key,value)数据时，首先计算Key的哈希值，将Hash值%16计算出Hash桶序号n(0-16之间），将元素存放在n号hash桶，存放的数据时Map.Entry包括Key值和Value值  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 1]  
当存放两个元素获取Hash并且Mod 16得到Hash桶编号相同时，出现Hash碰撞，hash桶使用链表存储这两个对象，使用HashMap.get(key)获取这两个对象时，需要两步实现，首先得到它们对应的Hash桶号，在根据Key与链表中的Key1=Value1比较key.equale(key1)，找出对应元素，这样需要递归遍历列表中的元素，执行效率降低。  
当链表长度大于8时，HashMap将链表存储转化为红黑树存储，红黑树遍历每次可以减少一个分支，效率比链表高，其时间复杂度为O(lg(n))。

## HashMap扩容 ##

HashMap使用数组存储，默认长度为16，加载因子为0.75,当HashMap的Hash桶数量的75%被分配使用时，HashMap扩容为原来的两倍。扩容时原来数组地址放弃，重新分配地址空间，并将原来对应的数据复制过来。此过程为rehashing，JDK1.7在多线程环境下HashMap扩容可以导致无限循环，因为扩容过程中会新数组会和原来的数组有指针引用关系。在JDK1.8中在多线程环境下HashMap扩容可以导致数据丢失。

## Key类型选定 ##

存放到HashMap中的Key的类型，最好选择HashCode方法返回hashcode固定值，防止hashcode变化，比如String类型重写了HashCode方法，只要字符串不变化，hashCode值唯一。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70]: /images/20220220/f5d18a8880584faebff75178b9b0b08e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 1]: /images/20220220/2c6ba22761204730adc2227f77a145f1.png

发表评论取消回复

表情：

评论列表（有 0 条评论，220人围观）

还没有评论，来说两句吧...

相关阅读

相关 HashMap原理

HashMap原理单线程下的HashMap HashMap中的字段存储结构 Node节点插入数据确定Node的存储位置

蔚落/ 2023年09月25日 19:35/ 0 赞/ 83 阅读

相关 HashMap原理

HashMap原理讲解 1.HashMap的继承体系图 2.Node数据结构 3.底层存储结构图 4.put数据原理图 5.什么是Hash碰

蔚落/ 2022年12月18日 05:56/ 0 赞/ 90 阅读

相关 HashMap初始值、排序问题以及存储原理

HashMap的初始值： hashmap有多个构造方法， 1. HashMap() 2. HashMap(int initCapacity) 3. HashMap(

柔情只为你懂/ 2022年06月06日 08:35/ 0 赞/ 136 阅读

相关 HashMap结构及存储原理

HashMap结构及存储原理数组的机制是存储连续，所以空间复杂度很高。表现出来就是插入，删除很慢但是查询很快链表的机制是存储分散，所以空间复杂度很小。表现

分手后的思念是犯贱/ 2022年05月27日 04:17/ 0 赞/ 134 阅读

相关 hashmap的存储原理

直接上代码： public V put(K key, V value) \{ //如果key为null，存储位置为table\[0\]或table\[0\]的冲突

ゞ浴缸里的玫瑰/ 2022年05月25日 02:27/ 0 赞/ 143 阅读

相关 HashMap原理

概述 HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。值得注意的是HashMap不是线程安全的

ゞ浴缸里的玫瑰/ 2022年04月06日 11:20/ 0 赞/ 179 阅读

相关 HashMap存储原理

HashMap存储的数据存放在内存中，提高HashMap数据寻址速度是重点要解决的问题，所以HashMap底层的存储结构非常关键，如果使用数组存储，时间复杂度为Ｏ(1)，使用链

小灰灰/ 2022年02月20日 15:29/ 0 赞/ 221 阅读

相关 Hashmap原理

[https://blog.csdn.net/l18848956739/article/details/85998121][https_blog.csdn.net_l18848

系统管理员/ 2022年02月16日 11:29/ 0 赞/ 203 阅读

相关 HashMap原理

HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap，都知道哪里要用HashMap，知道HashTable和HashMap之间的区别

╰半夏微凉°/ 2022年02月01日 05:13/ 0 赞/ 211 阅读

相关 HashMap实现存储原理及性能优化

最近工作比较忙，好久不写点东西了.......（其实是比较懒）这几天在看JAVA性能调优中讲到HashMap性能优化。这篇文章着实对我印象深刻，印象深刻的

柔情只为你懂/ 2021年12月12日 11:09/ 0 赞/ 356 阅读