大家平時(shí)都用過(guò)hashMap,但是可能大家對hashMap的底層實(shí)現不太了解，同時(shí)對其中可能出現的hash沖突有些不了解，這幾天我翻了下資料，也稍微了解下，記錄下來(lái)，以免遺忘。
上圖就是一個(gè)散列表（Hash table，也叫哈希表），是根據關(guān)鍵碼值(Key value)而直接進(jìn)行訪(fǎng)問(wèn)的數據結構。也就是說(shuō)，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪(fǎng)問(wèn)記錄，以加快查找的速度。這個(gè)映射函數叫做散列函數，存放記錄的數組叫做散列表。但是當關(guān)鍵字數量比較大的時(shí)候，難免就會(huì )造成一個(gè)問(wèn)題，就是不一樣的關(guān)鍵字隱射到同一個(gè)地址上，這樣就造成了一個(gè)問(wèn)題，就是hash沖突。那么如何解決呢？
一般比較常用的方法有開(kāi)放地址法：（內容來(lái)自百度百科）
1. 開(kāi)放尋址法：Hi=(H(key) + di) MOD m,i=1,2，…，k(k<=m-1），其中H(key）為散列函數，m為散列表長(cháng)，di為增量序列，可有下列三種取法：
1.1. di=1,2,3，…，m-1，稱(chēng)線(xiàn)性探測再散列；順序查看表的下一單元，直至找到某個(gè)空單元，或查遍全表。
1.2. di=1^2,-1^2,2^2,-2^2，⑶^2，…，±（k)^2,(k<=m/2）稱(chēng)二次探測再散列；在表的左右進(jìn)行跳躍式探測。
1.3. di=偽隨機數序列，稱(chēng)偽隨機探測再散列。根據產(chǎn)生的隨機數進(jìn)行探測。
2 再散列法：建立多個(gè)hash函數，若是當發(fā)生hash沖突的時(shí)候，使用下一個(gè)hash函數，直到找到可以存放元素的位置。
3 拉鏈法（鏈地址法）：就是在沖突的位置上建立一個(gè)鏈表，然后將沖突的元素插入到鏈表尾端，
4 建立公共溢出區：將哈希表分為基本表和溢出表，將與基本表發(fā)生沖突的元素放入溢出表中。
底層的hashMap是由數組和鏈表來(lái)實(shí)現的，就是上面說(shuō)的拉鏈法。首先當插入的時(shí)候，會(huì )根據key的hash值然后計算出相應的數組下標，計算方法是index = hashcode%table.length，（這個(gè)下標就是上面提到的bucket），當這個(gè)下標上面已經(jīng)存在元素的時(shí)候那么就會(huì )形成鏈表，將后插入的元素放到尾端，若是下標上面沒(méi)有存在元素的話(huà)，那么將直接將元素放到這個(gè)位置上。
當進(jìn)行查詢(xún)的時(shí)候，同樣會(huì )根據key的hash值先計算相應的下標，然后到相應的位置上進(jìn)行查找，若是這個(gè)下標上面有很多元素的話(huà)，那么將在這個(gè)鏈表上一直查找直到找到對應的元素。
聯(lián)系客服
