【正文】 碼簡(jiǎn)單的函數(shù)。 另一方 面，一味的追求低沖突率也不好。而素?cái)?shù)的約數(shù)是最少的，因此我們選用大素?cái)?shù)。也就是說余數(shù)的分布變得不均勻了。因此 ① 式的值就只有 b+1 種可能了。 簡(jiǎn)單的證明：假設(shè) p 是一個(gè)有較多約數(shù)的數(shù)，同時(shí)在數(shù)據(jù)中存在 q 滿足 gcd(p,q)=d 1 ，即有 p=a*d , q=b*d, 則有 q mod p= q p* [q div p] =q p*[b div a] . ① 其中 [b div a ] 的取值范圍是不會(huì)超過 [0， b] 的正整數(shù)。為什么呢？假設(shè) p=1000 ，則哈希函數(shù)分類的標(biāo)準(zhǔn)實(shí)際上就變成了按照末三位數(shù)分類，這樣最多 1000 類，沖突會(huì)很多。前 面提到，在使用 除余法 的時(shí)候， h(k)=k mod p ， p 最好是一個(gè)大素?cái)?shù)。 4. 應(yīng)用舉例 應(yīng)用的簡(jiǎn)單原則 什么時(shí)候適合應(yīng)用哈希表呢？如果發(fā)現(xiàn)解決這個(gè)問題時(shí)經(jīng)常要詢問： 某個(gè)元素是否在已知集合中？ ，也就是需要高效的數(shù)據(jù)存儲(chǔ)和查找，則使用哈希表是最好不過的了！那么，在應(yīng)用哈希表的過程中，值得注意的是什么呢？ 哈希函數(shù)的設(shè)計(jì)很重要。這就給了我們提示：如果確定使用哈希表，應(yīng)該盡量使數(shù)組開大（由于競(jìng)賽中可利用內(nèi)存越來越多，大數(shù)組通常不是問題，當(dāng)然也有少數(shù)情況例外），但對(duì)最太大的數(shù)組進(jìn)行操作也比較費(fèi)時(shí)間，需要找到一個(gè)平衡點(diǎn)。我們可以從圖像直觀的觀察到這一點(diǎn)。 初步結(jié)論： 當(dāng)數(shù)據(jù)規(guī)模接近哈希表上界或者下界的時(shí)候，哈希表完全不能夠體現(xiàn)高效的特點(diǎn)，甚至還不如一般算法。顯然浪費(fèi)這么多次運(yùn)算來解決沖突是不合算的，解決這個(gè)問題可以擴(kuò)大表的規(guī)模，或者使用 開散列 （盡管它是動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)）。這是因?yàn)闆_突的次數(shù)大大提高了，為了解決沖突，程序不得不遍歷一段都存儲(chǔ)了元素的數(shù)組空間來尋找空位 置。這是因?yàn)闆_突的次數(shù)較少。這一點(diǎn)在更復(fù)雜的哈希函數(shù)上會(huì)體現(xiàn)的更明顯，因?yàn)楦鼜?fù)雜的函數(shù)系數(shù)會(huì)更大。例如這道題的 H(x)=x mod 15589 ，通過與做同樣次數(shù)的加法相比較，測(cè)試發(fā)現(xiàn)系數(shù) 12 ，因?yàn)? mod 運(yùn)算本身 與快速排序的比較大小和交換元素運(yùn)算相比，比較費(fèi)時(shí)間。設(shè)哈希表的大小為 P . 首先，當(dāng)規(guī)模比較小的時(shí)候（大約為 a 10% * P，這個(gè)數(shù)據(jù)僅僅是通過若干數(shù)據(jù)估記出來的，沒有嚴(yán)格證明，下同），第二種方法比哈希表快。由于快速排序不穩(wěn)定，因此使用了隨機(jī)數(shù)據(jù)。當(dāng)然實(shí)際情況會(huì)比這個(gè)大，但是重復(fù)的幾率與哈希函數(shù)有關(guān)，不容易估計(jì) ) O(N log N+ N) = O(N log N) 測(cè)試數(shù)據(jù)規(guī)模 500 1000 2500 5000 7500 10000 13500 15000 對(duì)于數(shù)據(jù)的說明： 在 Celeron566 下用 TP 測(cè)試，為了使時(shí)間的差距明顯，讓程序重復(fù)運(yùn)了行 50 次。 我們假定 |A|=|B| ，對(duì)于隨機(jī)生成的數(shù)據(jù)，計(jì)算程序重復(fù)運(yùn)行 50 次所用時(shí)間。至于哈 希函數(shù)，只要按照除余法就行了，由于故意擴(kuò)大了原題的數(shù)據(jù)規(guī)模， H(x) = x mod 15889。） 分析： 我們先不管 A 與 B 的具體關(guān)系如何，注意到這個(gè)問題的本質(zhì)就是對(duì)于給定的集合 A ，確定 B 中的元素是否在 A 中。只需確定在 B 中但是不在 A 中的元素的個(gè)數(shù)即可。 3. 效率對(duì)比 簡(jiǎn)單的例子與實(shí)驗(yàn) 下面是一個(gè)比較簡(jiǎn)單的例子： 集合 ( Subset ) 問題描述： 給定兩個(gè)集合 A、 B，集合內(nèi)的任一元素 x 滿足 1 ≤ x ≤ ，并且每個(gè)集合的元素個(gè)數(shù)不大于 個(gè)。 end。 begin posi:=locate(x)。 查找元素是否已經(jīng)在表中 procedure member(x:longint):boolean。 //定位函數(shù)的返回值 if A[posi]=empty then A[posi]:=x else error。 var posi:integer。 end。 while (iS)and(A[(orig+i)mod S]x)and(A[(orig+i)mod S]empty) do inc(i)。 begin orig:=h(x)。 我們注意到，插入和查找首先都需要對(duì)這個(gè)元素定位，即如果這個(gè)元素若存在，它應(yīng)該存儲(chǔ)在什么位置，因此加入一個(gè)定位的函數(shù) locate function locate(x:longint):integer。 begin h:= x mod p。 End。 var i:integer。 // 用非常大的整數(shù)代表這個(gè)位置沒有存儲(chǔ)元素 p=9997。 設(shè)插入的元素的關(guān)鍵字為 x ， A 為存儲(chǔ)的數(shù)組。當(dāng)然這是可以通過擴(kuò)大數(shù)組范圍避免的）。 沖突處理 線性重新散列技術(shù)易于實(shí)現(xiàn)且可以較好的達(dá)到目的。而且此法非常容易實(shí)現(xiàn)，因此是最常用的方法。 總的來說， 直接定址 與 解決沖突 是哈希表的兩大 特點(diǎn)。 但是，不能夠保證每個(gè)元素的關(guān)鍵字與函數(shù)值是一一對(duì)應(yīng)的，因此極有可能出現(xiàn)對(duì)于不同的元素，卻計(jì)算出了相同的函數(shù)值，這樣就產(chǎn)生了 沖突 ，換句話說，就是把不同的元素分在了相同的 類 之中。 2. 基礎(chǔ)操作 基本原理 我們使用一個(gè)下標(biāo)范圍比較大的數(shù)組來存儲(chǔ)元素。 哈希表又叫做散列表，分為 開散列 和 閉散列 。然而在當(dāng)前可利用內(nèi)存越來越多的情況下，用空間換時(shí)間的做法是值得的。 [正文 ] 1. 引言 哈希表（ Hash Table）的應(yīng)用近兩年才在 NOI 中出現(xiàn)，作為一種高效的數(shù)據(jù)結(jié)構(gòu)，它正在競(jìng)賽中發(fā)揮著越來越 重要的作用。淺談競(jìng)賽中哈希表的應(yīng)用（一） 哈爾濱市第三中學(xué) 劉翀 [關(guān)鍵詞 ] 應(yīng)用 哈希表 數(shù)據(jù)結(jié)構(gòu) [摘要 ] 哈希表是一種高效的數(shù)據(jù)結(jié)構(gòu)。本文分五個(gè)部分：首先提出了哈希表的優(yōu)點(diǎn)，其次介紹了它的基礎(chǔ)操作，接著從簡(jiǎn)單的例子中作了效率對(duì)比，指出其適用范圍以及特點(diǎn)，然后通過例子說明了如何在題目中運(yùn)用哈希表以及需要注意的問題，最后總結(jié)全文。 哈希表最大的優(yōu)點(diǎn)，就是把數(shù)據(jù)的存儲(chǔ)和查找消耗的時(shí)間大大降低，幾乎可以看成是常數(shù)時(shí)間；而代價(jià)僅僅是消耗比較多的內(nèi)存。另外，編碼比較容易也是它的特點(diǎn)之一。考慮到競(jìng)賽時(shí)多數(shù)人通常避免使用動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)，本文中的 哈希表 僅指 閉散列 ，關(guān)于其他方面讀者可參閱其他書籍?？梢栽O(shè)計(jì)一個(gè) 函數(shù)（哈希函數(shù)， 也叫做散列函數(shù)），使得每個(gè)元素的關(guān)鍵字都與一個(gè)函數(shù)值（即數(shù)組下標(biāo)）相對(duì)應(yīng)，于是用這個(gè)數(shù)組單元來存儲(chǔ)這個(gè)元素；也可以簡(jiǎn)單的理解為，按照關(guān)鍵字為每一個(gè)元素 分類 ，然后將這個(gè)元素存儲(chǔ)在相應(yīng) 類 所對(duì)應(yīng)的地方。后面我們將看到一種解決 沖突 的簡(jiǎn)便做法。 函數(shù)構(gòu)造 構(gòu)造函數(shù)的常用方法（下面為了敘述簡(jiǎn)潔，設(shè) h(k) 表示關(guān)鍵字為 k 的元素所對(duì)應(yīng)的函數(shù)值）： a) 除余法： 選擇一個(gè)適當(dāng)?shù)恼麛?shù) p ，令 h(k ) = k mod p 這里， p 如果選取的是比較大的素?cái)?shù)，效果比較好。 b) 數(shù)字選擇法： 如果關(guān)鍵字的位數(shù)比較多，超過長整型范圍而無法直接運(yùn)算，可以選擇其中數(shù)字分布比較均勻的若干位，所組成的新的值作為關(guān)鍵字或者直接作為函數(shù)值。令數(shù)組元素個(gè)數(shù)為 S ，則當(dāng) h(k) 已經(jīng)存儲(chǔ)了元素的時(shí)候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存儲(chǔ)單元為止（或者從頭到尾掃描一圈仍未發(fā)現(xiàn)空單元，這就是哈希表已經(jīng)滿了，發(fā)生了錯(cuò)誤。 支持運(yùn)算 哈希表支持的運(yùn)算主要有：初始化 (makenull)、哈希函數(shù)值的運(yùn)算 (h(x))、插入元素 (insert)、查找元素 (member)。 初始化比較容易，例如 const empty=maxlongint。 // 表的大小 procedure makenull。 begin for i:=0 to p1 do A[i]:=empty。 哈希函數(shù)值的運(yùn)算根據(jù)函數(shù)的不同而變化，例如除余法的一個(gè)例子： function h(x:longint):Integer。 end。 var orig,i:integer。 i:=0。 //當(dāng)這個(gè)循環(huán)停下來時(shí)，要么找到一個(gè)空的存儲(chǔ)單元，要么找到這個(gè)元 //素存儲(chǔ)的單元，要么表已經(jīng)滿了 locate:=(orig+i) mod S。 插入元素 procedure insert(x:longint)。 begin posi:=locate(x)。 //error 即為發(fā)生了錯(cuò)誤，當(dāng)然這是可以避免的 end。 var posi:integer。 if A[posi]=x then member:=true else member:=false。 這些就是建立在哈希表上的常用基本運(yùn)算。我們希望求出 A、 B 之間的關(guān)系。（這個(gè)題目是根據(jù) OIBH NOIP 2020 模擬賽 1 的第一題改編的。所以，我們使用哈希表來處理。 當(dāng)然本題可以利用別的方法解決，所以選取了速度最快的快速排序 +二分查找，讓這兩種方法作效率對(duì)比。 對(duì)比表格如下： 哈希表（ sec） 快速排序 +二分查找 (sec) 復(fù)雜度 O(N) (只有忽略了沖突才是這個(gè)結(jié)果。同時(shí)哈希表中的 P= 15889 ，下標(biāo)范圍 0..15888 。 3． 2 對(duì)試驗(yàn)結(jié)果的分析： 注意到兩個(gè)程序的用時(shí)并不像我們期望的那樣，總是哈希表快。這是由于，雖然每次計(jì)算哈希函數(shù)用 O(1) 的時(shí)間，但是這個(gè)系數(shù)比較大。所以規(guī)模小的時(shí)候， O(N)（忽略沖突）的算法反而不如 O(NlogN)。 其次，當(dāng)規(guī)模稍大 （大約為 15%*P a 85%*P） 的時(shí)候，很明顯哈希表的效率高。 再次，當(dāng)規(guī)模再大 （大約為 90%*P a P ）的時(shí)候，哈希表的效率大幅下降。用白箱測(cè)試的方法統(tǒng)計(jì)，當(dāng)規(guī)模為 13500 的時(shí)候，為了找空位置，線性重新散列平均做了 150000 次運(yùn)算；而當(dāng)規(guī)模為 15000 的時(shí)候，平均竟然高達(dá)2020000 次運(yùn)算，某些數(shù)據(jù)甚至能達(dá)到 4265833 次。然而需要指出的是，沖突是不可避免的。但是如果規(guī)模在中央，它高效的特點(diǎn)可 以充分體現(xiàn)。 試驗(yàn)表明當(dāng)元素充滿哈希表的 90% 的時(shí)候，效率就已經(jīng)開始明顯下降。 通常使它的容量至少是題目最大需求的 120% ，效果比較好（這個(gè)僅僅是經(jīng)驗(yàn)，沒有嚴(yán)格證明）。一個(gè)不好的哈希函數(shù)，就是指造成很多沖突的情況，從前面的例子已經(jīng)可以看出來，解決沖突會(huì)浪費(fèi)掉大量時(shí)間，因此我們的目標(biāo)就是盡力避免沖突。這就是為了盡力避免沖突。一般地說，如果 p 的約數(shù)越多，那么沖突的幾率就越大。也就是說， [b div a] 的值只有 b+1 種可能，而 p 是一個(gè)預(yù)先確定的數(shù)。這樣，雖然 mod 運(yùn)算之后的余數(shù)仍然在 [0， p1] 內(nèi)，但是它的取值僅限于 ① 可能取到的那些值。容易看出， p 的約數(shù)越多，