哈希(hash)表查找速度为什么那么快？快在哪里了？
先看數組存儲數據是怎么樣的。
現在有一個數組，它里面每個單元存儲的是數據的地址
這叫指針數組吧，假設它有100個單元
我們稱他為p[100]
現在我想把一百個數據（地址）放到里面
我們想把某個數據放到p的第幾個單元完全是由
我們決定的，可以說想怎么放就怎么放
是一種亂放，既然是亂放，那么查找起來就比較耗時。
?
哈希表是怎么存儲數據的呢？
哈希表同樣是一個指針數組。
同樣需要存儲100個數據，需要的就不是100個單元了，因為哈希表要把某個數據存放在某個單元不是隨機的一個過程，而是算出來的，這個算法叫哈希函數
比如要存儲一個數據對
張三 1882356
李四 ?23456789
王五 ?58856456
張三經過哈希函數算出來的值是138，那么哈希表最少需要138個單元，因為張三對應的數據1882356要存儲在指針數組的p[138]的位置上。
李四經過哈希函數算出來的值是500，那么2356789這個數據就要存放在p[500]這個位置上。
所以你明白了，"數據的地址放在指針數組的哪個單元格是算出來的，是有跡可尋的，并不是想放在哪里就放在哪里"
那查找的時候就好查找了，你要查找張三對應的數據，
直接把張三用哈希函數算一下，得到138，哦 張三的數據就在p[138]這個位置上，所以一下就找到了。
?
哈希表是一個key- value的數據對，p是一個指針數組，用來存放value的地址，那么key和value的關系是下面這樣的。
p[f(key)]=&value
?
可以看出哈希表有時候會浪費很大空間的，比如上面張三 李四 王五那個例子 如果按照哈希表存儲要定義一個500個大小的指針數組。怎么解決這個問題呢？我再看看書。
? ? ? ?
HASH的理性認識
8/03 為什么會有哈希表，人們存儲數據時，想找到一種查找，插入和刪除、更新復雜度都不是很大的方法，于是哈希表應運而生。
? ? ?
- ?數組存儲空間是連續的，占用內存嚴重，占用空間很大，但數組的二分查找時間復雜度小。
- ? ?尋址容易，插入和刪除困難。
- ?鏈表存儲區間離散，占用內存小，空間復雜度小，但是時間復雜度很大。? ? ?
- ? ?尋址困難，插入和刪除容易。
- ?哈希表
- ? 尋址容易 插入和刪除也容易的數據結構
hash table的實現，最常用的是拉鏈法，可以理解為“鏈表的數組
?
從上圖我們可以發現哈希表是由數組+鏈表組成的，一個長度為16的數組中，每個元素存儲的是一個鏈表的頭結點。那么這些元素是按照什么樣的規則存儲到數組中呢。一般情況是通過hash(key)%len獲得，也就是元素的key的哈希值對數組長度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存儲在數組下標為12的位置。
HashMap的存取
????HashMap的功能是通過“鍵(key)”能夠快速的找到“值”。下面我們分析下HashMap存數據的基本流程：
????1、 當調用put(key,value)時，首先獲取key的hashcode，int hash = key.hashCode();
????2、 再把hash通過一下運算得到一個int h.
hash ^= (hash >>> 20) ^ (hash >>> 12);??// >>>是無符號的右移運算， 高位直接補零，低位移除。>>表示帶符號的右移運算， 高位如果符號位為正補零，符號位負補一，低位直接移除
hash = hash ^?(hash >>> 20) ^ (hash >>> 12)； ^代表異或運算
int h = hash ^ (hash >>> 7) ^ (hash >>> 4);
為什么要經過這樣的運算呢？這就是HashMap的高明之處。先看個例子，一個十進制數32768(二進制1000 0000 0000 0000)，經過上述公式運算之后的結果是35080(二進制1000 1001 0000 1000)。看出來了嗎？或許這樣還看不出什么，再舉個數字61440(二進制1111 0000 0000 0000)，運算結果是65263(二進制1111 1110 1110 1111)，現在應該很明顯了，它的目的是讓“1”變的均勻一點，散列的本意就是要盡量均勻分布。那這樣有什么意義呢？看第3步。
????3、 得到h之后，把h與HashMap的承載量（HashMap的默認承載量length是16，可以自動變長。在構造HashMap的時候也可以指定一個長 度。這個承載量就是上圖所描述的數組的長度。）進行邏輯與運算，即 h & (length-1)，這樣得到的結果就是一個比length小的正數，我們把這個值叫做index。其實這個index就是索引將要插入的值在數組中的 位置。第2步那個算法的意義就是希望能夠得出均勻的index，這是HashTable的改進，HashTable中的算法只是把key的 hashcode與length相除取余，即hash % length，這樣有可能會造成index分布不均勻。還有一點需要說明，HashMap的鍵可以為null，它的值是放在數組的第一個位置。
????4、 我們用table[index]表示已經找到的元素需要存儲的位置。先判斷該位置上有沒有元素（這個元素是HashMap內部定義的一個類Entity， 基本結構它包含三個類，key，value和指向下一個Entity的next）,沒有的話就創建一個Entity<K,V>對象，在 table[index]位置上插入，這樣插入結束；如果有的話，通過鏈表的遍歷方式去逐個遍歷，看看有沒有已經存在的key，有的話用新的value替 換老的value；如果沒有，則在table[index]插入該Entity，把原來在table[index]位置上的Entity賦值給新的 Entity的next，這樣插入結束。
大學學過記憶最深刻的是除留余數發
假設哈希表長為m，p為小于等于m的最大素數，則哈希函數為
h（k）=k??%??p ，其中%為模p取余運算。
例如，已知待散列元素為（18，75，60，43，54，90，46），表長m=10，p=7，則有
????h(18)=18 % 7=4????h(75)=75 % 7=5????h(60)=60 % 7=4???
????h(43)=43 % 7=1????h(54)=54 % 7=5????h(90)=90 % 7=6???
????h(46)=46 % 7=4
此時沖突較多。為減少沖突，可取較大的m值和p值，如m=p=13，結果如下：
????h(18)=18 % 13=5????h(75)=75 % 13=10????h(60)=60 % 13=8????
????h(43)=43 % 13=4????h(54)=54 % 13=2????h(90)=90 % 13=12???
????h(46)=46 % 13=7
?
解決hash沖突的辦法：
最常用的方法：鏈地址法
我們先復習數據結構里的一個知識點：在一個長度為n（假設是10000）的線性表（假設是ArrayList）里，存放著無序的數字；如果我們要找一個指定的數字，就不得不通過從頭到尾依次遍歷來查找，這樣的平均查找次數是n除以2（這里是5000）。
我們再來觀察Hash表（這里的Hash表純粹是數據結構上的概念，和Java無關）。它的平均查找次數接近于1，代價相當小，關鍵是在Hash表里，存放在其中的數據和它的存儲位置是用Hash函數關聯的。
我們假設一個Hash函數是x*x%5,( * & %的優先級是從左至右)當然實際情況里不可能用這么簡單的Hash函數，我們這里純粹為了說明方便，而Hash表是一個長度是11的線性表。如果我們要把6放入其中，那么我們首先會對6用Hash函數計算一下，結果是1，所以我們就把6放入到索引號是1這個位置。同樣如果我們要放數字7，經過Hash函數計算，7的結果是4，那么它將被放入索引是4的這個位置。這個效果如下圖所示。
?
這樣做的好處非常明顯。比如我們要從中找6這個元素，我們可以先通過Hash函數計算6的索引位置，然后直接從1號索引里找到它了。
不過我們會遇到“Hash值沖突”這個問題。比如經過Hash函數計算后，7和8會有相同的Hash值，對此Java的HashMap對象采用的是”鏈地址法“的解決方案。效果如下圖所示。
?
具體的做法是，為所有Hash值是i的對象建立一個同義詞鏈表。假設我們在放入8的時候，發現4號位置已經被占，那么就會新建一個鏈表結點放入8。同樣，如果我們要找8，那么發現4號索引里不是8，那會沿著鏈表依次查找。
雖然我們還是無法徹底避免Hash值沖突的問題，但是Hash函數設計合理，仍能保證同義詞鏈表的長度被控制在一個合理的范圍里。
總結
以上是生活随笔為你收集整理的哈希(hash)表查找速度为什么那么快？快在哪里了？的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Redis之简单动态字符串sds
- 下一篇： 什么是BSP工程师？