概念
哈希表（散列表 Hash）是相對于線性表、樹形結(jié)構(gòu)的一種數(shù)據(jù)結(jié)構(gòu)泻蚊，它能在元素的存儲位置和其關(guān)鍵字直接建立某種之間關(guān)系，那么在進行查找時，就無需做或者做很少次的比較湿刽，就能通過這個關(guān)系直接由關(guān)鍵字找到對對應(yīng)的記錄。這就是散列查找法（Hase Search）的思想褐耳，它通過對元素的關(guān)鍵字值進行某種運算诈闺，直接求出元素的地址。即使用關(guān)鍵字到地址的直接轉(zhuǎn)換方法铃芦，而不需要反復(fù)比較买雾。因此，散列查找法又叫雜湊法或者散列法杨帽。
- 散列函數(shù)和散列地址：在記錄的存儲位置p和關(guān)鍵字key直接建立一個確定的對應(yīng)關(guān)系H，使p=H(key)嗤军，稱這個對應(yīng)關(guān)系H為散列函數(shù)注盈，p為散列地址。
- 散列表：一個有限連續(xù)的地址空間叙赚，用以存儲散列函數(shù)計算得到相對于散列地址的數(shù)據(jù)記錄老客，通常是一個一位數(shù)組僚饭。
- 沖突和同義詞：對不同的關(guān)鍵字可能得到統(tǒng)一散列地址，即key1≠key2胧砰，而H(key1)=H(key2)鳍鸵，這種現(xiàn)象稱為沖突。具有相同函數(shù)值的關(guān)鍵字對該散列函數(shù)來說稱作同義詞尉间。
如何解決哈希沖突
選擇一個好的散列函數(shù)可以在一定程度上減少沖突偿乖，但在實際應(yīng)用中，很難完全避免發(fā)生沖突哲嘲，所以選擇一個有效的處理沖突的方法是散列表的另一個關(guān)鍵問題贪薪。
處理沖突的方法與散列表本身的組織形式有關(guān)。按組織形式的不同眠副，通常分為兩大類：開放地址法和鏈地址法画切。
開放地址法
開放地址法的基本思想是：把記錄都存儲在散列表數(shù)組中，當(dāng)某一記錄關(guān)鍵字key的初始散列地址H0=H(key)發(fā)生沖突時囱怕，以H0為基礎(chǔ)霍弹，采取合適方法計算得到另一地址H1，如果H1仍然發(fā)生沖突娃弓，已H1位基礎(chǔ)再求下一個地址H2典格，若H2仍然沖突，再求得H3忘闻，以此類推钝计，直至Hk不發(fā)生沖突為止，則Hk為該記錄在表中的散列地址齐佳。
根據(jù)計算方法私恬，可以分為以下三種探測方法：
- 線性探測法：這種探測方法可以將散列表假想成一個循環(huán)表。發(fā)生沖突時炼吴，從沖突地址的下一單元順序?qū)ふ铱諉卧久绻阶詈笠粋€位置也沒有找到空單元，則回到表頭開始繼續(xù)查找硅蹦，直到找到一個空位荣德，就把此元素放入此空位中。如果找不到空位童芹，則說明散列表已滿涮瞻，需要進行溢出操作。
di = 1,2,3,4,...,m-1 - 二次探測法：
di = 12,-12,22,-22,...k2,-k2(k≤m/2) - 偽隨機探測法：
di = 偽隨機數(shù)序列
線性探測法會在出現(xiàn)在處理過程中發(fā)生沖突的發(fā)生第一個散列地址不同的記錄爭奪同一個后繼散列地址的現(xiàn)象假褪，稱為二次聚集或者堆積署咽。即在處理同義詞的沖突過程中，又添加了非同義詞的沖突。
它的優(yōu)點是宁否，只要散列表未滿窒升，就一定能找到一個不發(fā)生沖突的地址
而二次探測法和偽隨機數(shù)探測法可以避免出現(xiàn)二次聚集現(xiàn)象，但是不保證一定能找到不發(fā)生沖突的地址慕匠。
鏈地址法
鏈地址法的基本思想是：把具有相同散列地址的記錄放在同一個單鏈表中饱须，稱為同義詞鏈表。有m個散列地址就有m個單鏈表台谊，同時用數(shù)組HT[0..m-1]存放各個鏈表的頭指針蓉媳，凡是散列地址為i的記錄都以結(jié)點的方式插入已HT[i]為頭結(jié)點的單鏈表中。
