|簡體中文

比思論壇

 找回密碼
 按這成為會員
搜索



查看: 1504|回復: 2
打印 上一主題 下一主題

[應用程式] HashMap的实现原理

[複製鏈接]

19

主題

1

好友

279

積分

小學生

Rank: 2

該用戶從未簽到

推廣值
0
貢獻值
0
金錢
1353
威望
279
主題
19
樓主
發表於 2021-12-7 10:18:06
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)

23

主題

1

好友

146

積分

小學生

Rank: 2

  • TA的每日心情
    開心
    2023-12-1 19:27
  • 簽到天數: 17 天

    [LV.4]偶爾看看III

    推廣值
    0
    貢獻值
    53
    金錢
    35
    威望
    146
    主題
    23
    沙發
    發表於 2022-2-12 16:55:47
    这个很具体
    頭像被屏蔽

    8

    主題

    0

    好友

    2801

    積分

    禁止發言

  • TA的每日心情
    慵懶
    2023-7-23 17:55
  • 簽到天數: 1435 天

    [LV.10]以壇為家III

    推廣值
    0
    貢獻值
    0
    金錢
    2906
    威望
    2801
    主題
    8
    板凳
    發表於 2022-2-20 19:30:29
    提示: 作者被禁止或刪除 內容自動屏蔽
    重要聲明:本論壇是以即時上載留言的方式運作,比思論壇對所有留言的真實性、完整性及立場等,不負任何法律責任。而一切留言之言論只代表留言者個人意見,並非本網站之立場,讀者及用戶不應信賴內容,並應自行判斷內容之真實性。於有關情形下,讀者及用戶應尋求專業意見(如涉及醫療、法律或投資等問題)。 由於本論壇受到「即時上載留言」運作方式所規限,故不能完全監察所有留言,若讀者及用戶發現有留言出現問題,請聯絡我們比思論壇有權刪除任何留言及拒絕任何人士上載留言 (刪除前或不會作事先警告及通知 ),同時亦有不刪除留言的權利,如有任何爭議,管理員擁有最終的詮釋權。用戶切勿撰寫粗言穢語、誹謗、渲染色情暴力或人身攻擊的言論,敬請自律。本網站保留一切法律權利。

    手機版| 廣告聯繫

    GMT+8, 2024-12-24 09:05 , Processed in 0.020611 second(s), 29 queries , Gzip On.

    Powered by Discuz! X2.5

    © 2001-2012 Comsenz Inc.

    回頂部