一、什么是散列？
散列 Hash是和順序、鏈接和索引一樣，是存儲集合或者線性表的一種方法。
散列的基本思想是：以集合或線性表中的每個元素的關(guān)鍵字K為自變量，通過一個散列函數(shù) h(K) 得到的結(jié)果，將這個結(jié)果解釋為一塊連續(xù)的存儲空間（如數(shù)組）的地址（如數(shù)組下標(biāo)），將這個元素存儲到這個空間中。
h(K) 稱為散列函數(shù)或者哈希函數(shù)，它實(shí)現(xiàn)了關(guān)鍵字到存儲地址的映射。h(K)的值 稱為散列地址或者哈希地址。存儲空間是線性表進(jìn)行散列存儲的空間，所以稱之為散列表或者哈希表。
二、沖突
如果出現(xiàn)一個待插入的元素的散列地址已經(jīng)被占用，使得該元素?zé)o法直接存入到此單元中，這種現(xiàn)象成為沖突。
我們把不同關(guān)鍵字通過散列函數(shù)后得到相同的散列地址的元素成為同義詞。
- 影響同義詞沖突的三個因素：
裝載因子 a：指散列表中已存入元素數(shù) n 和散列空間大小 m 的比值。a 越小時，沖突可能性越小，但是空間利用率越小。a 一般控制在0.6~0.9為宜。
散列函數(shù)：選擇適當(dāng)?shù)纳⒘泻瘮?shù)講元素均分在各個區(qū)域。
解決沖突的方法
三、散列函數(shù)
- 直接定址法
- 除留余數(shù)法
- 數(shù)字分析法
- 平方取中法
- 折疊法
四、處理沖突的方法
解決沖突的方法分為開放定址法和鏈接法兩種。
開放定址法
開放定址法是從發(fā)生沖突的單元開始，按照一定的次序，從散列表中找出一個空閑的存儲單元，把沖突元素插入到該單元。插入到該單元的元素叫非同義詞元素。
線性探查法
從發(fā)生沖突的單元開始，依次尋找下一個空閑單元。
- 特點(diǎn)：
- 容易造成元素的堆積。
平方探查法
探查序列為 d, d+(1^2), d+(2^2), d+(3^2), ...
- 特點(diǎn)
- 可以避免堆積現(xiàn)象；
- 無法探查到散列表上的所有單元，但至少可以探查到一半的單元。
雙散列函數(shù)探查法
使用兩個散列函數(shù) h1 和 h2，若關(guān)鍵字通過第一個散列函數(shù)得出的下標(biāo) d 沖突的話，探查的增量為 h2(K)。
鏈接法
把發(fā)生沖突的同義詞元素用單鏈表鏈接起來，散列表則保存他們的表頭指針。
- 特點(diǎn)
- 填充因子有可能會大于1；
- 比開放定址法占用更多存儲空間用于存儲表指針。
對比
開放定址法處理沖突的平均查找長度 > 鏈接法 > 任何其他查找方法
五、散列存儲的缺點(diǎn)
- 計算散列地址需要花費(fèi)時間，關(guān)鍵字不是整數(shù)還先要轉(zhuǎn)換為整數(shù)；
- 占用更多的存儲空間，開放定址法的裝載因子小于1，鏈接法則需要空間存儲指針；
- 只能按關(guān)鍵字查找，無法按非關(guān)鍵字查找。
