快捷導(dǎo)航

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

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

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

hashmap為什么查詢時(shí)間復(fù)雜度為O(1)

Hashmap是java里面一種類字典式數(shù)據(jù)結(jié)構(gòu)類，能達(dá)到O(1)級(jí)別的查詢復(fù)雜度，那么到底是什么保證了這一特性呢，這個(gè)就要從hashmap的底層存儲(chǔ)結(jié)構(gòu)說起

下來看一張圖：

上面就是hashmap的底層存儲(chǔ)示意圖，要想查看一個(gè)鍵值對(duì)應(yīng)的值，首先根據(jù)該鍵值的hash值找到該鍵的hash桶位置，即是tab[2]還是tab[1]等，計(jì)算某個(gè)鍵對(duì)應(yīng)的哈希桶位置很簡(jiǎn)單，就是

int pos = (n - 1) & hash，也就是hash%n，因?yàn)槲贿\(yùn)算效率高所以在hashmap實(shí)現(xiàn)時(shí)使用的是位運(yùn)算這種方式，需要注意的是哈希桶的數(shù)量必須是2^n，所以hashmap一旦擴(kuò)容必定是哈希桶數(shù)量翻番。

通過上面的描述，我們可以知道，根據(jù)鍵值找到哈希桶的位置時(shí)間復(fù)雜度為O(1)，使用的就是數(shù)組的高效查詢。但是僅僅有這個(gè)是無法滿足整個(gè)hashmap查詢時(shí)間復(fù)雜度為O(1)的。hashmap在處理哈希沖突的方式如上圖所示的拉鏈法，在沖突數(shù)據(jù)沒有達(dá)到8個(gè)以前該哈希桶內(nèi)部存儲(chǔ)使用的是鏈表的方式，當(dāng)某個(gè)哈希桶的數(shù)據(jù)超過8個(gè)的情況下，

有下面兩種處理方式：

1、哈希桶的數(shù)量是沒有超過64個(gè)，那么此時(shí)哈希桶數(shù)量double，然后數(shù)據(jù)遷移

2、哈希桶的數(shù)量超過了64個(gè)，將該哈希桶內(nèi)部數(shù)據(jù)進(jìn)行紅黑樹化處理

所以我們可以看到如果所有哈希桶內(nèi)部數(shù)據(jù)都是鏈表存儲(chǔ)的，那么每個(gè)哈希桶的數(shù)據(jù)量不會(huì)超過8個(gè)，這樣當(dāng)定位到某個(gè)哈希桶時(shí)，在該哈希桶繼續(xù)查找也可以在O(1)時(shí)間內(nèi)完成，下面看一種極端情況，所有的數(shù)據(jù)都在同一個(gè)桶里面（這種情況只在所有鍵值hash值相同的情況下，這種情況下查詢的時(shí)間復(fù)雜度為O(lgn)，比如下面給出的一個(gè)類，所有我們?cè)谠O(shè)置hashmap的鍵值時(shí)需要特別注意），在hashmap的文檔里面有這么一段描述，每個(gè)哈希桶中元素?cái)?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)計(jì)來看，hashmap的鍵值正常（不同對(duì)象的hash值不同的情況），哈希桶數(shù)量超過8個(gè)概率低于千萬分之一，所以我們通常認(rèn)為hashmap的查詢時(shí)間復(fù)雜度為O(1)

PS:

1、哈希沖突百分百的類

 /**
    測(cè)試哈希沖突的類，所有的對(duì)象都返回同樣的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、我們?cè)趯?shí)際使用hashmap時(shí)需要確保實(shí)現(xiàn)hashcode方法以及equals方法，否則不能作為hashmap的鍵值

3、在設(shè)置hashmap的鍵值hashcode方法時(shí)盡量保證較好的離散型

4、hashmap的鍵值需保證equals方法返回true時(shí)，hashcode必須相同，所以在實(shí)際中經(jīng)常使用的鍵值類string，重寫了equals以及hashcode方法