比思論壇
標題:
HashMap的实现原理
[打印本頁]
作者:
642377962
時間:
2021-12-7 10:18
標題:
HashMap的实现原理
HashMap概述: HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
HashMap的数据结构: 在Java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。
HashMap 基于 Hash 算法实现的
当我们往HashMap中put元素时,利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
存储时,如果出现hash值相同的key,此时有两种情况。
(1)如果key相同,则覆盖原始值;
(2)如果key不同(出现冲突),则将当前的key-value放入链表中
获取时,直接找到hash值对应的下标,在进一步判断key是否相同,从而找到对应值。
理解了以上过程就不难明白HashMap是如何解决hash冲突的问题,核心就是使用了数组的存储方式,然后将冲突的key的对象放入链表中,一旦发现冲突就在链表中做进一步的对比。
需要注意Jdk 1.8中对HashMap的实现做了优化,当链表中的节点数据超过八个之后,该链表会转为红黑树来提高查询效率,从原来的O(n)到O(logn)
作者:
zaiyunduan2912
時間:
2022-2-12 16:55
这个很具体
作者:
jf222
時間:
2022-2-20 19:30
提示:
作者被禁止或刪除 內容自動屏蔽
歡迎光臨 比思論壇 (http://bb-cdn.top/)
Powered by Discuz! X2.5