https://blog.csdn.net/xtzmm1215/article/details/47177701
https://blog.csdn.net/afterlife_qiye/article/details/47976917
首先在元素的關(guān)鍵字k和元素的存儲(chǔ)位置p之間建立一個(gè)對(duì)應(yīng)關(guān)系f厨喂，使得p=f(k)，f稱為哈希函數(shù)嗜诀。創(chuàng)建哈希表時(shí)，把關(guān)鍵字為k的元素直接存入地址為f(k)的單元；以后當(dāng)查找關(guān)鍵字為k的元素時(shí)筛婉，再利用哈希函數(shù)計(jì)算出該元素的存儲(chǔ)位置p=f(k)判沟，從而達(dá)到按關(guān)鍵字直接存取元素的目的在孝。
沖突：當(dāng)關(guān)鍵字集合很大時(shí)唾糯，關(guān)鍵字值不同的元素可能會(huì)映象到哈希表的同一地址上怠硼，即 k1≠k2 ，但 H（k1）=H（k2）趾断，這種現(xiàn)象稱為沖突拒名，此時(shí)稱k1和k2為同義詞。
哈希法主要包括以下兩方面的內(nèi)容：
1）如何構(gòu)造哈希函數(shù)
2）如何處理沖突芋酌。
本文介紹解決沖突的辦法
開放定址法
這種方法也稱再散列法，其基本思想是：當(dāng)關(guān)鍵字key的哈希地址p=H（key）出現(xiàn)沖突時(shí)雁佳，以p為基礎(chǔ)脐帝，產(chǎn)生另一個(gè)哈希地址p1，如果p1仍然沖突糖权，再以p為基礎(chǔ)堵腹，產(chǎn)生另一個(gè)哈希地址p2，…星澳，直到找出一個(gè)不沖突的哈希地址pi 疚顷，將相應(yīng)元素存入其中。這種方法有一個(gè)通用的再散列函數(shù)形式：
Hi=（H（key）+di）% m i=1，2腿堤，…阀坏，n
其中H（key）為哈希函數(shù)，m 為表長笆檀，di稱為增量序列忌堂。增量序列的取值方式不同，相應(yīng)的再散列方式也不同酗洒。
主要有以下三種：
線性探測(cè)再散列
dii=1士修，2，3樱衷，…棋嘲，m-1
這種方法的特點(diǎn)是：沖突發(fā)生時(shí)，順序查看表中下一單元矩桂，直到找出一個(gè)空單元或查遍全表封字。
二次探測(cè)再散列
di=12，-12耍鬓，22阔籽，-22，…牲蜀，k2笆制，-k2 ( k<=m/2 )
這種方法的特點(diǎn)是：沖突發(fā)生時(shí)，在表的左右進(jìn)行跳躍式探測(cè)涣达，比較靈活在辆。
偽隨機(jī)探測(cè)再散列
di=偽隨機(jī)數(shù)序列。
具體實(shí)現(xiàn)時(shí)度苔，應(yīng)建立一個(gè)偽隨機(jī)數(shù)發(fā)生器匆篓，（如i=(i+p) % m），并給定一個(gè)隨機(jī)數(shù)做起點(diǎn)寇窑。
從上述例子可以看出鸦概，線性探測(cè)再散列容易產(chǎn)生“二次聚集”，即在處理同義詞的沖突時(shí)又導(dǎo)致非同義詞的沖突甩骏。例如窗市，當(dāng)表中i, i+1 ,i+2三個(gè)單元已滿時(shí)，下一個(gè)哈希地址為i, 或i+1 ,或i+2饮笛，或i+3的元素咨察，都將填入i+3這同一個(gè)單元，而這四個(gè)元素并非同義詞福青。線性探測(cè)再散列的優(yōu)點(diǎn)是：只要哈希表不滿摄狱，就一定能找到一個(gè)不沖突的哈希地址脓诡，而二次探測(cè)再散列和偽隨機(jī)探測(cè)再散列則不一定。
鏈地址法
拉鏈法解決沖突的做法是：將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接在同一個(gè)單鏈表中媒役。若選定的散列表長度為m祝谚，則可將散列表定義為一個(gè)由m個(gè)頭指針組成的指針數(shù) 組T[0..m-1]。凡是散列地址為i的結(jié)點(diǎn)刊愚，均插入到以T[i]為頭指針的單鏈表中踊跟。T中各分量的初值均應(yīng)為空指針。
特點(diǎn)
- 拉鏈法處理沖突簡(jiǎn)單鸥诽，且無堆積現(xiàn)象商玫，即非同義詞決不會(huì)發(fā)生沖突，因此平均查找長度較短牡借；
- 由于拉鏈法中各鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的拳昌，故它更適合于造表前無法確定表長的情況；
再哈希法
這種方法是同時(shí)構(gòu)造多個(gè)不同的哈希函數(shù)：
Hi=RH1（key） i=1钠龙，2炬藤，…，k
當(dāng)哈希地址Hi=RH1（key）發(fā)生沖突時(shí)碴里，再計(jì)算Hi=RH2（key）……沈矿，直到?jīng)_突不再產(chǎn)生。這種方法不易產(chǎn)生聚集咬腋，但增加了計(jì)算時(shí)間羹膳。
建立一個(gè)公共溢出區(qū)
這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元素根竿，一律填入溢出表
