什么是散列表
散列表又被稱為哈希表，包含一個鍵key、一個值value它們之間的對應關系是一對一，散列表就提供了鍵key和值value的對應關系，基本結構如下。
鍵值不會重復所以通過鍵就可以找到與之對應的值，一般散列表查詢的時間復雜度為O(1)，那么為什么散列表會這么快呢？
哈希函數
在分析原因之前我們需要知道散列表其存儲底層是數組，正是利用了數組下標獲取元素效率高的特點，但我們需要注意的是數組下標是整型，而散列表的鍵值可不一定是整型，為什么散列表還能通過鍵高效獲取值呢？這就需要聊到哈希函數，所謂的哈希函數就是將散列表的鍵轉換為存儲數組的下標，再通過下標獲取散列表的值，獲取過程如下。
哈希函數如何實現
那么哈希函數如何實現呢？每個語言會有自己的計算邏輯，這里以JAVA為例。如果想要自己設計一個哈希函數第一步是需要取到每個鍵唯一且為整數的標識，在JAVA中有這種功能的函數被稱為hashCode方法，是每個對象唯一的標識，所以鍵對應的哈希函數就可以采用如下邏輯（JAVA中必然不可能如此簡單還會通過一系列的位運算提升效率，這里只是簡單討論）。
// key.hashCode()調用鍵的hashCode方法得到唯一的int值
// arr.length表示散列表底層數組的長度
int index = key.hashCode()%arr.length;
哈希碰撞
無論多好的哈希函數都避免不了的一個問題就是，兩個不相同的哈希值可能計算出來的數組下標為同一個。
假設數組長度為6，需要放入兩個鍵key1和key2，key1的hashCode值為3，key2的hashCode值為9，那么通過與數組長度模運算得到兩個數組下標都是3，如果按照數組的存儲方式，后面存儲的必然會把前面存儲的值覆蓋，這種場景被稱為哈希碰撞。
為解決哈希碰撞提出了兩種方法，分別為鏈表法和開放尋址法。
開放尋址法
開放尋址法其原理就是，當存儲元素的鍵下標被占用時，自動查找下一個空擋位置存放值，如下
存在一個元素Entry2，計算其數組下標為2，也就是Entry3的位置，計算出來的數組下標被占用，那么就往下查找下一個元素但是被Entry4占用，再去查找為空的位置，直到查找到數組下標為4的位置，插入元素保存即可。
這種方法在JAVA中的經典應用就是ThreadLocal~
鏈表法
鏈表法就是將散列表由單純的數組存儲改為數組+鏈表組合的形式存儲，每個數組中的元素都可以理解為鏈表的頭節點，當需要存儲元素時，先判斷該下標元素是否為空如果為空之間作為頭節點插入，如果不為空則將該數組下標元素頭節點指向需要插入的元素。
JAVA中的HashMap就是采用的鏈表法來解決哈希沖突，當然鏈表法不是萬無一失，當鏈表過長那么檢索的效率必然降低因為鏈表檢索需要遍歷鏈表，時間復雜度為O(n)，所以HashMap中還會涉及到擴容，擴容后將所有的元素重新哈希，以此來達到縮短鏈表長度的目的。
