哈希法-哈希表介紹
??哈希法又稱散列法贮乳、雜湊法以及關(guān)鍵字地址計算法等，相應(yīng)的表稱為哈希表恬惯。這種方法的基本思想是：首先在元素的關(guān)鍵字k和元素的存儲位置p之間建立一個對應(yīng)關(guān)系f向拆，使得p=f(k)，f稱為哈希函數(shù)酪耳。創(chuàng)建哈希表時浓恳，把關(guān)鍵字為k的元素直接存入地址為f(k)的單元；以后當查找關(guān)鍵字為k的元素時碗暗，再利用哈希函數(shù)計算出該元素的存儲位置p=f(k)颈将，從而達到按關(guān)鍵字直接存取元素的目的。
??當關(guān)鍵字集合很大時讹堤，關(guān)鍵字值不同的元素可能會映象到哈希表的同一地址上，即 k1≠k2 厨疙，但 H（k1）=H（k2）洲守，這種現(xiàn)象稱為沖突疑务，此時稱k1和k2為同義詞。實際中梗醇，沖突是不可避免的知允，只能通過改進哈希函數(shù)的性能來減少沖突。
綜上所述叙谨，哈希法主要包括以下兩方面的內(nèi)容：
1）如何構(gòu)造哈希函數(shù)
2）如何處理沖突温鸽。
哈希函數(shù)的構(gòu)造方法
常用五種方法：
（1）數(shù)字分析法；
（2）平方取中法
（3）分段疊加法
（4）除留余數(shù)法
（5）偽隨機數(shù)法
哈希表解決沖突的方法
主要有以下四種方法：
（1）開放定址法（也稱再散列法）
基本思想：當關(guān)鍵字key的哈希地址p=H（key）出現(xiàn)沖突時手负，以p為基礎(chǔ)涤垫，產(chǎn)生另一個哈希地址p1，如果p1仍然沖突竟终，再以p為基礎(chǔ)蝠猬，產(chǎn)生另一個哈希地址p2，…统捶，直到找出一個不沖突的哈希地址pi 榆芦，將相應(yīng)元素存入其中。
（2）再哈希法
基本思想：同時構(gòu)造多個不同的哈希函數(shù)喘鸟，當一個函數(shù)計算產(chǎn)生沖突時匆绣，再用另一個函數(shù)，直到?jīng)_突不再產(chǎn)生什黑。這種方法不易產(chǎn)生聚集崎淳，但增加了計算時間。
（3）鏈地址法
基本思想：將所有哈希地址為i的元素構(gòu)成一個稱為同義詞鏈的單鏈表兑凿，并將單鏈表的頭指針存在哈希表的第i個單元中凯力，因而查找、插入和刪除主要在同義詞鏈中進行礼华。鏈地址法適用于經(jīng)常進行插入和刪除的情況咐鹤。
（4）建立公共溢出區(qū)
基本思想：將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元素圣絮，一律填入溢出表祈惶。
