6-4散列表的查找技术

6-4散列表的查找技术v第六章查找技术回顾查找技术查找操作要完成什么任务？待查值k确定k在存储结构中的位置前面学过哪些查找技术？这些查找技术有什么共性呢？10152461235409855012345678（1）顺序查找（2）折半查找101520253035404550012345678==、!=<、==、>O(n)O(log2n)O(n)~(log2n)635542907058（3）二叉搜索树查找通过一系列的给定值与关键码的比较，查找效率依赖于查找过程中进行的给定值与关键码的比较次数Ω(log2n)查找技术的分类能否不用比较，通过关键码能够直接确定存储位置？在存储位置和关键码之间建立一个确定的对应关系查找技术比较式查找计算式查找设关键码key在存储结构中的位置是addr，则有addr=H(key)。

学什么？散列查找的基本思想散列函数的设计处理冲突的方法散列查找的性能分析开散列表与闭散列表的比较6-4-1散列查找的基本思想v第六章查找技术散列的基本思想关键码集合ri…………H(ki)Hki散列的基本思想：在记录的关键码和存储地址之间建立一个确定的对应关系，通过计算得到待查记录的地址。散列技术能进行范围查找吗？适合于哪种类型的查找？散列技术最适合回答的问题是：如果有的话，哪个记录的关键码等于待查值？散列的基本概念关键码集合ri…………H(ki)Hki散列表：采用散列技术存储查找集合的连续存储空间。散列表数组散列函数：将关键码映射为散列表中适当存储位置的函数。散列函数散列地址：由散列函数所得的存储地址。散列地址下标散列的关键问题关键码集合ri…………H(ki)Hki如何设计散列函数？如何解决冲突？冲突：对于两个不同关键码ki≠kj，有H(ki)＝H(kj)。同义词：ki和kj相对于H称做同义词。

kj散列是一种完整的存储结构吗？散列只是通过记录的关键码定位该记录，没有完整地表达记录之间的逻辑关系，所以，散列主要是面向查找的存储结构。6-4-2散列函数的设计v第六章查找技术设计原则关键码集合ri…………H(ki)Hki如何设计散列函数？（1）计算简单。散列函数不应该有很大的计算量，否则会降低查找效率。（2）地址均匀。函数值要尽量均匀散布在地址空间，保证存储空间的有效利用并减少冲突。Hash哈希杂凑散列散列技术名称的演变过程：常见的散列函数散列函数是关键码的线性函数，即：H(key)=a

key+b（a，b为常数）例1关键码集合为{10,30,50,70,80,90}，选取的散列函数为H(key)=key/10，散列表构造过程如下：0123456789103050708090直接定址法适用于：事先知道关键码，关键码集合不是很大且连续性较好平方取中法对关键码平方后，按散列表大小，取中间的若干位作为散列地址。适用于：事先不知道关键码的分布且关键码的位数不是很大例2散列地址为2位，设计平方取中法的散列函数。(1234)2＝1522756(1235)2＝1525225平方扩大了相近数之间的差别常见的散列函数除留余数法H(key)=keymodp

如何选取p，才能产生较少的同义词？1470147014散列地址56494235282114关键码例如：p=21=3×777常见的散列函数例3散列表长为15，设计除留余数法的散列函数。

H(key)=keymod13适用于：最简单、最常用，不要求事先知道关键码的分布小于等于表长（最好接近表长）的最小素数或不包含小于20质因子6-4-3处理冲突的方法v第六章查找技术开放定址法开放定址法如何处理冲突？对于给定的关键码key执行下述操作：（1）计算散列地址：j=H(key)如何寻找一个空的散列地址呢？（3）如果在地址j发生冲突，则寻找一个空的散列地址，存储key对应的记录；（2）如果地址j

的存储单元没有存储记录，则存储key对应的记录；（1）线性探测法；（2）二次探测法；（3）随机探测法……闭散列表：用开放定址法处理冲突得到的散列表闭散列表的类定义constintMaxSize=100;classClosedHashTable{public:ClosedHashTable();~ClosedHashTable();intInsert(intk);intDelete(intk);intSearch(intk);private:intH();intht[MaxSize];};ClosedHashTable::ClosedHashTable(){for(inti=0;i<MaxSize;i++)ht[i]=0;}ClosedHashTable::~ClosedHashTable(){}线性探测法Hi=(H(key)＋di)%m

（di=1，2，…，m-1）

线性探测法：从冲突位置的下一个位置起，依次寻找空的散列地址。设散列表的长度为m，对于键值key，发生冲突时，寻找空散列地址的公式为：例1设关键码集合为{47,7,29,11,16,92,22,8,3}，散列表表长为11，散列函数为H(key)=keymod11，用线性探测法处理冲突，散列表的构造过程如下：47729111692292222883333012345678910堆积：非同义词对同一个散列地址争夺的现象伪代码算法：Search输入：闭散列表ht[]，待查值k输出：如果查找成功，则返回记录的存储位置，否则返回查找失败的标志-11.计算散列地址j；2.探测下标i初始化：i=j；3.执行下述操作，直到ht[i]为空：3.1若ht[i]等于k，则查找成功，返回记录在散列表中的下标；3.2否则，i指向下一单元；4.查找失败，返回失败标志-1；算法实现intClosedHashTable::Search(intk){inti,j=H(k);//计算散列地址i=j;//设置比较的起始位置while(ht[i]!=0){if(ht[i]==k)returni;//查找成功elsei=(i+1)%m;//向后探测一个位置}return-1;//查找失败}二次探测法Hi=(H(key)＋di)%m

（di=12,-12,22,-22,…,q2,-q2(q≤m/2)）二次探测法：以冲突位置为中心，跳跃式寻找空的散列地址。设散列表的长度为m，对于键值key，发生冲突时，寻找空散列地址的公式为：例2设关键码集合为{47,7,29,11,16,92,22,8,3}，散列表表长为11，散列函数为H(key)=keymod11，用二次探测法处理冲突，散列表的构造过程如下：4772911169229222288333012345678910相对于线性探测法，二次探测法能够在一定程度上减少堆积设H(ki)=6，H(kj)=5，对于线性探测法：ki的探测序列：6,7,8,9,…kj的探测序列：5,6,7,8,…重合之后再不分开设H(ki)=6，H(kj)=5，对于二次探测法：ki的探测序列：6,7,5,10,2,…kj的探测序列：5,6,4,9,1,…重合之后很快分开二次探测法拉链法拉链法如何处理冲突？对于给定的关键码key执行下述操作：（1）计算散列地址：j=H(key)（2）将key对应的记录插入到同义词子表j中；开散列表：用拉链法处理冲突得到的散列表。开散列表中存储同义词子表的头指针，开散列表不会出现堆积现象同义词子表：所有散列地址相同的记录构成的单链表。开散列表会出现堆积现象吗？开散列表的类定义constintMaxSize=100;classOpenHashTable{public:OpenHashTable();

~OpenHashTable();

intInsert(intk);

intDelete(intk);

Node<int>*Search(intk);private:

intH();

Node<int>*ht[MaxSize];};OpenHashTable::OpenHashTable(){

for(inti=0;i<MaxSize;i++){

ht[i]=nullptr;

}

}012345678910

∧∧∧∧∧∧∧∧∧∧∧析构函数OpenHashTable::~OpenHashTable(){

Node<int>*p=nullptr,*q=nullptr;

for(inti=0;i<MaxSize;i++)

{

p=q=ht[i];

while(p!=nullptr)

{

p=p->next;

deleteq;

q=p;

}

}}012345678910

∧∧∧∧∧11∧

22

47∧

3

92∧

16∧

7∧

29

8∧插入算法例3设关键码集合为{47,7,29,11,16,92,22,8,3}，散列表表长为11，散列函数为H(key)=keymod11，用拉链法处理冲突，在散列表中插入元素33。012345678910

∧∧∧∧∧11∧

22

47∧

3

92∧

16∧

7∧

29

8∧

p33

qNode<int>*OpenHashTable::Insert(intk){j=H(k);Node<int>*p=ht[j];while(p!=nullptr){if(p->data==k)break;elsep=p->next;}if(p==nullptr){q=newNode<int>;q->data=k;q->next=ht[j];ht[j]=q;}}查找算法012345678910

∧∧∧∧∧11∧

22

47∧

3

92∧

16∧

7∧

29

8∧Node<int>*OpenHashTable::Search(intk){intj=H(k);Node<int>*p=ht[j];while(p!=nullptr){if(p->data==k)returnp;elsep=p->next;}returnnullptr;}

p例4设散列函数为H(key)=keymod11，在如下开散列表中，分别给出元素47和14的查找过程。6-4-4散列查找的性能分析v第六章查找技术衡量方法散列技术的查找性能取决于什么？产生冲突后，仍然是给定值与关键码进行比较（1）散列函数是否均匀影响冲突产生的因素有什么？（2）处理冲突的方法例1设关键码集合为{47,7,29,11,16,92,22,8,3}，散列表表长为11，散列函数为H(key)=keymod11，用线性探测法和拉链法处理冲突，分析查找性能。477291116922922228833012345678910查找成功的平均查找长度是：(1×5+2×3+4×1)/9=15/9例3设关键码集合为{47,7,29,11,16,92,22,8,3}，散列表表长为11，散列函数为H(key)=keymod11，用线性探测法和拉链法处理冲突，分析查找性能。012345678910

∧∧∧∧∧11∧

22

47∧

3

92∧

16∧

7∧

29

8∧查找成功的平均查找长度是：(1×6+2×3)/9=12/9衡量方法产生冲突后，仍然是给定值与关键码进行比较（1）散列函数是否均匀影响冲突产生的因素有什么？（2）处理冲突的方法散列技术的查找性能取决于什么？表中填入的记录数散列表的长度

=（3）散列表的装填因子α查找性能散列表的平均查找长度是装填因子α的函数，而不是查找集合中记录个数n的函数——O(1)！6-4-5闭散列表和开散列表的比较v第六章查找技术空间比较闭散列表：开散列表：受数组空间限制，需要考虑存储容量没有记录个数的限制，但子表过长会降低查找效率存储效率较高指针的结构性开销有堆积现象，降低查找效率不会产生堆积现象，效率较高仅适用于静态查找适用于静态查找和动态查找时间比较闭散列表：开散列表：开散列表的删除操作例4设关键码集合{47,7,29,11,16,92,22,8,3}，散列表表长为