当前位置：文档之家 › 数据结构.第9章.查找.4.哈希表

数据结构.第9章.查找.4.哈希表

  • 格式：pptx
  • 大小：2.29 MB
  • 文档页数：63

下载文档原格式

  / 63

合集下载

第章查找A

第章查找A
• 折半查找在查找成功时关键字比较次数 不超过树的深度,即: log2n + 1
假设 n=2h-1 并且查找概率相等
则
ASLbs

1 n
n i1
Ci

1 n

h j1
j

2
j1



n
n
1
log
2
(n

1)

1
在n>50时，可得近似结果
ASLbs log2(n 1) 1
若此关键字能识别若干记录，则称
之谓“次关键字”。
查找（搜索 、 Search)
所谓查找，就是在数据集合中寻找满足某种条 件的数据对象。
查找的结果通常有两种可能： 查找成功，即找到满足条件的数据对象。这 时，作为结果，可报告该对象在结构中的位置， 还可进一步给出该对象中的具体信息。 查找不成功，或搜索失败。作为结果，也应 报告一些信息，如失败标志、失败位置等。
• 分块有序原则：第二个子表的所有记录的关键字均 大于第一个字表中的最大关键字，……，依此类推。
索引顺序表的查找过程：
1）由索引确定记录所在块（子表）； 2）在顺序表的某个块内进行顺序查找。
可见， 索引顺序查找的过程也是一个
“缩小区间”的查找过程。
注意：索引可以根据查找表的特点来构造。
因为索引表中的 索引项是按关键字有 序排列的，因此可用顺序查找，也可用 折半查找；而块（子表）中的记录是任 意排列的，只能用顺序查找的方法。
for (i=ST.length; ST.elem[i].key!=key; --i);
// 从后往前找
return i ;

数据结构教案第9章 查找

数据结构教案第9章 查找

●性能分析 定义：为了确定记录在查找表中的位置，需和给定值进行比 较的关键字个数的期望值称为查找算法在查找成功时的平均查找 长度。
ASL = ∑ Pi C i
i =1
n
其中：Pi为查找表中第i个记录的概率；Ci为找到第i个记 录的比较次数； 查找成功的平均查找长度：
1 n n +1 ASL = ∑ (n − i + 1) = 2 n i =1
索引表 最大关键字 起始地址
22 48 86 1 7 13
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53
9．2动态查找表 特点：表结构本身是在查找过程中动态生 成的，即对于给定值key，若表中存在其关键 字等于key的记录，则查找成功返回；否则插 入关键字等于key的记录。
10 10 9 15 9 17 17 15
a
16
作业：(P55)9.9, 9. 33
9．3哈希表 9．3．1什么是哈希表 哈希函数：在记录的关键字和它的存储位置之间建立 一个确定的对应关系f，使每个关键字和结构中一个 唯一的存储位置相对应，称对应关系f为哈希(Hash) 函数。 哈希表：按哈希函数建立的表称为哈希表。
void Delete(BiTree &p){ if(!p->rchild) { q=p; p=p->lchild; free(q); } else if(!p->lchild) { q=p; p=p->rchild; free(q); } else{ q=p; s=p->lchild; while(s->rchild) {q=s; s=s->rchild;} p->data=s->data; if(q!=p) q->rchild=s->lchild; \*q！=p正常情况 else q->lchile= s->lchild; \* q=p意外者，p的左子树的根没有右子树 free(s); }\\else }

数据结构_查找原理及典型的查找算法

数据结构_查找原理及典型的查找算法
无法实现！因全部元素的定位只能从头指针head开 始，是一种非随机存取结构。
3.对非线性(树)结构如何进行折半查找？ 可借助二叉排序树来查找（属动态查找表形式）。
9.1.2 有序表的查找
折半查找过程可以描述为一棵二叉树
折半查找的判定树 如：（a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11）
总之：
二叉排序树既有类似于折半查找的特性，又采用了链 表存储，它是动态查找表的一种适宜表示。
一、二叉排序树
（3）构造过程: 例：输入序列{45，12，37，3，53，100，24}
45
12
53
3
37
100
24
一、二叉排序树
（2）非递归查找过程 BiTree SearchBST(BiTree T,KeyType key){
CH9 查找
查找的基本概念 9.1 静态查找表
9.1.1 顺序查找 9.1.2 有序表的查找 9.1.3 索引顺序表的查找
9.2 动态查找表
9.2.1 二叉排序树和平衡二叉树 9.2.2 B－和B＋树
9.3 哈希表
查找的基本概念
1.查找表 2.查找
关键字 主关键字 次关键字
}
9.2.1 二叉排序树和平衡二叉树
一、二叉排序树 二、平衡二叉树
一、二叉排序树
1.定义、特点、构造过程
（1）定义 二叉排序树或者是一棵空树，或是具有下列性质的二叉树：
若左子树非空，则左子树上所有结点的值均小于它的 根结点的值。
若右子树非空，则右子树上所有结点的值均大于它的 根结点的值。
有序/无序表 有序表
顺序/链式存 储
顺序存储
分块查找 介于二者之间 表中元素逐段有序 顺序/链式存储

大学数据结构课件--第9章 查找

大学数据结构课件--第9章 查找
——这种既查找又插入的过程称为动态查找。
二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态 查找表的一种适宜表示。
注：若数据元素的输入顺序不同，则得到的二叉排序树形态 也不同！
17
二、二叉树的插入和删除操作
1、二叉排序树的插入和查找操作
例：输入待查找的关键字序列=（45，24，53，12，90）
折半查找举例：
已知如下11个元素的有序表：
（05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21和85的数据元素。
Low指向待查元 素所在区间的下 界
mid指向待查元素所在 high指向待查元素所
区间的中间位置
在区间的上界
8
9.1.2 折半查找（又称二分查找或对分查找）
balance。这样，可以得到AVL树的其它性质：
❖ 任一结点的平衡因子只能取：-1、0 或 1；如果树中任 意一个结点的平衡因子的绝对值大于1，则这棵二叉树 就失去平衡，不再是AVL树；
24
三、平衡二叉树
例：判断下列二叉树是否AVL树？
-1
1
-1
0
0
1
0
(a) 平衡树
2
-1
0
0
1
0
(b) 不是平衡树
（1）p为叶子结点，只需修改p双亲f的指针f->lchild=NULL或 f->rchild=NULL
（2）P只有左子树或右子树 ❖ P只有左子树，用P的左孩子代替P ❖ P只有右子树，用P的右孩子代替P
（3）P左、右子树均非空 （P左子树的根C的右子树分支找到S，S的右子树为空） ❖ P的左子树成为双亲f的左子树，P的右子树成为S的右子树 ❖ S的左子树成为S的双亲Q的右子树，用S取代p； 若C无右子树，用C取代p

数据结构第9章作业 查找答案

数据结构第9章作业 查找答案

第9章 查找答案一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。

2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 9 次。

设有100个结点，用二分法查找时，最大比较次数是 7 。

3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。

解：显然，平均查找长度＝O （log 2n ）<5次（25）。

但具体是多少次，则不应当按照公式)1(log 12++=n nn ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。

因为这是在假设n ＝2m-1的情况下推导出来的公式。

应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。

5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。

6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。

7. 有一个表长为m 的散列表，初始状态为空，现将n （n<m ）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。

如果这n 个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。

(而任一元素查找次数 ≤n-1)二、单项选择题（ B ）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;Ｃ. ＡＳＬ＝n ＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１（ A ）2. 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。

数据结构考研试题精选及答案第9章 查找答案

数据结构考研试题精选及答案第9章 查找答案

第9章集合部分答案解释如下。

4．不能说哪种哈希函数的选取方法最好，各种选取方法有自己的适用范围。

8．哈希表的结点中可以包括指针，指向其元素。

11．单链表不能使用折半查找方法。

20．按插入后中序遍历是递增序列的原则，若某结点只有右子树，而插入元素的关键字小于该结点的关键字，则会插入到该结点的左侧，成为其左孩子。

这种插入就不是插入到叶子下面。

21．从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。

但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。

故不能说完全二叉树是平衡二叉树。

23．某结点的左子树根结点不一定是它的中序前驱，其右子树根结点也不一定是它的中序后继。

24．在等概率下，查找成功时的平均查找长度相同，查找失败时的平均查找长度不相同。

26．只有被删除结点是叶子结点时命题才正确。

三．填空题1．n n+1 2．4 3．6,9,11,12 4．55．26（第4层是叶子结点，每个结点两个关键字） 6．1,3,6,8,11,13,16,19 7．5,96 8．m-1,「m/2⎤-1 9．2,4,310．(1)哈希函数(2)解决冲突的方法 (3)选择好的哈希函数 (4)处理冲突的方法 (5)均匀(6)简单11．AVL树（高度平衡树，高度平衡的二叉排序树），或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1。

12．小于等于表长的最大素数或不包含小于20的质因子的合数 13．16 14．⎣㏒n」+1215．(1)45 (2)45 (3)46（块内顺序查找） 16．k(k+1)/2 17．30，31.5（块内顺序查找）18．(1)顺序存储或链式存储 (2)顺序存储且有序 (3)块内顺序存储，块间有序 (4) 散列存储19．(n+1)/2 20．(n+1)/n*log2(n+1)-1 21．结点的左子树的高度减去结点的右子树的高度22．(1)顺序表(2)树表(3)哈希表(4)开放定址方法(5)链地址方法(6)再哈希(7)建立公共溢出区23．直接定址法 24．log⎡m/2⎤(21n+)+1 25．O(N) 26．n(n+1)/227．54 28．31 29．37/12 30．主关键字 31．左子树右子树32．插入删除 33．14 34．(1)126 (2)64 (3)33 (4)65 35．（1）low<=high (2) (low+hig) DIV 2 (3) binsrch:=mid (4)binsrch:=0 36．(1) k (2) I<n+1 37．(1)rear=mid-1 (2)head=mid+1 (3)head>rear 38．(1)p!=null (2)pf=p (3)p!=*t (4)*t=null四．应用题1．概念是基本知识的主要部分，要牢固掌握。

(完整word版)数据结构第九章查找

第九章查找：习题习题一、选择题1．散列表查找中k个关键字具有同一散列值，若用线性探测法将这k个关键字对应的记录存入散列表中，至少要进行( )次探测。

A. k B。

k+l C. k(k+l）／2 D. l+k （k+l)/22．下述命题( )是不成立的。

A。

m阶B-树中的每一个结点的子树个数都小于或等于mB。

m阶B-树中的每一个结点的子树个数都大于或等于『m/2-1C。

m阶B-树中的每一个结点的子树高度都相等D。

m阶B—树具有k个子树的非叶子结点含有(k-l）个关键字3．如果要求一个基本线性表既能较快地查找，又能适应动态变化的要求，可以采用( ）查找方法.A。

分块 B. 顺序 C. 二分 D.散列4．设有100个元素，用折半查找法进行查找时，最大比较次数是( ),最小比较次数是( ）.A。

7，1 B.6，l C.5，1 D. 8，15．散列表长m=15，散列表函数H(key）=key％13。

表中已有4个结点：addr（18)=5；addr(32）=6; addr(59)=7；addr(73)=8;其余地址为空，如果用二次探测再散列处理冲突，关键字为109的结点的地址是( )。

A. 8 B。

3 C. 5 D。

46．用分块查找时，若线性表中共有729个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分( )个结点最佳。

A。

15 B. 27 C。

25 D。

307．散列函数有一个共同性质，即函数值应当以( )取其值域的每个值。

A.同等概率B。

最大概率C。

最小概率D。

平均概率8．设散列地址空间为O.。

m—1，k为关键字，假定散列函数为h(k)=k％p，为了减少冲突，一般应取p为( )。

A.小于m的最大奇数B. 小于m的最大素数C.小于m的最大偶数D.小于m的最大合数9．当向一棵m阶的B-树做插入操作时，若使一个结点中的关键字个数等于( )，则必须分裂成两个结点。

A。

m B。

m-l C.m+l D。

数据结构的查找算法

数据结构的查找算法在计算机科学中，数据结构是用于组织和存储数据的一种方式。

查找算法是数据结构中的重要部分，它用于在数据集合中搜索特定元素或信息。

本文将介绍几种常见的数据结构查找算法，包括线性查找、二分查找、哈希查找以及树结构的查找算法。

1. 线性查找线性查找是一种简单直观的查找方法，适用于无序的数据集合。

其基本思想是从数据集合的第一个元素开始逐个比较，直到找到目标元素或者遍历完整个数据集合。

由于线性查找需要遍历所有元素，所以时间复杂度为O(n)，其中n为数据集合的大小。

2. 二分查找二分查找是一种高效的查找算法，但它要求数据集合中的元素必须有序。

具体实现方式是将数据集合分为两半，然后与目标元素进行比较，不断缩小查找范围，直到找到目标元素或者确定目标元素不存在。

由于每次都将查找范围减小一半，所以时间复杂度为O(log n)，其中n为数据集合的大小。

3. 哈希查找哈希查找利用哈希函数将目标元素映射到哈希表中的特定位置，从而快速定位目标元素。

哈希表是一种以键-值对形式存储数据的数据结构，可以快速插入和删除元素，因此在查找时具有良好的性能。

哈希查找的时间复杂度为O(1)，但在处理哈希冲突时可能会影响性能。

4. 树结构的查找算法树是一种常见的数据结构，其查找算法主要包括二叉搜索树、平衡二叉搜索树以及B树和B+树。

二叉搜索树是一种有序的二叉树，左子树的所有节点值都小于根节点，右子树的所有节点值都大于根节点。

通过比较目标元素与节点的值，可以快速定位目标元素。

平衡二叉搜索树是为了解决二叉搜索树在某些情况下可能出现的退化情况，通过旋转操作保持树的平衡性。

B树和B+树是一种多路搜索树，它们可以减少磁盘I/O操作，适用于大规模数据的查找。

综上所述，数据结构的查找算法是计算机科学中的重要内容。

不同的查找算法适用于不同的场景，选择合适的算法可以提高查找效率。

在实际应用中，需要根据数据集合的特点及查找需求来选择合适的算法。

数据结构第九章--查找-习题及答案

第九章查找一、选择题1。

若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。

A． (n—1)/2 B. n/2 C。

（n+1）/2 D。

n2. 下面关于二分查找的叙述正确的是（ )A。

表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列B。

表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储3. 用二分(对半）查找表的元素的速度比用顺序法（ )A．必然快 B. 必然慢 C. 相等 D. 不能确定4. 具有12个关键字的有序表，折半查找的平均查找长度( ）A. 3。

1 B。

4 C. 2。

5 D. 55．当采用分块查找时,数据的组织方式为 ( ）A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序,但块间必须有序，每块内最大(或最小）的数据组成索引块C。

数据分成若干块，每块内数据有序，每块内最大(或最小）的数据组成索引块D. 数据分成若干块,每块（除最后一块外)中数据个数需相同6。

二叉查找树的查找效率与二叉树的( （1）)有关, 在（（2）)时其查找效率最低（1）: A。

高度 B。

结点的多少 C. 树型 D. 结点的位置(2）: A。

结点太多 B. 完全二叉树 C。

呈单枝树 D. 结点太复杂。

7. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败，它们的平均查找长度是((1）） ,对于查找成功，他们的平均查找长度是（（2））供选择的答案：A。

相同的 B。

不同的9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）A．(100,80， 90， 60， 120，110，130） B。

（100，120，110,130，80， 60, 90) C。

（100，60, 80， 90, 120，110，130） D。

查找-数据结构


平均查找长度：为确定记录在查找表中 的位置，需和给定值进行比较的关键字 个数的期望值称为查找算法在查找成功 时的平均查找长度，简称ASL。
对于含有n个记录的表，查找成功时的平 均查找长度为： n ASL PiCi i 1
其找到中表：中Pi为其查关找键表字中与第给i定个值记相录等的的概第率，i个C记i为 录时和给定值已进行过比较的关键字个数。
（1）若*p 为叶子结点，直接删除即可。
45
45
12
3
37
53
f
100
24
p
61
60
90
12
53
3
删除24
f->lchild = null; delete p;
37
100
61
60
90
78
78
（2）若*p结点只有左子树PL或只有右子树PR,此 时只要令PL或PR直接成为*f的左子树即可
f
F
f
F
p
P
p
二叉排序树的插入
基本思想：
若二叉排序树为空，则待插结点作为根结点插入 到空树中；
若待插结点的关键字值和根结点的关键字值相等， 则说明树中已有此结点，无需插入；
若待插结点的关键字值小于根结点的关键字值， 则将待插结点插入到根的左子树中；
若待插结点的关键字值大于根结点的关键字值， 则将待插结点插入到根的右子树中；
mid low
mid low
mid low
mid low
mid
mid
mid
mid
6
3
9
1
47
10
2
58
11
由此可见，二分查找过程恰好是走了一条从判 定树的根到被查结点的路径，比较的关键字个 数恰为该结点在判定树中的层数。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

§9.3 哈希表
开放地址法
例：关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11； 拟用线性探测法处理冲突。建哈希表： 0 1
11 22
2
3
4
5
6
3
7
7
8
29
9
8
10
47 92 16
§9.3 哈希表
开放地址法
选用关键字的某几位组合成哈希地址。
选用原则应当是：各种符号在该位上出现的频率大致
相同。
适于关键字位数比哈希地址位数大，且可能出现的关 键字事先知道的情况。
§9.3 哈希表
数字分析法
例：有一组（例如80个）关键码，其样式如下： 讨论： 3 4 7 0 5 2 4 ① 第1、2位均是“3和4”，第3位也只有 3 4 9 1 4 8 7 3 4 8 2 6 9 6 “ 7、8、9”，因此，这几位不能用，余 3 4 8 5 2 7 0 下四位分布较均匀，可作为哈希地址选用。 3 4 8 6 3 0 5 ② 若哈希地址取两位（因元素仅80个）， 3 4 9 8 0 5 8 则可取这四位中的任意两位组合成哈希地 3 4 7 9 6 7 1 址，也可以取其中两位与其它两位叠加求 3 4 7 3 9 1 9 和后，取低两位作哈希地址。 位号：① ② ③ ④ ⑤ ⑥ ⑦
拟用二次探测法处理冲突。建哈希表如下： Hi = ( H(K)+di ) mod m 其中di =12, -12, 22,-22,…, j2, -j2 ( j≤m/2)。
0 1
11 22
2
3
3
4
5
6
7
7
8
29
9 10
8
47 92 16
§9.3 哈希表
开放地址法
(3) 伪随机探测法
伪随机探测法对应的探查地址序列的计算公式为： Hi = ( H(K)+di ) mod m
实际的应用中，要存储的关键字集合K，相对
U来说很小，因此分配给T的大部分空间会被浪费。
§9.3 哈希表
哈希表(Hash Tables)
给定关键字，期望通过计算，即利用哈希函数
h(x)计算出关键字在表T中的位置。
§9.3 哈希表
哈希表(Hash Tables)
在直接寻址方式下，具有关 键字k的数据元素，存放在槽k中。
访问到数组的任意元素。
§9.3 哈希表
哈希表(Hash Tables)
当关键字全域比较小的时候，利用数组(直接
寻址表)是一种简单有效的技术。
§9.3 哈希表
哈希表(Hash Tables)
直接寻址技术存在的问题：
如果全域U很大，在计算机中存储大小为|U|的
一张表T就有点不实际，甚至是不可能的。
频度很高的现象。
§9.3 哈希表
折叠法
构造：将关键字分割成位数相同的几部分，然后取这几部分 的叠加和（舍去进位）做哈希地址。 移位叠加：将分割后的几部分低位对齐相加。 间界叠加：从一端沿分割界来回折叠，然后对齐相加。
适于关键字位数很多，且每一位上数字分布大致均匀情况
§9.3 哈希表
折叠法
例：关键字为：0442205864，哈希地址位数为 4。 5864 4220 04 移位叠加 10088 H(key)=0088 例：元素42751896, 移位法： 427＋518＋96=1041 5864 0224 04 间界叠加 6092 H(key)=6092
线性探测法的优点：只要哈希表未被填满，保证能找到一 个空地址单元存放有冲突的元素；
线性探测法的缺点：可能使第i个哈希地址的同义词存入第
i+1个哈希地址，这样本应存入第i+1个哈希地址的元素 变成了第i+2个哈希地址的同义词，……， 因此，可能出现很多元素在相邻的哈希地址上“堆积”起 来，大大降低了查找效率。 可采用二次探测法或伪随机探测法，以改善“堆积”问题
§9.3 哈希表
链地址法
基本思想： 将具有相同哈希地址的记录链成一个单链表，m个哈希 地址就设m个单链表，然后用一个数组将m个单链表的表头 指针存储起来，形成一个动态的结构。 优点：插入、删除方便。 缺点：占用存储空间多。
例：已知一组关键字 (19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79) 哈希函数为：H(key)=key MOD 13，用链地址法处理冲突。
100
2
3
300
4
5
500
6
7
8

9
700 800 900
§9.3 哈希表
直接定址法
特点：地址集合的大小 = 关键字集合的大小。 优点：以关键码 key 的某个线性函数值为哈希地址，
不会产生冲突。
缺点：要占用连续地址空间，空间效率低。
实际中能使用这种哈希函数的情况很少
§9.3 哈希表
数字分析法
武汉科技大学
Wuhan University of Science and Technology
张 凯 计算机学院 软件工程系
2011年3月12日
第9章
查找
查找的基本概念
静态查找表
动态查找表 哈希表
§9.3 哈希表
哈希表(Hash Tables)
也被称为散列表，是普通数组概念的推广。因
为可以对数组进行直接寻址，故可以在O(1)时间内
碰撞(collision)
在哈希方式下，具有关键字 k的数据元素，存放在槽h(k) 中。 其中h(x)是散列函数。
例如：对于如下 9 个关键字： {Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dai}
设哈希函数 f (key) = (Ord(关键字首字母) - Ord(„A‟) + 1) / 2 0 1 2 3 4
其中di =伪随机序列
例：表长为 11 的哈希表中已填有关键字为 17，60，29 的记录， H(key)=key MOD 11，现有第 4 个记录，其关键字为 38， 按三种处理冲突的方法，将它填入表中。 0 1 2 3 4 5 6 7 8 9 10 38 38 60 17 29 38 (1) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5+2) MOD 11=7 冲突 H3=(5+3) MOD 11=8 不冲突 (2) H(38)=38 MOD 11=5 冲突 H1=(5+1² MOD 11=6 冲突 ) H2=(5-1² MOD 11=4 不冲突 ) (3) H(38)=38 MOD 11=5 冲突 设伪随机数序列为 9，则： H1=(5+9) MOD 11=3 不冲突
2) 由于哈希函数是一个压缩映像，因此，在一般情况下，很容 易产生“冲突”现象，即：key1 key2，而 f (key1) = f (key2)。 这种具有相同函数值的关键字称为同义词。
3) 很难找到一个不产生冲突的哈希函数。一般情况下，只能 选择恰当的哈希函数，使冲突尽可能少地产生。 因此：在构造这种特殊的“查找表”时，除了需要选择一
Han
5
6
Li
7
8
9
10
11
Wu
12
13
Zhou
问题: 若添加关键字 Zhou，会出现什么情况 ？ 从这个例子可见：
Chen Dai
Qian Sun
Zhou Ye Zhao
1) 哈希函数是一个映像，即：将关键字的集合映射到某个地址 集合上。它的设置很灵活，只要使得关键字的哈希函数值都 落在表长允许的范围之内即可；
§9.3 哈希表
直接定址法
取关键字或关键字的某个线性函数值为散列地址，即哈 希函数为关键字的线性函数 H(key) = key 或者 H(key) = a key + b (其中a、b为常数) 例：关键码集合为{ 100，300，500，700，800，900 }， 选取哈希函数为 Hash(key)=key/100，画初存储结构(哈希表) 0 1
1. 直接定址法 2. 数字分析法
4. 折叠法 5. 除留余数法
3. 平方取中法
6. 随机数法
对非数字关键字，常用字符串哈希函数有 BKDRHash，APHash，DJBHash，JSHash， RSHash，SDBMHash，PJWHash，ELFHash等等
§9.3 哈希表
哈希函数的构造方法
§9.3 哈希表
平方取中法（较常用）
构造：以关键字的平方值的中间几位作为哈希地址。 求“关键字的平方值”的目的是“扩大差别”，同时平方 值的中 间各位又能受到整个关键字中各位的影响。
例：2589的平方值为6702921，可以取中间的029为地址。
此方法适合于：关键字中的每一位都有某些数字重复出现
§9.3 哈希表
除留余数法(最常用)
给定一组关键字：12, 39, 18, 24, 33, 21，若取 p = 11, 则他们对
应的哈希函数值将为
0 33 1 12 2 24 3 4 5 6 39 7 18 8 9 10 21
§9.3 哈希表
除留余数法(最常用)
给定一组关键字：12, 39, 18, 24, 33, 21，若取 p = 9, 则他们对应
其中，Random是伪随机函数。
通常，当关键字长度不等时采用此法构造哈希函数较恰当
§9.3 哈希表
哈希函数的构造方法
实际造表时，采用何种构造哈希函数的方法取决于建表的关 键字集合的情况（包括关键字的范围和形态），总的原则是使产 生冲突的可能性降到尽可能地小。 选取哈希函数，考虑以下因素： 1）计算哈希函数所需时间 2）关键字长度 3）哈希表长度（哈希地址范围） 4）关键字分布情况 5）记录的查找频率