散列函數(shù)
通常大家所說的哈希函數(shù)也可以稱為散列函數(shù)，哈希函數(shù)的功能只是將你的目標(biāo)key通過一種映射方法，也可以說是一種函數(shù)運(yùn)算f，最后得到你目標(biāo)的
hashValue = f(key)，這里的函數(shù)f就稱為哈希函數(shù)/散列函數(shù)。
解決哈希沖突
可以看到哈希函數(shù)的選擇是一個很關(guān)鍵的步驟。為了引進(jìn)哈希桶算法，必然要介紹一下哈希沖突，因?yàn)楣Ｍ熬褪菫榱私鉀Q哈希沖突的。舉個例子，有一組序列為[10,11,21,31,38,48,55]，使用的哈希函數(shù)為f(key) = key mod 10
這個時候就產(chǎn)生了沖突了，也就是不同的key通過映射后得到了同樣值的hashvalue。
哈希桶算法（鏈地址）
哈希桶算法其實(shí)就是鏈地址解決沖突的方法
如上面的例子所示，就可以設(shè)置桶的個數(shù)為10，也就是f(key)集合的個數(shù)，而這樣的話，hashvalue就可以作為桶的索引，將10,11分別通過f(key)得到0，1則可將這幾個key放入桶0， 1的首地址所指的內(nèi)存中，然后處理值為21的key，得到hashvalue值為1，這個時候需要放入桶1中，但桶1的首地址已經(jīng)有了元素11，怎么辦？那么就可以為每個桶開辟一片內(nèi)存，內(nèi)存中存放所有hashvalue相同的key，沖突的key之間用單向鏈表進(jìn)行存儲，這樣就解決了哈希沖突，在查找對應(yīng)key的時候，只需要通過key索引到對應(yīng)的桶，然后從桶的首地址對應(yīng)的節(jié)點(diǎn)開始查找，就是鏈表順序找到，對比key的值，直到找到對應(yīng)key的信息，所以，在沖突的時候，特別是沖突率比較高的時候，桶內(nèi)的鏈表就會很長，使得查找效率比較低，而在最壞的情況下，所有的key都對應(yīng)同一個hashvalue，當(dāng)然這種情況不會出現(xiàn)，這樣的哈希函數(shù)選取的也沒有意義了，假設(shè)這種情況出現(xiàn)，那么哈希表就退化成了單鏈表，其他桶內(nèi)存浪費(fèi)，且將查找效率從O(1)直接降到了O(N)，所以上面才說，哈希函數(shù)的選擇也是很關(guān)鍵的。
鏈地址缺點(diǎn)
如果相同元素過多，元素在一個桶內(nèi)部鏈接過長，反而導(dǎo)致時間復(fù)雜度上升。解決思路是桶中元素不再指向鏈表，而指向一個紅黑樹。
