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