哈希（散列）方法是對插入的數據通過哈希函數計算出一個哈希地值，并將這個哈希地址作為儲存改數據的地址，這樣下次再查找這個數據時，只需要通過哈希函數再獲取到該地址然后直接去拿就好
這樣就做到了不經過任何比較，一次就能從表中拿到元素的O(1)的時間復雜度，他將哈希函數計算出來的值和目標值建立了一一映射的關系
比如有一個數組大小為5? 下標為0 1 2 3 4
再插入值時，我對他進行 %5 取余操作，再儲存2時就映射到了下標2，于是將值放到數組下標2的位置，%5 這就是一個簡單的哈希函數而構建出來的表（這個數組）就稱為哈希表（散列表）
沖突
對于剛剛的例子，很容易看出單數據多了，就會出現不同的數據映射到相同的位置，這種不同的數據通過哈希函數計算出來了相同的哈希地址，就稱為哈希沖突或者哈希碰撞，把具有相同哈希值但是不是相同的數據稱為同義詞
沖突的避免
要知道哈希沖突時不可解決的，但數據量大之后，什么可能都會出現，而我們能做的是減低沖突率
避免哈希函數的最有效的辦法是優化哈希函數，哈希函數計算出來的地址應該要平均分布到空間中，如果有m個地址，那么哈希函數計算出來的值就應該平均的分布到0 - m-1
負載因子的調節
負載因子的定義 α = 數據的總數 / 哈希表的長度
α是哈希函數裝滿程度的標注因子，且發送哈希沖突的可能性和α成正比，因為數據越多，發送哈希沖突的可能性更大
所以要降低沖突率就要減低負載因子，而儲存數據的總數是不能變的，于是需要擴大哈希表的大小
沖突的解決分為開散列和閉散列
閉散列
當沖突發生時，哈希表還沒有被填滿，所以表中一定還有空的位置，那么就找出這個空的位置來放沖突元素
線性探測
若計算出的哈希地址沖突了，就往后繼續探測一個空的位置，直接放入
再刪除元素的時候，采用的是標志位的偽刪除法，因為使用線性探測法，一個哈希地址對應的有可能是多個元素，而這其他的元素，要基于這個哈希地址來往后查找，如果這個位置被刪除了，那么就表示這里就沒有元素，而和他沖突的元素也就不存在了
二次探測
線性探測的缺點是沖突元素容易產生堆積，這于尋找下一個位置有關系，因為是挨個挨個找到空位置，而二次探測為了避免該問題是跳著尋找空位置的，尋找下標的公式是
，也可以是h0-i^2，Hi是最終的下標，H0是計算出來的沖突地址，m是表大小，i是1 2 3.... 是動態遞增的，沖突一次i就加一
有研究表明，但α 小于0.5時，新的數據一定能插入，且任何位置都不會被探測倆次，因此再還有一般的空位置時，就不會存在沖突的情況，那么再搜索時就不用考慮沖突的情況，但如果大于了0.5就要考慮擴容表了
所以哈希表對空間的利用率比較底，這是哈希的缺陷
開散列 哈希桶
開散列又叫鏈地址法，將沖突的元素歸于一個集合，每一個子集稱為一個桶桶中的元素又鏈表聯系起來
實現：在哈希表中儲存的是一個鏈表，當沖突的元素就直接儲存再這個鏈表中，再查找時就先通過哈希函數找到這個鏈表，再遍歷這個鏈表來獲取到元素，因為沖突的次數一般都是常熟級的，所以遍歷這個鏈表的時間也可以近似忽略，所以搜索還是O(1) 的復雜度
但當元素過多之后，遍歷這個鏈表所需要的時間也不能被接受了，于是這個桶也可以是另一個哈希表或者是一顆搜索樹
雖然哈希的發展是一直在和哈希沖突做斗爭，但是我們在平時使用時，哈希沖突發送的情況也不是很頻繁，對于增刪查改的時間復雜度視為是O(1)? 的
)
