散列表也叫作哈希表（hash table），
這種數(shù)據(jù)結(jié)構(gòu)提供了鍵（Key）和值（Value）的映射關(guān)系。
只要給出一個Key，就可以高效查找到它所匹配的Value，時間復(fù)雜度接近于O(1)。
二、存儲原理散列表在本質(zhì)上也是一個數(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;
這是最簡單的計算方式 還有很多hash函數(shù)：CRC16、CRC32、siphash 、murmurHash、times 33等，
此種Hash計算方式為固定Hash方式，也稱為傳統(tǒng)Hash。
該方式在數(shù)組固定時，可以快速檢索 但當(dāng)數(shù)組長度變化時，需要重新計算數(shù)組下標(biāo)，此時根據(jù)key檢索將出現(xiàn)問題，
所以說傳統(tǒng)Hash法雖然比較簡單，但不利于擴(kuò)展，如果要擴(kuò)展可以采用一致性Hash法。
三、操作1、寫操作（put）
寫操作就是在散列表中插入新的鍵值對（在JDK中叫作Entry或Node）
第1步，通過哈希函數(shù)，把Key轉(zhuǎn)化成數(shù)組下標(biāo)
第2步，如果數(shù)組下標(biāo)對應(yīng)的位置沒有元素，就把這個Entry填充到數(shù)組下標(biāo)的位置。
2、Hash沖突（碰撞）
由于數(shù)組的長度是有限的，當(dāng)插入的Entry越來越多時，不同的Key通過哈希函數(shù)獲得的下標(biāo)有可能是相同的，這種情況，就叫作哈希沖突。
3、解決Hash沖突方案
【1】開放尋址法
開放尋址法的原理是當(dāng)一個Key通過哈希函數(shù)獲得對應(yīng)的數(shù)組下標(biāo)已被占用時，就尋找下一個空檔位置
在Java中，ThreadLocal所使用的就是開放尋址法。
【2】鏈表法
數(shù)組的每一個元素不僅是一個Entry對象，還是一個鏈表的頭節(jié)點。
每一個Entry對象通過next指針 指向它的下一個Entry節(jié)點。
當(dāng)新來的Entry映射到與之沖突的數(shù)組位置時，只需要插入到對應(yīng)的鏈表中即可，默認(rèn)next指向null。
public class Node { String key; String value; // 指向下一個結(jié)點 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é)點 public void addNode(String key, String value) { //在外界設(shè)置好head了 if (head == null) return; // 創(chuàng)建結(jié)點 Node node = new Node(key, value, null); // 臨時變量 Node tmp = head; //循環(huán)單鏈表 while (true) { //key相同覆蓋值 從head開始 if (key.equals(tmp.key)) { tmp.value = value; } if (tmp.next == null) { break; } //指向下一個 tmp = tmp.next; } //當(dāng)前尾結(jié)點的下一個指針指向新增的結(jié)點 tmp.next = node; }}public class MyHashMap { //數(shù)組初始化 2的n次方 ListNode[] map = new ListNode[8]; //ListNode的個數(shù) int size; public void put(String key, String value) { //該擴(kuò)容了 if (size >= map.length * 0.75) { System.out.println("map需要擴(kuò)容"); return; } //計算索引 數(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é)點 Node head = new Node(key, value, null); //掛載頭結(jié)點 lnNew.head = head; //把單鏈放到數(shù)組里 map[index] = lnNew; size++; } //該下標(biāo)有值，hash碰撞 else { //單鏈表掛結(jié)點 ln.addNode(key, value); } }}
當(dāng)根據(jù)key查找值的時候，在index=2的位置是一個單鏈表 遍歷該單鏈表，再根據(jù)key即可取值。
4、讀操作（get）
讀操作就是通過給定的Key，在散列表中查找對應(yīng)的Value。
第1步，通過哈希函數(shù)，把Key轉(zhuǎn)化成數(shù)組下標(biāo)。
第2步，找到數(shù)組下標(biāo)所對應(yīng)的元素，如果key不正確，說明產(chǎn)生了hash沖突， 則順著頭節(jié)點遍歷該單鏈表，再根據(jù)key即可取值。
public class ListNode { Node head; //頭結(jié)點 public String getVal(String key) { if (head == null) return null; //只有一個結(jié)點 if (head.next == null) { return head.value; } //遍歷單鏈表 else { Node tmp = head; while (tmp != null) { //找到匹配的key if (key.equals(tmp.key)) { return tmp.value; } //指向下一個 tmp = tmp.next; } return null; } }}public class MyHashMap { //數(shù)組初始化 2的n次方 ListNode[] map = new ListNode[8]; //ListNode的個數(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ù)組實現(xiàn)的，所以散列表需要擴(kuò)容。
當(dāng)經(jīng)過多次元素插入，散列表達(dá)到一定飽和度時，Key映射位置發(fā)生沖突的概率會逐漸提高。
這樣 一來，大量元素?fù)頂D在相同的數(shù)組下標(biāo)位置，形成很長的鏈表，對后續(xù)插入操作和查詢操作的性能都有很大影響。
影響擴(kuò)容的因素有兩個
Capacity：HashMap的當(dāng)前長度；
LoadFactor：HashMap的負(fù)載因子（閾值），默認(rèn)值為0.75f。
當(dāng)HashMap.Size >= Capacity×LoadFactor時，需要進(jìn)行擴(kuò)容 擴(kuò)容的步驟：
【1】 擴(kuò)容，創(chuàng)建一個新的Entry空數(shù)組，長度是原數(shù)組的2倍
【2】 重新Hash，遍歷原Entry數(shù)組，把所有的Entry重新Hash到新數(shù)組中
關(guān)于HashMap的實現(xiàn)，JDK 8和以前的版本有著很大的不同。當(dāng)多個Entry被Hash到同一個數(shù)組下標(biāo)位 置時，為了提升插入和查找的效率，HashMap會把Entry的鏈表轉(zhuǎn)化為紅黑樹這種數(shù)據(jù)結(jié)構(gòu)。
JDK1.8前在HashMap擴(kuò)容時，會反序單鏈表，這樣在高并發(fā)時會有死循環(huán)的可能。
四、時間復(fù)雜度
1、Hash擴(kuò)容：O(n) n是數(shù)組元素個數(shù) rehash
2、Hash沖突寫單鏈表：O(m)
3、寫操作： O(1) + O(m) = O(m) m為單鏈元素個數(shù)
4、Hash沖突讀單鏈表：O(m) m為單鏈元素個數(shù)
5、讀操作：O(1) + O(m) m為單鏈元素個數(shù)
五、優(yōu)缺點1、優(yōu)點：讀寫快
2、缺點：哈希表中的元素是沒有被排序的、Hash沖突、擴(kuò)容重新計算
六、應(yīng)用1、HashMap
JDK1.7中HashMap使用一個table數(shù)組來存儲數(shù)據(jù)，
用key的hashcode取模來決定key會被放到數(shù)組里的位置，
如果hashcode相同，或者h(yuǎn)ashcode取模后的結(jié)果相同，
那么這些key會被定位到Entry數(shù)組的 同一個格子里，這些key會形成一個鏈表，
在極端情況下比如說所有key的hashcode都相同，將會導(dǎo)致這個鏈表會很長，
那么put/get操作需要遍歷整個鏈表，那么最差情況下時間復(fù)雜度變?yōu)镺（n）。
擴(kuò)容死鏈針對JDK1.7中的這個性能缺陷，JDK1.8中的table數(shù)組中可能存放的是鏈表結(jié)構(gòu)，也可能存放的是紅黑樹結(jié)構(gòu)，
如果鏈表中節(jié)點數(shù)量不超過8個則使用鏈表存儲，
超過8個會調(diào)用treeifyBin函數(shù)，將鏈表轉(zhuǎn)換紅黑樹。那么即使所有key的hashcode完全相同，由于紅黑樹的特點，查找某個特定元素，也只需要 O（logn）的開銷。
2、字典
Redis字典dict又稱散列表（hash），是用來存儲鍵值對的一種數(shù)據(jù)結(jié)構(gòu)。
Redis整個數(shù)據(jù)庫是用字典來存儲的。（K-V結(jié)構(gòu)）
對Redis進(jìn)行CURD操作其實就是對字典中的數(shù)據(jù)進(jìn)行CURD操作。
Redis字典實現(xiàn)包括：字典(dict)、Hash表(dictht)、Hash表節(jié)點(dictEntry)。
3、布隆過濾器
布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進(jìn)制向量和一系列隨機(jī) hash映射函數(shù)。
布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點是空間效率和查詢時間都遠(yuǎn)遠(yuǎn)超過一般 的算法。
布隆過濾器的原理是，當(dāng)一個元素被加入集合時，通過K個Hash函數(shù)將這個元素映射成一個數(shù)組中的K 個點，把它們置為1。
檢索時，我們只要看看這些點是不是都是1就（大約）知道集合中有沒有它了：如果這些點有任何一個0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。
這就是布隆過濾器的基本思想。
