HashMap底层数据结构及其增put删remove查get方法的代码实现原理

简介: HashMap 是基于数组 + 链表 + 红黑树实现的高效键值对存储结构。默认初始容量为16,负载因子为0.75。当存储元素超过容量 * 负载因子时,会进行扩容。HashMap 使用哈希算法计算键的索引位置,通过链表或红黑树解决哈希冲突,确保高效存取。插入、获取和删除操作的时间复杂度接近 O(1)。

PS:由于文档是我在本地编写好之后再复制过来的,有些文本格式没能完整的体现,故提供下述图片,供大家阅览,以便有更好的阅读体验:
image.png

1.HashMap底层数据结构是数组+链表(jdk1.7头插法<扩容时链表逆序可能会导致环形链表的问题出现> jdk1.8尾插法)+红黑树(jdk1.8).
2.HashMap中数组的容量默认为16,负载因子默认为0.75,当数组的0-15个下标里有16×0.75=12个被使用时,且HashMap中存储的元素总个数大于64时,则发生扩容操作,数组的容量扩大为原来的2n.
3.负载因子代表数组中存储数据密度的大小:负载因子越大,数组单位容量内存储的数据越多,不同元素之间(key不同,但计算得到的数组下标相同)越容易发生碰撞(哈希碰撞);反之,则单位容量内存储的数据越少,越不易发生碰撞.
4.put(key,value)时的处理逻辑:
(1)hash(key) = (key==NULL)?0:(h=key.hashCode())^(h>>>16),即取key的原始哈希码的高低16位进行异或位运算,计算出一个经高低位混合后高低位分布更加均匀的新哈希码,再用该新哈希码和数组容量减一做与位运算(hash(key)&(2^n-1))得出要存放的数组下标[当HashMap的容量是2的n次幂时,(2^n-1)的二进制就是11111*111全1的形式,这样与hash(key)进行与的位运算时,能够充分的散列,使得添加的元素均匀分布到HashMap的每个位置上,减少hash碰撞],可以一定程度降低根据不同元素计算得出相同数组下标(哈希碰撞)的概率;
(2)得出的数组下标里已经存放有数据元素,则根据key的值遍历比较该下标下的链表或红黑树,如果遇到相同key,则更新key对应的value值后返回(return);若遍历链表后未遇到相同的key,则在链表(jdk1.7头部 jdk1.8尾部)或红黑树合适位置(可能触发红黑树的左旋右旋或颜色改变),插入新的(key,value)键值对元素(插入值时统计存储的总元素个数的变量值会加一) ;
(3)某链表插入新的键值对后,可能导致该链表的长度大于等于8,若此时数组存储的总元素个数大于等于64,则将链表转为红黑树(保证最好最坏情况下时间复杂度为以2为底总元素个数n的对数级别,以提高增删查处理性能);
(4)链表插入新值后,也可能会触发数组扩容操作
5.get(key)时的处理逻辑:同put(key,value)的步骤(1),会根据key值计算得出数组下标,然后用key值遍历比较该数组下标下的链表或或红黑树,找到相同key对应的value值并返回,否则,返回null;
6.remove(key)时的处理逻辑:同get(key)和put(key,value)的步骤(1),会先根据key找到要删除元素所在位置,然后进行删除操作;

目录
相关文章
|
2月前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
47 1
|
2月前
|
存储 Java 开发者
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
64 2
|
14天前
|
存储 Java Serverless
深入探索:HashMap的底层数据结构揭秘
HashMap作为Java中一个非常重要的集合类,其底层数据结构的设计对于性能有着至关重要的影响。本文将详细解析HashMap的底层数据结构,帮助开发者更好地理解和使用这一强大的工具。
26 7
|
2月前
|
存储 算法 安全
HashMap的实现原理,看这篇就够了
关注【mikechen的互联网架构】,10年+BAT架构经验分享。深入解析HashMap,涵盖数据结构、核心成员、哈希函数、冲突处理及性能优化等9大要点。欢迎交流探讨。
HashMap的实现原理,看这篇就够了
|
2月前
|
存储
让星星⭐月亮告诉你,HashMap的put方法源码解析及其中两种会触发扩容的场景(足够详尽,有问题欢迎指正~)
`HashMap`的`put`方法通过调用`putVal`实现,主要涉及两个场景下的扩容操作:1. 初始化时,链表数组的初始容量设为16,阈值设为12;2. 当存储的元素个数超过阈值时,链表数组的容量和阈值均翻倍。`putVal`方法处理键值对的插入,包括链表和红黑树的转换,确保高效的数据存取。
59 5
|
2月前
|
存储 安全 数据库
除了 HashMap,还有哪些数据结构可以实现键值对存储?
【10月更文挑战第11天】 除了`HashMap`,其他常见支持键值对存储的数据结构包括:`TreeMap`(基于红黑树,键有序)、`LinkedHashMap`(保留插入顺序)、`HashTable`(线程安全)、`B-Tree`和`B+Tree`(高效存储大量数据)、`SkipList`(通过跳跃指针提高查找效率)及`UnorderedMap`(类似`HashMap`)。选择合适的数据结构需根据排序、并发、存储和查找性能等需求。
|
2月前
|
Java C++ 索引
让星星⭐月亮告诉你,LinkedList和ArrayList底层数据结构及方法源码说明
`LinkedList` 和 `ArrayList` 是 Java 中两种常见的列表实现。`LinkedList` 基于双向链表,适合频繁的插入和删除操作,但按索引访问元素效率较低。`ArrayList` 基于动态数组,支持快速随机访问,但在中间位置插入或删除元素时性能较差。两者均实现了 `List` 接口,`LinkedList` 还额外实现了 `Deque` 接口,提供了更多队列操作。
26 3
|
2月前
|
存储 索引
让星星⭐月亮告诉你,HashMap在put数据时是如何找到要存放的位置的?
HashMap 是一种常用的键值对存储结构,其底层采用数组+链表+红黑树实现。本文探讨了 HashMap 在插入键值对时如何确定存放位置。通过分析 `put` 方法的源代码,重点解析了哈希码的计算过程和数组索引的确定方法。哈希码通过 `hashCode()` 方法和位运算优化,确保均匀分布,从而减少哈希碰撞,提高性能。最终,通过 `(n-1) & hash` 计算出数组索引,确保键值对被正确存放到指定位置。
36 2
|
2月前
|
存储
ES6中的Set数据结构的常用方法和使用场景
ES6中的Set数据结构的常用方法和使用场景
|
2月前
|
Java
让星星⭐月亮告诉你,HashMap中保证红黑树根节点一定是对应链表头节点moveRootToFront()方法源码解读
当红黑树的根节点不是其对应链表的头节点时,通过调整指针的方式将其移动至链表头部。具体步骤包括:从链表中移除根节点,更新根节点及其前后节点的指针,确保根节点成为新的头节点,并保持链表结构的完整性。此过程在Java的`HashMap$TreeNode.moveRootToFront()`方法中实现,确保了高效的数据访问与管理。
30 2