散列表
- 概念：Hash表是通過(guò)關(guān)鍵字用f()（hash函數(shù)）去找對(duì)應(yīng)地址的數(shù)據(jù)結(jié)構(gòu)；（就像查字典一樣）
- hash沖突：如果是多音字an（按，安）通過(guò)關(guān)鍵字查找的頁(yè)數(shù)都是一樣的,這樣就形成了hash沖突也就是hash碰撞；
- hash碰撞的常用解決方法有：1.開(kāi)發(fā)定址法 2.鏈地址法
-
開(kāi)放定址發(fā)：
圖1
注意：上面所說(shuō)的開(kāi)發(fā)定址法的原理是遇到?jīng)_突的時(shí)候查找順著原來(lái)哈希地址查找下一個(gè)空閑地址然后插入，但是也有一個(gè)問(wèn)題就是如果空間不足，那他無(wú)法處理沖突也無(wú)法插入數(shù)據(jù)，因此需要裝填因子(空間/插入數(shù)據(jù))>=1。
-
鏈地址法（拉鏈法）：鏈地址法的原理時(shí)如果遇到?jīng)_突，他就會(huì)在原地址新建一個(gè)空間，然后以鏈表結(jié)點(diǎn)的形式插入到該空間。我感覺(jué)業(yè)界上用的最多的就是鏈地址法。（hashmap的解決方法）
圖2 - 哈希表的性能：由于哈希表高效的特性，查找或者插入的情況在大多數(shù)情況下可以達(dá)到O(1)，時(shí)間主要花在計(jì)算hash上，當(dāng)然也有最壞的情況就是hash值全都映射到同一個(gè)地址上，這樣哈希表就會(huì)退化成鏈表，查找的時(shí)間復(fù)雜度變成O(n)，但是這種情況比較少，只要不要把hash計(jì)算的公式外漏出去并且有人故意攻擊，一般也不會(huì)出現(xiàn)這種情況。
HashMap
- HashMap基于hash表原理，我們通過(guò)put()和get()方法儲(chǔ)存和獲取對(duì)象。當(dāng)我們將鍵值對(duì)傳遞給put()方法時(shí)，它調(diào)用鍵對(duì)象的hashCode()方法來(lái)計(jì)算最終的hashCode值，然后找到bucket位置來(lái)儲(chǔ)存值對(duì)象。當(dāng)獲取對(duì)象時(shí)，通過(guò)鍵對(duì)象的equals()方法找到正確的鍵值對(duì)，然后返回值對(duì)象。
HashMap，HashTable的區(qū)別
- 1.HashTable 上早期用來(lái)存儲(chǔ)鍵值對(duì)的map，HashMap是在HashTable 之后出來(lái)的。
- 2.HashTable 線程安全因?yàn)镠ashTable 是同步的,HashMap不是同步的所以造成線程不安全。
- 3.hashmap的速度快于HashTable ，主要原因是遍歷方式的內(nèi)部實(shí)現(xiàn)上不同，HashMap中的迭代器是一個(gè)快速迭代器，而HashTable 用的枚舉器。
- 4.HashMap的鍵和值可以是null，而HashTable不能
為什么要用ConCurrentHashMap
- 當(dāng)你想多線程處理數(shù)據(jù)你就可以用ConCurrentHashMap，因?yàn)镃onCurrentHashMap的處理速度快，HashTable是過(guò)時(shí)的散列表結(jié)構(gòu)，缺陷有1.內(nèi)部遍歷處理速度慢，2.在多線程操作HashTable 時(shí)，HashTable 同步的是整個(gè)散列表，所以當(dāng)一個(gè)線程操作put()方法時(shí)，另一個(gè)線程只能等該線程操作完成后才能操作HashTable ，而ConCurrentHashMap就不一樣了，他實(shí)行分段鎖，把整個(gè)散列表分成很多部分，當(dāng)一個(gè)線程執(zhí)行ConCurrentHashMap的put()時(shí)只是占用了這一部分的鎖，此時(shí)其他線程能占用其他的get()去占用其他部分鎖，所以他的效率要高于HashTable ，在多線程處理散列表時(shí)我們應(yīng)該優(yōu)先選擇ConCurrentHashMap。
