your site here
•解决冲突方法有多种，最常见的有“拉链 法”和“线性探测法”。下面主要讲解这 两种hash表的实现方法。
LOGO
哈希表(hash)
hash表的拉链法实现图示
•Key2与keyN冲突
your family site
your site here
Key1 Key2 Key3 . . . KeyN
hash表的拉链法实现pascal版
const
your family site
//注：本程序用数组模拟指针法编程
maxN = 1000000; maxM = 2000003; //大质数，通常 maxM > 2*maxN
type
Tnode =record x, c :longint; next :longint; end; //记录读入数据x和计数器c //用数组模拟指针，next是下一个元素下标
your family site
your site here
LOGO
哈希表(hash)
hash表的拉链法实现pascal版
begin
your family site
assign(input,'expa.in'); reset(input); assign(output,'expa.out'); rewrite(output); readln(n); for i:=1 to n do
your family site
your site here
•hash的思想是能直接找到需要的元素，因此必须 在元素的存储位置和它的关键字之间建立一确定 的对应关系f，使每个关键字和存储结构中一个( 几乎)唯一的存储位置相对应。
•注：虽然存储方式的多种，但NOIP的实践中，用 数组更简单实用,本讲义的hash表都是数组实现。
哈希表(hash)
hash表的线性探测法实现图示
•Key2与keyN冲突
your family site
your site here
Key1 Key2 Key3 . . . KeyN
0 1 2 . . . . . .
key2 keyN key1
向 后 找 到 空 位 插 入
key3 m>n
m
LOGO
LOGO
哈希表(hash)
Hash函数图示
•图示
your family site
单射关系f Key1 Key2 Key3 . . . Keyn
your site here
0 1 2 . . . . . .
m
m>n
LOGO
哈希表(hash)
hash表的概念
•Hash函数：上面的记录中关键字key和存 储位置(这里是数组下标)之间建立的对应 your family site 关系函数f(key)。称这个对应关系f为哈希 函数，按这个思想建立的表为哈希表（又 称为杂凑法或散列表）。
c
NOIP基础数据结构
哈希表、并查集概念与应用
LOGO
目录
目录
1
your family siteLeabharlann 哈希表---散列表 并查集
2
your site here
LOGO
哈希表(hash)
hash表的引入
•Hash表，也称散列表。一般应用于有大量 “动态”的插入(删除)和查找操作的一类 your family site 问题。
your family site
your site here
LOGO
哈希表(hash)
hash表的性探测法实现pascal版
begin
your family site
assign(input,'expa.in'); reset(input); assign(output,'expa.out'); rewrite(output); readln(n); for i:=1 to n do
your site here
LOGO
哈希表(hash)
hash表的关键问题
your family site
•Hash表冲突(collision)：通常的hash函 数不是一一对应关系。比如关键字是15位的身
份证号码时，普通情况下hash函数很可能会出现 keyi≠keyj，f(keyi)=f(keyj) 现象。也就是几 个关键字可能对应同一个“地址”。
your site here
LOGO
哈希表(hash)
hash表的性探测法实现pascal版
procedure add( i: longint); //新增加第i个节点 Var p:longint; begin
p:= find(data[i].x); //先查找是否已经有相同的元素 if hash[p]>0 then inc(data[hash[p]].c) //如果有，计数+1 else begin //如果没有，直接填入 hash[p]:=i; data[i].c:=1; end; write(data[ hash[p] ].c,' '); //打印data[i].x出现的次数 end;
your family site
your site here
LOGO
哈希表(hash)
常用Hash函数举例
•直接取余法： f(x):= x mod maxM ; maxM一般 是不太接近 2^t 的一个质数。
your family site
•乘法取整法： f(x):=trunc((x/maxX)*maxlongit) mod maxM， 主要用于实数。 •平方取中法：f(x):=(x*x div 1000 ) mod 1000000); 平方后取中间的，每位包含信息比较 多。
哈希表(hash)
hash表的性探测法实现pascal版
const
your family site
//注：线性探测法的hash表仅一个大数组
maxN = 1000000; maxM = 2000003; //大质数，通常 maxM > 2*maxN
type
Tnode =record x, c :longint; // next :longint; end; //记录读入数据x和计数器c //没有指针
your site here
LOGO
哈希表(hash)
hash表的拉链法实现pascal版
procedure add( i: longint); //新增加第i个节点 Var p, cod :longint; begin
p:= find(data[i].x); //先查找是否已经有相同的元素 if p>0 then inc(data[p].c) //如果有，计数+1 else begin //如果没有，则插入到表头 cod:= data[i].x mod maxM; data[i].next:=hash[cod]; hash[cod]:=i; data[i].c:=1; p:=i; end; write(data[ p ].c,' '); //打印data[i].x出现的次数 end;
your site here
LOGO
哈希表(hash)
hash表例1
分析：
your family site
由于0< N <1,000,000，不算很大，却是“动 态”的，用排序不太好。
但下面用更方便的hash法来实现，用以示 范hash表编程方法。
your site here
LOGO
哈希表(hash)
begin
your site here
read(data[i].x); add(i); //增加新节点 i ,并打印data[i].x出现次数 end; close(input); close(output);
end.
LOGO
空
your family site
your site here
LOGO
//查找元素x有没有出现在hash表中 function find(x: longint ):longint; var p,cod:longint;
your family site
begin
cod := x mod maxM; //hash函数 p:=hash[cod]; //hash值为cod的链表开头 while (p>0) and (data[p].x <> x ) do //在这个链表中查找x p:=data[p].next; exit (p); //返回找到的节点地址(下标) end;
your site here
•如果是“静态”的，通常可以先对数据排 序，查找时就可以用“二分查找”，时间 效率也很好了。 •虽然可以用“平衡树”之类方法，但实践 中，用hash表更简单实用。
LOGO
哈希表(hash)
hash表的引入
•普通的查找方法建立在“比较”的基础上，查找 的效率与比较次数密切相关。
your site here
var
data : array[1..maxN] of Tnode; //数据节点记录 hash : array[0..maxm] of longint; //hash表.可直接Tnode，无data N, i : longint ;
LOGO
哈希表(hash)
hash表的性探测法实现pascal版
your site here
var
data : array[1..maxN] of Tnode; //数据节点记录 hash : array[0..maxm] of longint; //hash表的链表头，开始为0 N,i : longint ;