哈希函數和哈希表（散清單）

哈希表的簡單介紹：哈希表是一種實作字典操作的一種有效的資料結構，它是普通數組概念的推廣，由于對普通數組可以直接尋址，使得其的查找的時間複雜度是始終為O(1)的。

一、哈希函數：

若一個函數為哈希函數其必然具有以下四個性質：

①輸入域無窮但對用的輸出域是相對有限的

②若輸入确定，輸出一定确定

③輸出相同，但輸入并不一定相同，也就是輸出不同，輸入可能相同：哈希碰撞

④其具有離散性。也就是每個輸出數的機率是幾乎相同的，也就是在整個s域上是幾乎均勻分布的。（其均衡性性越好，離散性越高，其哈希函數的性能也就越優良）

作用：是用來打亂輸入規律的，他的變換過程很複雜，但是是非随機的，滿足②③性質input(輸入) -> code（哈希值，均勻分布） -> %M（對M取餘） -> 0 - M-1（得到一個0 - M-1的區間）在input很大時，M較小時，我們得到的0 - M-1的區間對應的每一個數也幾乎均勻分布

二、哈希表

輸入域通過哈希函數得到一個輸出域，把輸出域對M進行取餘之後得到一個長度為M的數組，這個數組的每個位置都叫做一個位桶，每個位桶都是幾乎均勻分布的，我們用連結清單來當做每個位桶的資料結構，但是當連結清單的長度達到一定的時候，我們認為就不經濟了，因為查詢或者其它操作的時候消耗的資源很大，我們就會成倍的擴充數組，并重新計算哈希函數，我們可以認為他的額外的空間複雜度為O(n)，但因為擴容是可以離線的，擴充也沒有這麼頻繁，是以我們認為，在查詢的時候的時間複雜度是可以做到O(1)的，在java中實作這種資料結構的很多，經典的就是HashSet和HashMap，因為連結清單我們認為當它在長度超過一定範圍慢了，在jdk1.8之後，位桶的長度大于8的時候，我們采用紅黑樹來替代連結清單這種資料結構。HashSet和HashMap其實都是一樣的（其實都是選擇的拉鍊法去解決的哈希沖突），不同的是，HashSet在每個位桶所對應的資料上，隻有key，而HashMap在每個key上又挂了一個value，也就是HashSet的add(key)方法，和HashMap的put(key,value)方法，HashSet可以根據這個key看是否有這個key，HashMap可以根據key去拿這個value（我們可以認為使用哈希表這種資料結構的增删改查時間複雜都為O(1)的操作，但是常數項比較大，因為哈希函數再計算的時候代價比較高）

對于哈希表這種資料結構，對每個關鍵字去映射到一個位桶裡，因為位桶的數目遠小于關鍵字的數目，是以肯定會産生兩個輸入域的關鍵字會映射到同一個位桶裡，即哈希沖突，如何解決哈希沖突，請看下一篇文章。