hashmap為什么查詢時間復(fù)雜度為O(1)
Hashmap是java里面一種類字典式數(shù)據(jù)結(jié)構(gòu)類，能達到O(1)級別的查詢復(fù)雜度，那么到底是什么保證了這一特性呢，這個就要從hashmap的底層存儲結(jié)構(gòu)說起
下來看一張圖：
上面就是hashmap的底層存儲示意圖，要想查看一個鍵值對應(yīng)的值，首先根據(jù)該鍵值的hash值找到該鍵的hash桶位置，即是tab[2]還是tab[1]等，計算某個鍵對應(yīng)的哈希桶位置很簡單，就是
int pos = (n - 1) & hash，也就是hash%n，因為位運算效率高所以在hashmap實現(xiàn)時使用的是位運算這種方式，需要注意的是哈希桶的數(shù)量必須是2^n，所以hashmap一旦擴容必定是哈希桶數(shù)量翻番。
通過上面的描述，我們可以知道，根據(jù)鍵值找到哈希桶的位置時間復(fù)雜度為O(1)，使用的就是數(shù)組的高效查詢。但是僅僅有這個是無法滿足整個hashmap查詢時間復(fù)雜度為O(1)的。hashmap在處理哈希沖突的方式如上圖所示的拉鏈法，在沖突數(shù)據(jù)沒有達到8個以前該哈希桶內(nèi)部存儲使用的是鏈表的方式，當某個哈希桶的數(shù)據(jù)超過8個的情況下，
有下面兩種處理方式：
1、哈希桶的數(shù)量是沒有超過64個，那么此時哈希桶數(shù)量double，然后數(shù)據(jù)遷移
2、哈希桶的數(shù)量超過了64個，將該哈希桶內(nèi)部數(shù)據(jù)進行紅黑樹化處理
所以我們可以看到如果所有哈希桶內(nèi)部數(shù)據(jù)都是鏈表存儲的，那么每個哈希桶的數(shù)據(jù)量不會超過8個，這樣當定位到某個哈希桶時，在該哈希桶繼續(xù)查找也可以在O(1)時間內(nèi)完成，下面看一種極端情況，所有的數(shù)據(jù)都在同一個桶里面（這種情況只在所有鍵值hash值相同的情況下，這種情況下查詢的時間復(fù)雜度為O(lgn)，比如下面給出的一個類，所有我們在設(shè)置hashmap的鍵值時需要特別注意），在hashmap的文檔里面有這么一段描述，每個哈希桶中元素數(shù)量是成泊松分布的，
|
1
|
listSize = (exp(-0.5) * pow(0.5, k) / * factorial(k))， |
不同數(shù)量出現(xiàn)的概率如下：
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
大于8: <千萬分之1
通過上面的統(tǒng)計來看，hashmap的鍵值正常（不同對象的hash值不同的情況），哈希桶數(shù)量超過8個概率低于千萬分之一，所以我們通常認為hashmap的查詢時間復(fù)雜度為O(1)
PS:
1、哈希沖突百分百的類
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
/** 測試哈希沖突的類，所有的對象都返回同樣的hash值 **/ public static class Student{ private String name; Student(String name){ this.name = name; } @Override public int hashCode(){ return 1; } @Override public boolean equals(Object obj){ if(this == obj){ return true; } if(obj == null){ return false; } return this.name.equals(((Student)obj).name); } } |
2、我們在實際使用hashmap時需要確保實現(xiàn)hashcode方法以及equals方法，否則不能作為hashmap的鍵值
3、在設(shè)置hashmap的鍵值hashcode方法時盡量保證較好的離散型
4、hashmap的鍵值需保證equals方法返回true時，hashcode必須相同，所以在實際中經(jīng)常使用的鍵值類string，重寫了equals以及hashcode方法
HashMap時間復(fù)雜度問題
HashMap底層采用了hash算法
根據(jù) key 獲得 hashCode 值
HashMap 初始有很多個類似于“桶”的數(shù)據(jù)結(jié)構(gòu)，比如說預(yù)設(shè)了 10 個桶，通過 hashCode 經(jīng)過一定的算法（這個算法必須是快速的）
得到這個 hashCode 應(yīng)存在哪個桶中，然后內(nèi)部生成 Map.Entry 對象將 key 和 value 存到桶中去。
所以一般情況下HashMap的插入和查找的時間復(fù)雜度都是O(1);
以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持服務(wù)器之家。
原文鏈接：https://jonhuster.blog.csdn.net/article/details/104727895
