1、按先后顺序存储在A[i]中，查找须要O（n），假设用二分查找，须要O（logn）

2、定义一个一维数组A[1..1353]。使得A[key]=key，这样，查找仅仅需O（1）就能够了，但空间开销比較大

思考：有什么办法使得查找时间快，占用空间小

哈希表基本原理

哈希表的基本原理是使用一个下标范围比較大的数组A来存储元素，设计一个函数h，对于要存储的线性表的每个元素node，取一个keywordkey，算出一个函数值h（key），把h（key）作为数组下标。用A[h(key)]这个数组单元来存储node。也能够简单理解为，依照keyword为每个元素“分类”。然后将这个元素存储在相应“类”所相应的地方。

哈希函数的构造

构造哈希函数有两个标准：简单和均匀

哈希函数的keyword通常是整数或者字符串

最经常使用的哈希函数：除余法。即h(key)=key mod m。

m为素数。能够使得较好保证分布均匀。

function hash(key:integer):integer;

begin

  exit(key mod m);

end;

冲突的处理——拉链法

採用分离链接技术构造哈希表，把哈希值同样的keyword串成链表。即哈希值为x的全部元素存储在以head[x]为表头的单链表中。

哈希表的基本操作

const

  maxn=10000;//哈希表容量

  limit=1007;//哈希函数的模

type

  node=record       //哈希表元素类型

    key,next:integer;

  end;

var

  head:array[1..limit] of integer;

  hash:array[1..maxn] of node;

  i,j,n,m,tot,key:integer;

元素插入

procedure insert(key:integer);

begin

  inc(tot);

  hash[tot].key:=key;

  hash[tot].next:=head[key mod limit];

  head[key mod limit]:=tot;

end;

元素查找

function find(key:integer):boolean;

var

  tmp:integer;

begin

  tmp:=head[key mod limit];

  while tmp<>-1 do

    begin

      if hash[tmp].key=key then exit(true);

      tmp:=hash[tmp].next;

    end;

  exit(false);

end;