概念
哈希表（散列表 Hash）是相對(duì)于線性表、樹形結(jié)構(gòu)的一種數(shù)據(jù)結(jié)構(gòu)，它能在元素的存儲(chǔ)位置和其關(guān)鍵字直接建立某種之間關(guān)系，那么在進(jìn)行查找時(shí)，就無需做或者做很少次的比較，就能通過這個(gè)關(guān)系直接由關(guān)鍵字找到對(duì)對(duì)應(yīng)的記錄。這就是散列查找法（Hase Search）的思想，它通過對(duì)元素的關(guān)鍵字值進(jìn)行某種運(yùn)算，直接求出元素的地址。即使用關(guān)鍵字到地址的直接轉(zhuǎn)換方法，而不需要反復(fù)比較。因此，散列查找法又叫雜湊法或者散列法。
- 散列函數(shù)和散列地址：在記錄的存儲(chǔ)位置p和關(guān)鍵字key直接建立一個(gè)確定的對(duì)應(yīng)關(guān)系H，使p=H(key)，稱這個(gè)對(duì)應(yīng)關(guān)系H為散列函數(shù)，p為散列地址。
- 散列表：一個(gè)有限連續(xù)的地址空間，用以存儲(chǔ)散列函數(shù)計(jì)算得到相對(duì)于散列地址的數(shù)據(jù)記錄，通常是一個(gè)一位數(shù)組。
- 沖突和同義詞：對(duì)不同的關(guān)鍵字可能得到統(tǒng)一散列地址，即key1≠key2，而H(key1)=H(key2)，這種現(xiàn)象稱為沖突。具有相同函數(shù)值的關(guān)鍵字對(duì)該散列函數(shù)來說稱作同義詞。
如何解決哈希沖突
選擇一個(gè)好的散列函數(shù)可以在一定程度上減少?zèng)_突，但在實(shí)際應(yīng)用中，很難完全避免發(fā)生沖突，所以選擇一個(gè)有效的處理沖突的方法是散列表的另一個(gè)關(guān)鍵問題。
處理沖突的方法與散列表本身的組織形式有關(guān)。按組織形式的不同，通常分為兩大類：開放地址法和鏈地址法。
開放地址法
開放地址法的基本思想是：把記錄都存儲(chǔ)在散列表數(shù)組中，當(dāng)某一記錄關(guān)鍵字key的初始散列地址H0=H(key)發(fā)生沖突時(shí)，以H0為基礎(chǔ)，采取合適方法計(jì)算得到另一地址H1，如果H1仍然發(fā)生沖突，已H1位基礎(chǔ)再求下一個(gè)地址H2，若H2仍然沖突，再求得H3，以此類推，直至Hk不發(fā)生沖突為止，則Hk為該記錄在表中的散列地址。
根據(jù)計(jì)算方法，可以分為以下三種探測(cè)方法：
- 線性探測(cè)法：這種探測(cè)方法可以將散列表假想成一個(gè)循環(huán)表。發(fā)生沖突時(shí)，從沖突地址的下一單元順序?qū)ふ铱諉卧绻阶詈笠粋€(gè)位置也沒有找到空單元，則回到表頭開始繼續(xù)查找，直到找到一個(gè)空位，就把此元素放入此空位中。如果找不到空位，則說明散列表已滿，需要進(jìn)行溢出操作。
di = 1,2,3,4,...,m-1 - 二次探測(cè)法：
di = 12,-12,22,-22,...k2,-k2(k≤m/2) - 偽隨機(jī)探測(cè)法：
di = 偽隨機(jī)數(shù)序列
線性探測(cè)法會(huì)在出現(xiàn)在處理過程中發(fā)生沖突的發(fā)生第一個(gè)散列地址不同的記錄爭(zhēng)奪同一個(gè)后繼散列地址的現(xiàn)象，稱為二次聚集或者堆積。即在處理同義詞的沖突過程中，又添加了非同義詞的沖突。
它的優(yōu)點(diǎn)是，只要散列表未滿，就一定能找到一個(gè)不發(fā)生沖突的地址
而二次探測(cè)法和偽隨機(jī)數(shù)探測(cè)法可以避免出現(xiàn)二次聚集現(xiàn)象，但是不保證一定能找到不發(fā)生沖突的地址。
鏈地址法
鏈地址法的基本思想是：把具有相同散列地址的記錄放在同一個(gè)單鏈表中，稱為同義詞鏈表。有m個(gè)散列地址就有m個(gè)單鏈表，同時(shí)用數(shù)組HT[0..m-1]存放各個(gè)鏈表的頭指針，凡是散列地址為i的記錄都以結(jié)點(diǎn)的方式插入已HT[i]為頭結(jié)點(diǎn)的單鏈表中。
