哈希表(hashtable)冲突处理方法及常用基本运算

冲突处理  

线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ，则当 h(k) 已经存储了元素的时候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。

支持运算  

哈希表支持的运算主要有：初始化(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;  

这些就是建立在哈希表上的常用基本运算。