淺談hashmap為什么查詢時間復雜度為O(1)

更新時間：2021年08月02日 08:48:48 作者：PolarisHuster

這篇文章主要介紹了hashmap為什么查詢時間復雜度為O(1)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

hashmap為什么查詢時間復雜度為O(1)

Hashmap是java里面一種類字典式數(shù)據(jù)結(jié)構(gòu)類，能達到O(1)級別的查詢復雜度，那么到底是什么保證了這一特性呢，這個就要從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ù)鍵值找到哈希桶的位置時間復雜度為O(1)，使用的就是數(shù)組的高效查詢。但是僅僅有這個是無法滿足整個hashmap查詢時間復雜度為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值相同的情況下，這種情況下查詢的時間復雜度為O(lgn)，比如下面給出的一個類，所有我們在設(shè)置hashmap的鍵值時需要特別注意），在hashmap的文檔里面有這么一段描述，每個哈希桶中元素數(shù)量是成泊松分布的，

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的查詢時間復雜度為O(1)

PS:

1、哈希沖突百分百的類

 /**
    測試哈希沖突的類，所有的對象都返回同樣的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方法