一、什么是散列谴仙？
散列 Hash是和順序迂求、鏈接和索引一樣，是存儲(chǔ)集合或者線性表的一種方法晃跺。
散列的基本思想是：以集合或線性表中的每個(gè)元素的關(guān)鍵字K為自變量揩局，通過一個(gè)散列函數(shù) h(K) 得到的結(jié)果，將這個(gè)結(jié)果解釋為一塊連續(xù)的存儲(chǔ)空間（如數(shù)組）的地址（如數(shù)組下標(biāo)）哼审，將這個(gè)元素存儲(chǔ)到這個(gè)空間中谐腰。
h(K) 稱為散列函數(shù)或者哈希函數(shù)，它實(shí)現(xiàn)了關(guān)鍵字到存儲(chǔ)地址的映射涩盾。h(K)的值 稱為散列地址或者哈希地址十气。存儲(chǔ)空間是線性表進(jìn)行散列存儲(chǔ)的空間，所以稱之為散列表或者哈希表春霍。
二砸西、沖突
如果出現(xiàn)一個(gè)待插入的元素的散列地址已經(jīng)被占用，使得該元素?zé)o法直接存入到此單元中址儒，這種現(xiàn)象成為沖突芹枷。
我們把不同關(guān)鍵字通過散列函數(shù)后得到相同的散列地址的元素成為同義詞。
- 影響同義詞沖突的三個(gè)因素：
裝載因子 a：指散列表中已存入元素?cái)?shù) n 和散列空間大小 m 的比值莲趣。a 越小時(shí)鸳慈，沖突可能性越小，但是空間利用率越小喧伞。a 一般控制在0.6~0.9為宜走芋。
散列函數(shù)：選擇適當(dāng)?shù)纳⒘泻瘮?shù)講元素均分在各個(gè)區(qū)域。
解決沖突的方法
三潘鲫、散列函數(shù)
- 直接定址法
- 除留余數(shù)法
- 數(shù)字分析法
- 平方取中法
- 折疊法
四翁逞、處理沖突的方法
解決沖突的方法分為開放定址法和鏈接法兩種。
開放定址法
開放定址法是從發(fā)生沖突的單元開始溉仑，按照一定的次序挖函，從散列表中找出一個(gè)空閑的存儲(chǔ)單元，把沖突元素插入到該單元浊竟。插入到該單元的元素叫非同義詞元素怨喘。
線性探查法
從發(fā)生沖突的單元開始，依次尋找下一個(gè)空閑單元振定。
- 特點(diǎn)：
- 容易造成元素的堆積哲思。
平方探查法
探查序列為 d, d+(1^2), d+(2^2), d+(3^2), ...
- 特點(diǎn)
- 可以避免堆積現(xiàn)象；
- 無法探查到散列表上的所有單元吩案，但至少可以探查到一半的單元棚赔。
雙散列函數(shù)探查法
使用兩個(gè)散列函數(shù) h1 和 h2，若關(guān)鍵字通過第一個(gè)散列函數(shù)得出的下標(biāo) d 沖突的話，探查的增量為 h2(K)靠益。
鏈接法
把發(fā)生沖突的同義詞元素用單鏈表鏈接起來丧肴，散列表則保存他們的表頭指針。
- 特點(diǎn)
- 填充因子有可能會(huì)大于1胧后；
- 比開放定址法占用更多存儲(chǔ)空間用于存儲(chǔ)表指針芋浮。
對(duì)比
開放定址法處理沖突的平均查找長(zhǎng)度 > 鏈接法 > 任何其他查找方法
五、散列存儲(chǔ)的缺點(diǎn)
- 計(jì)算散列地址需要花費(fèi)時(shí)間壳快，關(guān)鍵字不是整數(shù)還先要轉(zhuǎn)換為整數(shù)纸巷；
- 占用更多的存儲(chǔ)空間，開放定址法的裝載因子小于1眶痰，鏈接法則需要空間存儲(chǔ)指針瘤旨；
- 只能按關(guān)鍵字查找，無法按非關(guān)鍵字查找竖伯。
