高等教育数据结构查找.pptx

基本概念基本概念查找的概念：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找是成功的，此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在这样的一个记录，则称查找不成功的，此时查找的结果为一个空记录或空指针。基本概念基本概念(续续)查找表（查找表（Search TableSearch Table）概念：查找表是由同一类型的数据元素概念：查找表是由同一类型的数据元素 （或记录）（或记录）构成的集合。构成的集合。关键字关键字关键字关键字：数据元素（或记录）中某个数据项的值，它：数据元素（或记录）中某个数据项的值，它可以唯一标识（识别）一个数据元素（或记录）。若可以唯一标识（识别）一个数据元素（或记录）。若此关键字可以唯一地标识一个记录，则称此关键字为此关键字可以唯一地标识一个记录，则称此关键字为主关键字主关键字主关键字主关键字。查找表的操作类型查找表的操作类型 在查找某个在查找某个“特定的特定的”数据元素是否存在表中数据元素是否存在表中 检索某个检索某个“特定的特定的”数据元素的各种属性数据元素的各种属性 在查找表中插入一个数据元素在查找表中插入一个数据元素 从查找表中删除一个数据元素从查找表中删除一个数据元素查找表类型查找表类型 根据对查找表所进行查找操作的不同，根据对查找表所进行查找操作的不同，查找表可被分为两类：查找表可被分为两类：静态查找表：若对查找表只做查静态查找表：若对查找表只做查找操作，则此类查找表是静态查找表。找操作，则此类查找表是静态查找表。动态查找表：若在查找过程中进动态查找表：若在查找过程中进行插入或删除操作，则此类查找表是动行插入或删除操作，则此类查找表是动态查找表。态查找表。基本概念基本概念(续续)9.9.1 1 静态查找表静态查找表9.9.1.1 1.1 顺序表的查找顺序表的查找1.1.基本思想：基本思想：当以顺序表或线性链表表示静态查找当以顺序表或线性链表表示静态查找表时，可采用顺序查找法。表时，可采用顺序查找法。关于线性链表的顺序查找法在关于线性链表的顺序查找法在单链表单链表中有类似的描述，这里不重点讲。下中有类似的描述，这里不重点讲。下面重点讲顺序表中的查找。面重点讲顺序表中的查找。顺序查找法的过程为：从表的一端（如最后顺序查找法的过程为：从表的一端（如最后一个记录）开始，逐个进行一个记录）开始，逐个进行记录的关键字与记录的关键字与记录的关键字与记录的关键字与给定值的比较给定值的比较给定值的比较给定值的比较，若相等，则查找成功；否则，若相等，则查找成功；否则，若直至表的另一端（如第一个记录）仍未相若直至表的另一端（如第一个记录）仍未相等，则查找不成功（失败）。等，则查找不成功（失败）。2.2.顺序查找的实现。顺序查找的实现。#defineEQ(a,b)(a)=(b)typedefintKeyType;/*可换为可换为char,float等类型等类型*/typedefstructKeyTypeKey;/*关键字域关键字域*/;/*其他域，如其他域，如data数据域等数据域等*/ElemType;/*-静态查找表的顺序存储结构静态查找表的顺序存储结构-*/typedefstructElemType*elem;/*存储空间基址存储空间基址,0号单元留空号单元留空*/intlength;/*当前长度当前长度*/SSTable;intSearch_Seq(SSTableST,KeyTypekey)ST.elem0.Key=key;/*监视哨监视哨监视哨监视哨*/for(i=ST.length;!EQ(ST.elemi.Key,key);-i);returni;/*找不到时，找不到时，找不到时，找不到时，i=0;i=0;因为因为因为因为ST.elem0.Key=keyST.elem0.Key=key*/Search_Seq3.3.性能分析：性能分析：平均查找长度平均查找长度 为确定记录在查找表中的位置，需要为确定记录在查找表中的位置，需要和关键字进行的比较的关键字个数的期和关键字进行的比较的关键字个数的期望值，称为平均查找长度望值，称为平均查找长度ASL。在等概率的情况下，顺序查找成功时的在等概率的情况下，顺序查找成功时的平均查找长度为：平均查找长度为：ASL=(n+1)/2ASL=(n+1)/2顺序查找的优点和缺点顺序查找的优点和缺点算法简单，且对表的结构无任何要求（比如算法简单，且对表的结构无任何要求（比如记录不必按关键字排序、记录不必按关键字排序、线性链表也可以用线性链表也可以用顺序查找顺序查找）。）。查找效率较低，当查找效率较低，当n n较大时，不宜采用顺序较大时，不宜采用顺序查找。查找。9.1.2有序表的查找（二分查找）有序表的查找（二分查找）1.1.基本思想：基本思想：又称又称“折半查找折半查找”，先确定待查记录所在的范，先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不围（区间），然后逐步缩小范围直到找到或找不到该记录为止。到该记录为止。设当前搜索的区间为设当前搜索的区间为设当前搜索的区间为设当前搜索的区间为(ST.elemlow,(ST.elemlow,(ST.elemlow,(ST.elemlow,ST.elemlow+1,ST.elemlow+1,ST.elemlow+1,ST.elemlow+1,ST.elemhigh),ST.elemhigh),ST.elemhigh),ST.elemhigh),若令若令若令若令mid mid mid mid=(low+high)/2=(low+high)/2=(low+high)/2=(low+high)/2指示区间的中间位置指示区间的中间位置指示区间的中间位置指示区间的中间位置，则这则这则这则这种二分搜索称为种二分搜索称为种二分搜索称为种二分搜索称为折半搜索折半搜索折半搜索折半搜索。折半搜索算法将表划分成几乎相等的两个子表折半搜索算法将表划分成几乎相等的两个子表折半搜索算法将表划分成几乎相等的两个子表折半搜索算法将表划分成几乎相等的两个子表.下面的具体例子来模拟折半搜索算法的执行过程。其中，方括号内下面的具体例子来模拟折半搜索算法的执行过程。其中，方括号内是当前搜索的表，带下画线的整数是当前与待查关键字值是当前搜索的表，带下画线的整数是当前与待查关键字值keykey比较比较的关键字值。的关键字值。(1)key=66，搜索成功：，搜索成功：21303641525466728397213036415254667283972130364152546672839721303641525466728397(2)key=35，搜索失败：，搜索失败：21303641525466728397213036415254667283972130364152546672839721303641525466728397上述搜索过程可以用一棵二叉树来描述。通常称描述搜索上述搜索过程可以用一棵二叉树来描述。通常称描述搜索算法执行过程的二叉树为算法执行过程的二叉树为二叉判定树二叉判定树(binarydecisiontree)。3.3.3.3.折半查找性能分析折半查找性能分析折半查找性能分析折半查找性能分析 通过对相应二叉判定树的分析可知：通过对相应二叉判定树的分析可知：折半查找在查找成功时，和给定值进行比较折半查找在查找成功时，和给定值进行比较的关键字个数至多为的关键字个数至多为 loglog2 2n n +1+1，查找不查找不成功时的比较次数最多也不超过成功时的比较次数最多也不超过loglog2 2n n +1+1。优点：查找的效率比顺序查找高。优点：查找的效率比顺序查找高。局限性：要求查找表有序；只适用于顺序存储局限性：要求查找表有序；只适用于顺序存储结构结构。9.1.4索引顺序表的查找（分块查找）索引顺序表的查找（分块查找）又称又称“索引顺序查找索引顺序查找”，是顺序查找的一，是顺序查找的一种改进方法，是一种性能介于顺序查找和二分种改进方法，是一种性能介于顺序查找和二分查找之间的一种查找方法。在查找法中，除表查找之间的一种查找方法。在查找法中，除表本身外，尚需建立一个本身外，尚需建立一个“索引表索引表”。ASLASL比顺比顺序查找有了很大改进，但远不及折半查找。序查找有了很大改进，但远不及折半查找。9.9.2 2 动态查找表动态查找表 9.9.2.1 2.1 二叉二叉排序排序树和平衡二叉树树和平衡二叉树1.1.二叉排序树二叉排序树二叉排序树二叉排序树(二叉搜索树二叉搜索树二叉搜索树二叉搜索树)的概念的概念:二叉排序树是一种动态树表。二叉排序树是一种动态树表。二叉排序树的定义：二叉排序树或者是一棵空树，二叉排序树的定义：二叉排序树或者是一棵空树，或者是一棵具有如下性质的二叉树：或者是一棵具有如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值若它的左子树非空，则左子树上所有结点的值均小于根结点的值；均小于根结点的值；若它的右子树非空，则右子树上所有结点的值若它的右子树非空，则右子树上所有结点的值均大于根结点的值；均大于根结点的值；左、右子树本身又各是一棵二叉排序树。左、右子树本身又各是一棵二叉排序树。二叉排序树的性质：二叉排序树的性质：按中序遍历二叉排序树，所按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列。得到的中序遍历序列是一个递增有序序列。2.2.二叉排序树的查找二叉排序树的查找:在二叉排序树中进行查找的过程和二分查找类似，也是在二叉排序树中进行查找的过程和二分查找类似，也是在二叉排序树中进行查找的过程和二分查找类似，也是在二叉排序树中进行查找的过程和二分查找类似，也是一个逐步缩小查找范围的过程。一个逐步缩小查找范围的过程。一个逐步缩小查找范围的过程。一个逐步缩小查找范围的过程。若查找成功，则是走了一条若查找成功，则是走了一条从根结点到待查结点的路径；若查找失败，则是走了一条根从根结点到待查结点的路径；若查找失败，则是走了一条根结点到某个叶子结点的路径。因此，查找过程中和关键字比结点到某个叶子结点的路径。因此，查找过程中和关键字比较的次数不超过树的深度。较的次数不超过树的深度。由于含有由于含有n n个结点的二叉排序树不唯一，形态和深度可能不个结点的二叉排序树不唯一，形态和深度可能不同。故含有同。故含有n n个结点的二叉排序树的平均查找长度和树的形态个结点的二叉排序树的平均查找长度和树的形态有关。有关。最好的情况是：最好的情况是：二叉排序树和二叉判定树形态相同。二叉排序树和二叉判定树形态相同。最坏的情况是：最坏的情况是：二叉排序树为单支树，这时的平均查找长二叉排序树为单支树，这时的平均查找长度和顺序查找时相同。度和顺序查找时相同。最坏情况示例最坏情况示例 就平均性能而言，二叉排序树上的查找和二分查找相差就平均性能而言，二叉排序树上的查找和二分查找相差不大，并且二叉排序树上的插入和删除结点十分方便，无须不大，并且二叉排序树上的插入和删除结点十分方便，无须大量移动结点。大量移动结点。4.4.平衡二叉树平衡二叉树(1)(1)平衡二叉树的概念平衡二叉树的概念:平衡二叉树（又称平衡二叉树（又称AVLAVL树）是指形态匀称的二叉树，树）是指形态匀称的二叉树，严格的定义为：严格的定义为：平衡二叉树或者是空树，或者是任何结点的左子平衡二叉树或者是空树，或者是任何结点的左子树和右子树的高度最多相差树和右子树的高度最多相差1 1的的二叉树。的的二叉树。结点的平衡因子结点的平衡因子BFBF：指该结点的左子树高度和右指该结点的左子树高度和右子树的高度之差。子树的高度之差。平衡二叉树的性质：平衡二叉树上所有结点的平平衡二叉树的性质：平衡二叉树上所有结点的平衡因子只可能是衡因子只可能是-1-1、0 0、1 1。平衡二叉树示例平衡二叉树示例 非平衡二叉树示例非平衡二叉树示例 9.9.2.2 B-2.2 B-树和树和B+B+树树 B-B-树是用于文件系统，它是一种平衡的多叉树，其定义树是用于文件系统，它是一种平衡的多叉树，其定义如下：如下：一棵一棵m m阶的阶的B-B-树满足下列条件：树满足下列条件：树中每个结点至多有树中每个结点至多有m m个孩子；个孩子；除根结点和叶子结点外，其它每个结点至少有除根结点和叶子结点外，其它每个结点至少有m/2m/2个孩子；个孩子；若根结点不是叶子结点，则至少有若根结点不是叶子结点，则至少有2 2个孩子；个孩子；所有叶子结点都出现在同一层，叶子结点不包含所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息；任何关键字信息；有有k k个孩子的非终端结点恰好包含有个孩子的非终端结点恰好包含有k-1k-1个关键字。个关键字。9.9.3 3 哈希表哈希表 （HashHash TableTable）9.3.1 9.3.1 什么是哈希表什么是哈希表9.3.2 9.3.2 哈希函数的构造方法哈希函数的构造方法9.3.3 9.3.3 处理冲突的方法处理冲突的方法9.3.1什么是哈希表什么是哈希表例子例子1-1-线性索引线性索引 有一个存放职工信息的数据表，每一个职有一个存放职工信息的数据表，每一个职工对象有近工对象有近40 40 字节的信息。字节的信息。哈希表（散列表）的概念哈希表（散列表）的概念散列方法散列方法散列方法散列方法：在记录的存储位置：在记录的存储位置：在记录的存储位置：在记录的存储位置AddressAddressAddressAddress （在一个有限（在一个有限（在一个有限（在一个有限的连续的地址区间中）与它的关键字的连续的地址区间中）与它的关键字的连续的地址区间中）与它的关键字的连续的地址区间中）与它的关键字keykeykeykey之间建立一个之间建立一个之间建立一个之间建立一个确定的对应函数关系确定的对应函数关系确定的对应函数关系确定的对应函数关系H H H H(keykeykeykey)，使每个关键字与结构中，使每个关键字与结构中，使每个关键字与结构中，使每个关键字与结构中一个唯一存储位置相对应：一个唯一存储位置相对应：一个唯一存储位置相对应：一个唯一存储位置相对应：AddressAddressAddressAddress H H H H(keykeykeykey)在搜索时，首先对给定的关键字进行函数计算，把函在搜索时，首先对给定的关键字进行函数计算，把函在搜索时，首先对给定的关键字进行函数计算，把函在搜索时，首先对给定的关键字进行函数计算，把函数值当做记录的存储位置，在结构中按此位置取记录数值当做记录的存储位置，在结构中按此位置取记录数值当做记录的存储位置，在结构中按此位置取记录数值当做记录的存储位置，在结构中按此位置取记录的关键字与该给定的关键字比较。若相等，则搜索成的关键字与该给定的关键字比较。若相等，则搜索成的关键字与该给定的关键字比较。若相等，则搜索成的关键字与该给定的关键字比较。若相等，则搜索成功。在存放记录时，根据相同函数计算存储位置，并功。在存放记录时，根据相同函数计算存储位置，并功。在存放记录时，根据相同函数计算存储位置，并功。在存放记录时，根据相同函数计算存储位置，并按此位置存放。这种方法就是按此位置存放。这种方法就是按此位置存放。这种方法就是按此位置存放。这种方法就是散列方法散列方法散列方法散列方法。在散列方法中使用的转换函数叫做在散列方法中使用的转换函数叫做在散列方法中使用的转换函数叫做在散列方法中使用的转换函数叫做散列函数散列函数散列函数散列函数。存储位。存储位。存储位。存储位置置置置AddressAddressAddressAddress称为称为称为称为哈希地址哈希地址哈希地址哈希地址或或或或散列地址散列地址散列地址散列地址。而按此种想法构造出来的表或结构就叫做而按此种想法构造出来的表或结构就叫做而按此种想法构造出来的表或结构就叫做而按此种想法构造出来的表或结构就叫做散列表或哈散列表或哈散列表或哈散列表或哈希表希表希表希表。使使使使用用用用散散散散列列列列方方方方法法法法进进进进行行行行搜搜搜搜索索索索不不不不必必必必进进进进行行行行多多多多次次次次关关关关键键键键字字字字的的的的比比比比较较较较，搜搜搜搜索索索索速速速速度度度度比比比比较较较较快快快快，可可可可以以以以直直直直接接接接到到到到达达达达或或或或逼逼逼逼近近近近具具具具有有有有此此此此关关关关键键键键字字字字的记录的实际存放地址。的记录的实际存放地址。的记录的实际存放地址。的记录的实际存放地址。散散散散列列列列函函函函数数数数是是是是一一一一个个个个压压压压缩缩缩缩映映映映象象象象函函函函数数数数。散散散散列列列列函函函函数数数数是是是是从从从从关关关关键键键键字字字字集集集集合合合合到到到到地地地地址址址址集集集集合合合合的的的的影影影影像像像像，关关关关键键键键字字字字集集集集合合合合比比比比散散散散列列列列地地地地址址址址集集集集合合合合大大大大得得得得多多多多。因因因因此此此此有有有有可可可可能能能能经经经经过过过过散散散散列列列列函函函函数数数数的的的的计计计计算算算算，把把把把不不不不同同同同的的的的关关关关键键键键字字字字映映映映射射射射到到到到同同同同一一一一个个个个散散散散列列列列地地地地址址址址上上上上，这这这这就就就就产产产产生生生生了了了了冲冲冲冲突突突突 (Collision)(Collision)(Collision)(Collision)。示例：有一组记录，其关键字分别是示例：有一组记录，其关键字分别是示例：有一组记录，其关键字分别是示例：有一组记录，其关键字分别是 12361,07251,03309,3097612361,07251,03309,3097612361,07251,03309,3097612361,07251,03309,30976 采用的散列函数是采用的散列函数是采用的散列函数是采用的散列函数是 hashhashhashhash(x x x x)=)=)=)=x x x x%73+13420%73+13420%73+13420%73+13420 其中，其中，其中，其中，“%”是除法取余操作。是除法取余操作。是除法取余操作。是除法取余操作。则则则则 有有有有：hash(12361)hash(12361)hash(12361)hash(12361)=hash(07251)hash(07251)hash(07251)hash(07251)=hash(03309)hash(03309)hash(03309)hash(03309)=hash(30976)hash(30976)hash(30976)hash(30976)=13444134441344413444。就就就就是是是是说说说说，对对对对不不不不同同同同的的的的关关关关键键键键字字字字，通通通通过过过过散散散散列列列列函函函函数数数数的的的的计计计计算算算算，得得得得到到到到了了了了同同同同一一一一散散散散列列列列地地地地址址址址。我我我我们们们们称称称称这这这这些些些些产产产产生生生生冲冲冲冲突突突突的的的的散散散散列地址相同的不同关键字为列地址相同的不同关键字为列地址相同的不同关键字为列地址相同的不同关键字为同义词。同义词。同义词。同义词。构造要求：构造要求：构造要求：构造要求：哈希哈希哈希哈希函数的定义域函数的定义域函数的定义域函数的定义域(即关键字集合即关键字集合即关键字集合即关键字集合)必须包括所有必须包括所有必须包括所有必须包括所有可能的关键字，如果散列表允许有可能的关键字，如果散列表允许有可能的关键字，如果散列表允许有可能的关键字，如果散列表允许有 n n n n个地址时个地址时个地址时个地址时,其值域（即哈希地址集合）必须在其值域（即哈希地址集合）必须在其值域（即哈希地址集合）必须在其值域（即哈希地址集合）必须在 0 0 0 0 到到到到 n-1 n-1 n-1 n-1 之间。之间。之间。之间。关键字经过关键字经过关键字经过关键字经过哈希哈希哈希哈希函数计算出来的函数计算出来的函数计算出来的函数计算出来的“随机地址随机地址随机地址随机地址”应应应应能均匀分布在整个地址空间中：若能均匀分布在整个地址空间中：若能均匀分布在整个地址空间中：若能均匀分布在整个地址空间中：若 key key key key 是从关键是从关键是从关键是从关键字集合中随机抽取的一个关键字，字集合中随机抽取的一个关键字，字集合中随机抽取的一个关键字，字集合中随机抽取的一个关键字，哈希哈希哈希哈希函数应能以函数应能以函数应能以函数应能以同等概率同等概率同等概率同等概率取取取取 0 0 0 0 到到到到 n-1 n-1 n-1 n-1 中的每一个值。从而中的每一个值。从而中的每一个值。从而中的每一个值。从而尽量减尽量减尽量减尽量减少冲突。少冲突。少冲突。少冲突。9.3.2 9.3.2 哈希函数的构造方法哈希函数的构造方法 1.1.直接定址法直接定址法 此类函数取关键字的某个线性函数值作此类函数取关键字的某个线性函数值作为散列地址：为散列地址：H(key)H(key)a*key+ba*key+b a,a,b b为常数为常数 由于这类散列函数是一对一的映射，而且散列由于这类散列函数是一对一的映射，而且散列地址集合的大小与关键字集合的大小相同，因地址集合的大小与关键字集合的大小相同，因此一般不会产生冲突，但是实际应用很少。此一般不会产生冲突，但是实际应用很少。示例：有一组关键字如下：示例：有一组关键字如下：942148,941269,940527,941630,942148,941269,940527,941630,941805,941558,942047,940001 941805,941558,942047,940001。散列函数为散列函数为 H(key)=key-940000H(key)=key-940000则有则有H(942148)=2148 H(941269)=1269H(942148)=2148 H(941269)=1269H(940527)=527 H(941630)=1630H(940527)=527 H(941630)=1630H(941805)=1805 H(941558)=1558H(941805)=1805 H(941558)=1558H(942047)=2047 H(940001)=1H(942047)=2047 H(940001)=1 5.5.除留余数法除留余数法设散列表中允许的地址数为设散列表中允许的地址数为 n n。根据经验，取。根据经验，取一个不大于一个不大于 n n，但最接近于或等于，但最接近于或等于 n n 的的质数质数 p,p,或选取一个不包含小于或选取一个不包含小于2020的质因数的的质因数的合数合数p p，利用以下散列函数把关键字转换成散列地址：，利用以下散列函数把关键字转换成散列地址：H(key)=key%pH(key)=key%pp p n n其中其中,“%”是整数除法取余的运算或称为是整数除法取余的运算或称为取取模运算模运算modmod。质数和合数质数和合数：只有：只有1 1和它本身两个约数的数，和它本身两个约数的数，叫质数；除了叫质数；除了1 1和它本身两个约数外，还有其和它本身两个约数外，还有其它约数的数，叫合数它约数的数，叫合数。示例：示例：有一个关键字有一个关键字有一个关键字有一个关键字 key=962148key=962148key=962148key=962148，散列表大小，散列表大小，散列表大小，散列表大小 n=n=n=n=25252525，即，即，即，即 HT24HT24HT24HT24。取质数取质数取质数取质数 p=23p=23p=23p=23（不大于（不大于（不大于（不大于25252525的质数），散列函数的质数），散列函数的质数），散列函数的质数），散列函数 hash(key)=key%phash(key)=key%phash(key)=key%phash(key)=key%p。则散列地址为则散列地址为则散列地址为则散列地址为 hash(962148)=962148%23=12 hash(962148)=962148%23=12 hash(962148)=962148%23=12 hash(962148)=962148%23=12。需要注意的是，使用上面的散列函数计算出来的需要注意的是，使用上面的散列函数计算出来的需要注意的是，使用上面的散列函数计算出来的需要注意的是，使用上面的散列函数计算出来的地址范围是地址范围是地址范围是地址范围是 0 0 0 0到到到到 22222222（不到（不到（不到（不到24242424，因为除数，因为除数，因为除数，因为除数p=23p=23p=23p=23），），），），因此，因此，因此，因此，从从从从23232323到到到到24242424只可能在处理溢出时达到这些地只可能在处理溢出时达到这些地只可能在处理溢出时达到这些地只可能在处理溢出时达到这些地址址址址。9.3.3 9.3.3 处理冲突的方法处理冲突的方法因为任一种均匀散列函数可以减少冲突，但不能因为任一种均匀散列函数可以减少冲突，但不能避免产生冲突，因此选择好的解决冲突的方法十避免产生冲突，因此选择好的解决冲突的方法十分必要。分必要。处理冲突的基本思想：处理冲突的基本思想：处理冲突的基本思想：处理冲突的基本思想：所有的记录都直接放在散列表数组中。所有的记录都直接放在散列表数组中。所有的记录都直接放在散列表数组中。所有的记录都直接放在散列表数组中。因此每个数组元素因此每个数组元素因此每个数组元素因此每个数组元素对应一个记录。对应一个记录。对应一个记录。对应一个记录。若设散列表地址集合为若设散列表地址集合为若设散列表地址集合为若设散列表地址集合为 0 0 0 0 到到到到 n-1n-1n-1n-1，当要，当要，当要，当要加入加入加入加入一个记录一个记录一个记录一个记录 R R R R2 2 2 2时时时时,用它的关键字用它的关键字用它的关键字用它的关键字 R R R R2 2 2 2.key.key.key.key，通过散列函数，通过散列函数，通过散列函数，通过散列函数 H(RH(RH(RH(R2 2 2 2.key).key).key).key)的计算，得到它的哈希地址的计算，得到它的哈希地址的计算，得到它的哈希地址的计算，得到它的哈希地址 j(0 j(0 j(0 j(0 j j j j n-1)n-1)n-1)n-1)，但是发现，但是发现，但是发现，但是发现这个位置上已经被另一个记录这个位置上已经被另一个记录这个位置上已经被另一个记录这个位置上已经被另一个记录 R R R R1 1 1 1 占据了。这时就发生了占据了。这时就发生了占据了。这时就发生了占据了。这时就发生了冲突冲突冲突冲突，则，则，则，则处理冲突处理冲突处理冲突处理冲突就是把就是把就是把就是把 R R R R2 2 2 2 存放到表中下一个存放到表中下一个存放到表中下一个存放到表中下一个”空空空空“（即该地址上没有记录）的哈希地址（即该地址上没有记录）的哈希地址（即该地址上没有记录）的哈希地址（即该地址上没有记录）的哈希地址中。中。中。中。在处理冲突过程中，可能得到一个地址序列在处理冲突过程中，可能得到一个地址序列在处理冲突过程中，可能得到一个地址序列在处理冲突过程中，可能得到一个地址序列H H H Hi i i i，i=1,2,i=1,2,i=1,2,i=1,2,k,H,k,H,k,H,k,Hi i i i 0,n-10,n-1。即在处理冲突时，若得到的另一。即在处理冲突时，若得到的另一。即在处理冲突时，若得到的另一。即在处理冲突时，若得到的另一个哈希地址个哈希地址个哈希地址个哈希地址H H H H1 1 1 1仍然发生冲突，则再求下一个地址仍然发生冲突，则再求下一个地址仍然发生冲突，则再求下一个地址仍然发生冲突，则再求下一个地址H H H H2 2 2 2，若，若，若，若H H H H2 2 2 2仍然发生冲突，则再求下一个地址仍然发生冲突，则再求下一个地址仍然发生冲突，则再求下一个地址仍然发生冲突，则再求下一个地址H H H H3 3 3 3，以此类推，直到，以此类推，直到，以此类推，直到，以此类推，直到H H H Hk k k k不发生冲突为止，则不发生冲突为止，则不发生冲突为止，则不发生冲突为止，则H H H HK K K K为记录在表中的地址。为记录在表中的地址。为记录在表中的地址。为记录在表中的地址。通常用的处理冲突的方法通常用的处理冲突的方法开放定址法开放定址法开放定址法开放定址法(1)(1)(1)(1)线性探测再散列线性探测再散列线性探测再散列线性探测再散列(2)(2)(2)(2)二次探测再散列二次探测再散列二次探测再散列二次探测再散列(3)(3)(3)(3)伪随机探测再散列伪随机探测再散列伪随机探测再散列伪随机探测再散列再哈希法再哈希法再哈希法再哈希法链地址法链地址法链地址法链地址法建立一个公共溢出区建立一个公共溢出区建立一个公共溢出区建立一个公共溢出区1.1.开放定址法开放定址法”空空“的哈希地址的哈希地址H Hi i i i的计算公式为：的计算公式为：H Hi i=(H(key)+d=(H(key)+di i)MODn)MODn i=1,2,k(ki=1,2,k(k n-1)(9-25)n-1)(9-25)其中，其中，其中，其中，H(key)H(key)是哈希函数，是哈希函数，是哈希函数，是哈希函数，n n n n为哈希表的长度。为哈希表的长度。为哈希表的长度。为哈希表的长度。d di i为增量序列，可以有下列为增量序列，可以有下列为增量序列，可以有下列为增量序列，可以有下列3 3 3 3种取法：种取法：种取法：种取法：(1)(1)(1)(1)线性探测再散列：线性探测再散列：线性探测再散列：线性探测再散列：d d d di i i i=1=1=1=1，2 2 2 2，3 3 3 3，n-1n-1n-1n-1(2)(2)(2)(2)二次探测再散列二次探测再散列二次探测再散列二次探测再散列:d:d:d:di i i i=1=1=1=12 2 2 2，-1-1-1-12 2 2 2,2,2,2,22 2 2 2，-2-2-2-22 2 2 2,3,3,3,32 2 2 2，k k k k2 2 2 2(3)(3)(3)(3)伪随机探测再散列伪随机探测再散列伪随机探测再散列伪随机探测再散列:d:d:d:di i i i=伪随机数序列伪随机数序列伪随机数序列伪随机数序列 1.1.开放定址法开放定址法 举例举例假设哈希表的长度为假设哈希表的长度为假设哈希表的长度为假设哈希表的长度为11111111，即，即，即，即n=11,n=11,n=11,n=11,哈希函数哈希函数哈希函数哈希函数H(key)=key MOD 11H(key)=key MOD 11H(key)=key MOD 11H(key)=key MOD 11，则哈希地址集合为则哈希地址集合为则哈希地址集合为则哈希地址集合为0 0 0 0 10101010，此时的哈希表为空，如下图所示。表中每一单，此时的哈希表为空，如下图所示。表中每一单，此时的哈希表为空，如下图所示。表中每一单，此时的哈希表为空，如下图所示。表中每一单元都可以存放一个记录，这里，为了简单起见，元都可以存放一个记录，这里，为了简单起见，元都可以存放一个记录，这里，为了简单起见，元都可以存放一个记录，这里，为了简单起见，假定记录只有一个关键字域。假定记录只有一个关键字域。假定记录只有一个关键字域。假定记录只有一个关键字域。又有一组关键字为又有一组关键字为又有一组关键字为又有一组关键字为17171717，60606060，29292929，38383838。下面如何构。下面如何构。下面如何构。下面如何构造哈希表？造哈希表？造哈希表？造哈希表？0123456789101.1.开放定址法开放定址法 举例举例 (1)(1)采用线性探测再散列的方法处理采用线性探测再散列的方法处理 由于由于由于由于H(17)=17 MOD 11=6H(17)=17 MOD 11=6H(17)=17 MOD 11=6H(17)=17 MOD 11=6，所以将，所以将，所以将，所以将17171717加入到哈希地址为加入到哈希地址为加入到哈希地址为加入到哈希地址为6 6 6 6的单元中；的单元中；的单元中；的单元中；由于由于由于由于H(60)=60 MOD 11=5H(60)=60 MOD 11=5H(60)=60 MOD 11=5H(60)=60 MOD 11=5，所以将，所以将，所以将，所以将60606060加入到哈希地址为加入到哈希地址为加入到哈希地址为加入到哈希地址为5 5 5 5的单元中；的单元中；的单元中；的单元中；由于由于由于由于H(29)=29 MOD 11=7H(29)=29 MOD 11=7H(29)=29 MOD 11=7H(29)=29 MOD 11=7，所以将，所以将，所以将，所以将29292929加入到哈希地址为加入到哈希地址为加入到哈希地址为加入到哈希地址为7 7 7 7的单元中；的单元中；的单元中；的单元中；由于由于由于由于H(38)=38 MOD 11=5H(38)=38 MOD 11=5H(38)=38 MOD 11=5H(38)=38 MOD 11=5，此时发生冲突（即，此时发生冲突（即，此时发生冲突（即，此时发生冲突（即38383838与与与与60606060），另一个哈希地），另一个哈希地），另一个哈希地），另一个哈希地址址址址H H1 1=(H(38)+1)MOD11=6=(H(38)+1)MOD11=6，仍然冲突，仍然冲突，仍然冲突，仍然冲突（即（即（即（即38383838与与与与17171717），下一个哈希地），下一个哈希地），下一个哈希地），下一个哈希地址址址址H H2 2=(H(38)+2)MOD11=7=(H(38)+2)MOD11=7，仍然冲突，仍然冲突，仍然冲突，仍然冲突（即（即（即（即38383838与与与与29292929），下一个哈希地），下一个哈希地），下一个哈希地），下一个哈希地址址址址H H3 3=(H(38)+3)MOD11=8=(H(38)+3)MOD11=8，此时没有冲突，所以，此时没有冲突，所以，此时没有冲突，所以，此时没有冲突，所以将将将将38383838加入到哈希地加入到哈希地加入到哈希地加入到哈希地址为址为址为址为8 8 8 8的单元中；的单元中；的单元中；的单元中；012345678910601729381.1.开放定址法开放定址法 举例举例 (2)(2)采用二次探测再散列的方法处理采用二次探测再散列的方法处理 由于由于由于由于H(17)=17 MOD 11=6H(17)=17 MOD 11=6H(17)=17 MOD 11=6H(17)=17 MOD 11=6，所以将，所以将，所以将，所以将17171717加入到哈希地址为加入到哈希地址为加入到哈希地址为加入到哈希地址为6 6 6 6的单元中；的单元中；的单元中；的单元中；由于由于由于由于H(60)=60 MOD 11=5H(60)=60 MOD 11=5H(60)=60 MOD 11=5H(60)=60 MOD 11=5，所以将，所以将，所以将，所以将60606060加入到哈希地址为加入到哈希地址为加入到哈希地址为加入到哈希地址为5 5 5 5的单元中；的单元中；的单元中；的单元中；由于由于由于由于H(29)=29 MOD 11=7H(29)=29 MOD 11=7H(29)=29 MOD 11=7H(29)=29 MOD 11=7，所以将，所以将，所以将，所以将29292929加入到哈希地址为加入到哈希地址为加入到哈希地址为加入到哈希地址为7 7 7 7的单元中；的单元中；的单元中；的单元中；由于由于由于由于H(38)=38 MOD 11=5H(38)=38 MOD 11=5H(38)=38 MOD 11=5