散列表也叫作哈希表（hash table），

這種數(shù)據(jù)結(jié)構(gòu)提供了鍵（Key）和值（Value）的映射關(guān)系。

只要給出一個(gè)Key，就可以高效查找到它所匹配的Value，時(shí)間復(fù)雜度接近于O(1)。

散列表在本質(zhì)上也是一個(gè)數(shù)組。

散列表的Key則是以字符串類型為主的，

通過hash函數(shù)把Key和數(shù)組下標(biāo)進(jìn)行轉(zhuǎn)換，

作用是把任意長度的輸入通過散列算法轉(zhuǎn)換成固定類型、固定長度的散列值。

//數(shù)組下標(biāo)=取key的hashcode模數(shù)組的長度后的余數(shù)index = HashCode (Key) % Array.length//index的范圍是（0-9）int index=Math.abs("Hello".hashCode())%10;

這是最簡單的計(jì)算方式 還有很多hash函數(shù)：CRC16、CRC32、siphash 、murmurHash、times 33等，

此種Hash計(jì)算方式為固定Hash方式，也稱為傳統(tǒng)Hash。

該方式在數(shù)組固定時(shí)，可以快速檢索 但當(dāng)數(shù)組長度變化時(shí)，需要重新計(jì)算數(shù)組下標(biāo)，此時(shí)根據(jù)key檢索將出現(xiàn)問題，

所以說傳統(tǒng)Hash法雖然比較簡單，但不利于擴(kuò)展，如果要擴(kuò)展可以采用一致性Hash法。

1、寫操作（put）

寫操作就是在散列表中插入新的鍵值對(duì)（在JDK中叫作Entry或Node）

第1步，通過哈希函數(shù)，把Key轉(zhuǎn)化成數(shù)組下標(biāo)

第2步，如果數(shù)組下標(biāo)對(duì)應(yīng)的位置沒有元素，就把這個(gè)Entry填充到數(shù)組下標(biāo)的位置。

2、Hash沖突（碰撞）

由于數(shù)組的長度是有限的，當(dāng)插入的Entry越來越多時(shí)，不同的Key通過哈希函數(shù)獲得的下標(biāo)有可能是相同的，這種情況，就叫作哈希沖突。

3、解決Hash沖突方案

【1】開放尋址法

開放尋址法的原理是當(dāng)一個(gè)Key通過哈希函數(shù)獲得對(duì)應(yīng)的數(shù)組下標(biāo)已被占用時(shí)，就尋找下一個(gè)空檔位置

在Java中，ThreadLocal所使用的就是開放尋址法。

【2】鏈表法

數(shù)組的每一個(gè)元素不僅是一個(gè)Entry對(duì)象，還是一個(gè)鏈表的頭節(jié)點(diǎn)。

每一個(gè)Entry對(duì)象通過next指針 指向它的下一個(gè)Entry節(jié)點(diǎn)。

當(dāng)新來的Entry映射到與之沖突的數(shù)組位置時(shí)，只需要插入到對(duì)應(yīng)的鏈表中即可，默認(rèn)next指向null。

public class Node { String key; String value; // 指向下一個(gè)結(jié)點(diǎn) Node next; public Node(String key, String value, Node next) { this.key = key; this.value = value; this.next = next; }}public class ListNode { Node head; //頭結(jié)點(diǎn) public void addNode(String key, String value) { //在外界設(shè)置好head了 if (head == null) return; // 創(chuàng)建結(jié)點(diǎn) Node node = new Node(key, value, null); // 臨時(shí)變量 Node tmp = head; //循環(huán)單鏈表 while (true) { //key相同覆蓋值 從head開始 if (key.equals(tmp.key)) { tmp.value = value; } if (tmp.next == null) { break; } //指向下一個(gè) tmp = tmp.next; } //當(dāng)前尾結(jié)點(diǎn)的下一個(gè)指針指向新增的結(jié)點(diǎn) tmp.next = node; }}public class MyHashMap { //數(shù)組初始化 2的n次方 ListNode[] map = new ListNode[8]; //ListNode的個(gè)數(shù) int size; public void put(String key, String value) { //該擴(kuò)容了 if (size >= map.length * 0.75) { System.out.println("map需要擴(kuò)容"); return; } //計(jì)算索引 數(shù)組下標(biāo) int index = Math.abs(key.hashCode()) % map.length; //獲得該下標(biāo)處的ListNode ListNode ln = map[index]; //該下標(biāo)處無值 if (ln == null) { //創(chuàng)建單鏈表 ListNode lnNew = new ListNode(); //創(chuàng)建頭結(jié)點(diǎn) Node head = new Node(key, value, null); //掛載頭結(jié)點(diǎn) lnNew.head = head; //把單鏈放到數(shù)組里 map[index] = lnNew; size++; } //該下標(biāo)有值，hash碰撞 else { //單鏈表掛結(jié)點(diǎn) ln.addNode(key, value); } }}

當(dāng)根據(jù)key查找值的時(shí)候，在index=2的位置是一個(gè)單鏈表 遍歷該單鏈表，再根據(jù)key即可取值。

4、讀操作（get）

讀操作就是通過給定的Key，在散列表中查找對(duì)應(yīng)的Value。

第1步，通過哈希函數(shù)，把Key轉(zhuǎn)化成數(shù)組下標(biāo)。

第2步，找到數(shù)組下標(biāo)所對(duì)應(yīng)的元素，如果key不正確，說明產(chǎn)生了hash沖突， 則順著頭節(jié)點(diǎn)遍歷該單鏈表，再根據(jù)key即可取值。

public class ListNode { Node head; //頭結(jié)點(diǎn) public String getVal(String key) { if (head == null) return null; //只有一個(gè)結(jié)點(diǎn) if (head.next == null) { return head.value; } //遍歷單鏈表 else { Node tmp = head; while (tmp != null) { //找到匹配的key if (key.equals(tmp.key)) { return tmp.value; } //指向下一個(gè) tmp = tmp.next; } return null; } }}public class MyHashMap { //數(shù)組初始化 2的n次方 ListNode[] map = new ListNode[8]; //ListNode的個(gè)數(shù) int size; public String get(String key){ int index=Math.abs(key.hashCode())%map.length; ListNode ln=map[index]; if(ln==null) return null; return ln.getVal(key); }}5、Hash擴(kuò)容（resize）

散列表是基于數(shù)組實(shí)現(xiàn)的，所以散列表需要擴(kuò)容。

當(dāng)經(jīng)過多次元素插入，散列表達(dá)到一定飽和度時(shí)，Key映射位置發(fā)生沖突的概率會(huì)逐漸提高。

這樣 一來，大量元素?fù)頂D在相同的數(shù)組下標(biāo)位置，形成很長的鏈表，對(duì)后續(xù)插入操作和查詢操作的性能都有很大影響。

影響擴(kuò)容的因素有兩個(gè)

Capacity：HashMap的當(dāng)前長度；

LoadFactor：HashMap的負(fù)載因子（閾值），默認(rèn)值為0.75f。

當(dāng)HashMap.Size >= Capacity×LoadFactor時(shí)，需要進(jìn)行擴(kuò)容 擴(kuò)容的步驟：

【1】 擴(kuò)容，創(chuàng)建一個(gè)新的Entry空數(shù)組，長度是原數(shù)組的2倍

【2】 重新Hash，遍歷原Entry數(shù)組，把所有的Entry重新Hash到新數(shù)組中

關(guān)于HashMap的實(shí)現(xiàn)，JDK 8和以前的版本有著很大的不同。當(dāng)多個(gè)Entry被Hash到同一個(gè)數(shù)組下標(biāo)位 置時(shí)，為了提升插入和查找的效率，HashMap會(huì)把Entry的鏈表轉(zhuǎn)化為紅黑樹這種數(shù)據(jù)結(jié)構(gòu)。

JDK1.8前在HashMap擴(kuò)容時(shí)，會(huì)反序單鏈表，這樣在高并發(fā)時(shí)會(huì)有死循環(huán)的可能。

四、時(shí)間復(fù)雜度

1、Hash擴(kuò)容：O(n) n是數(shù)組元素個(gè)數(shù) rehash

2、Hash沖突寫單鏈表：O(m)

3、寫操作： O(1) + O(m) = O(m) m為單鏈元素個(gè)數(shù)

4、Hash沖突讀單鏈表：O(m) m為單鏈元素個(gè)數(shù)

5、讀操作：O(1) + O(m) m為單鏈元素個(gè)數(shù)

1、優(yōu)點(diǎn)：讀寫快

2、缺點(diǎn)：哈希表中的元素是沒有被排序的、Hash沖突、擴(kuò)容重新計(jì)算

1、HashMap

JDK1.7中HashMap使用一個(gè)table數(shù)組來存儲(chǔ)數(shù)據(jù)，

用key的hashcode取模來決定key會(huì)被放到數(shù)組里的位置，

如果hashcode相同，或者h(yuǎn)ashcode取模后的結(jié)果相同，

那么這些key會(huì)被定位到Entry數(shù)組的 同一個(gè)格子里，這些key會(huì)形成一個(gè)鏈表，

在極端情況下比如說所有key的hashcode都相同，將會(huì)導(dǎo)致這個(gè)鏈表會(huì)很長，

那么put/get操作需要遍歷整個(gè)鏈表，那么最差情況下時(shí)間復(fù)雜度變?yōu)镺（n）。

擴(kuò)容死鏈針對(duì)JDK1.7中的這個(gè)性能缺陷，JDK1.8中的table數(shù)組中可能存放的是鏈表結(jié)構(gòu)，也可能存放的是紅黑樹結(jié)構(gòu)，

如果鏈表中節(jié)點(diǎn)數(shù)量不超過8個(gè)則使用鏈表存儲(chǔ)，

超過8個(gè)會(huì)調(diào)用treeifyBin函數(shù)，將鏈表轉(zhuǎn)換紅黑樹。那么即使所有key的hashcode完全相同，由于紅黑樹的特點(diǎn)，查找某個(gè)特定元素，也只需要 O（logn）的開銷。

2、字典

Redis字典dict又稱散列表（hash），是用來存儲(chǔ)鍵值對(duì)的一種數(shù)據(jù)結(jié)構(gòu)。

Redis整個(gè)數(shù)據(jù)庫是用字典來存儲(chǔ)的。（K-V結(jié)構(gòu)）

對(duì)Redis進(jìn)行CURD操作其實(shí)就是對(duì)字典中的數(shù)據(jù)進(jìn)行CURD操作。

Redis字典實(shí)現(xiàn)包括：字典(dict)、Hash表(dictht)、Hash表節(jié)點(diǎn)(dictEntry)。

3、布隆過濾器

布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個(gè)很長的二進(jìn)制向量和一系列隨機(jī) hash映射函數(shù)。

布隆過濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都遠(yuǎn)遠(yuǎn)超過一般 的算法。

布隆過濾器的原理是，當(dāng)一個(gè)元素被加入集合時(shí)，通過K個(gè)Hash函數(shù)將這個(gè)元素映射成一個(gè)數(shù)組中的K 個(gè)點(diǎn)，把它們置為1。

檢索時(shí)，我們只要看看這些點(diǎn)是不是都是1就（大約）知道集合中有沒有它了：如果這些點(diǎn)有任何一個(gè)0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。

這就是布隆過濾器的基本思想。