哈希表原理简介.docx

引言
哈希表(Hash Table)的应用近两年才在 NOI 中消灭,作为一种高效的数据构造, 它正在竞赛中发挥着越来越重要的作用。
哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。设插入的元素的关键字为 x ,A 为存储的数组。初始化比较简洁,例如:
[cpp]view plaincopy
empty=maxlongint; // =9997; // 表的大小
makenull; i:integer;
i:=0 to p-1 do [i]:=empty; ;
哈希函数值的运算依据函数的不同而变化,例如除余法的一个例子: [cpp]view plaincopy
h(x:longint):Integer;
:= x mod p;
;
我们留意到,插入和查找首先都需要对这个元素定位,即假设这个元素假设存在, 它应当存储在什么位置,因此参加一个定位的函数 locate
[cpp]view plaincopy
locate(x:longint):integer; orig,i:integer;
:=h(x); :=0;
(i<S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty)
do
(i);
//当这个循环停下来时,要么找到一个空的存储单元,要么找到这个元
//素存储的单元,:=(orig+i) mod S; ;
插入元素
[cpp]view plaincopy insert(x:longint); posi:integer;

:=locate(x); // A[posi]=empty then A[posi]:=x
error; //error 即为发生了错误,;
查找元素是否已经在表中[cpp]view plaincopy
member(x:longint):boolean; posi:integer;
:=locate(x);
A[posi]=x then member:=true member:=false;
;
这些就是建立在哈希表上的常用根本运算。初步结论:
当数据规模接近哈希表上界或者下界的时候,哈希表完全不能够表达高效的特点,甚至还不如一般算法。但是假设规模在中心,它高效的特点可以充分表达。试验说明当元素布满哈希表的 90% 的时候,效率就已经开头明显下降。这就给了