什么是哈希表呢？

簡單說就是按照哈希函數關系建立的表 具體內容請參考數據結構相關知識~ 下面引用一些別的地方

1 基本原理 我們使用一個下標范圍比較大的數組來存儲元素。可以設計一個函數（哈希函數），使得每個元素的關鍵字都與一個函數值（即數組下標）相對應，于是用這個數組單元來存儲這個元素；也可以簡單的理解為，按照關鍵字為每一個元素"分類"，然后將這個元素存儲在相應"類"所對應的地方。 但是，不能夠保證每個元素的關鍵字與函數值是一一對應的，因此極有可能出現對于不同的元素，卻計算出了相同的函數值，這樣就產生了"沖突"，換句話說，就是把不同的元素分在了相同的"類"之中。后面我們將看到一種解決"沖突"的簡便做法。 總的來說，"直接定址"與"解決沖突"是哈希表的兩大特點。

2 函數構造 構造函數的常用方法（下面為了敘述簡潔，設 h(k) 表示關鍵字為 k 的元素所對應的函數值）： a) 除余法： 選擇一個適當的正整數 p ，令 h(k ) = k mod p 這里， p 如果選取的是比較大的素數，效果比較好。而且此法非常容易實現，因此是最常用的方法。 b) 數字選擇法： 如果關鍵字的位數比較多，超過長整型范圍而無法直接運算，可以選擇其中數字分布比較均勻的若干位，所組成的新的值作為關鍵字或者直接作為函數值。

3 沖突處理 線性重新散列技術易于實現且可以較好的達到目的。令數組元素個數為 S ，則當 h(k) 已經存儲了元素的時候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存儲單元為止（或者從頭到尾掃描一圈仍未發現空單元，這就是哈希表已經滿了，發生了錯誤。當然這是可以通過擴大數組范圍避免的）。

4 支持運算 哈希表支持的運算主要有：初始化(makenull)、哈希函數值的運算(h(x))、插入元素(insert)、查找元素(member)。 設插入的元素的關鍵字為 x ，A 為存儲的數組。 初始化比較容易，例如 const empty=maxlongint; // 用非常大的整數代表這個位置沒有存儲元素 p=9997; // 表的大小 procedure makenull; var i:integer; begin for i:=0 to p-1 do A[i]:=empty; End; 哈希函數值的運算根據函數的不同而變化，例如除余法的一個例子： function h(x:longint):Integer; begin h:= x mod p; end; 我們注意到，插入和查找首先都需要對這個元素定位，即如果這個元素若存在，它應該存儲在什么位置，因此加入一個定位的函數 locate function locate(x:longint):integer; var orig,i:integer; begin orig:=h(x); i:=0; while (i<S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty) do inc(i); //當這個循環停下來時，要么找到一個空的存儲單元，要么找到這個元 //素存儲的單元，要么表已經滿了 locate:=(orig+i) mod S; end; 插入元素 procedure insert(x:longint); var posi:integer; begin posi:=locate(x); //定位函數的返回值 if A[posi]=empty then A[posi]:=x else error; //error 即為發生了錯誤，當然這是可以避免的 end; 查找元素是否已經在表中 procedure member(x:longint):boolean; var posi:integer; begin posi:=locate(x); if A[posi]=x then member:=true else member:=false; end; 這些就是建立在哈希表上的常用基本運算。