数据结构第25讲：第10章查找表可扩充散列-c.ppt

1,一、哈希表是什么？,二、哈希函数的构造方法,三、处理冲突的方法,四、哈希表的查找,9.4 哈 希 表,五.可扩充散列,2,查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程为:,四、哈希表的查找,对于给定值 K,计算哈希地址 Hi=H(K),若 rHi.key=NULL 则查找不成功,若 rHi.key=K 则查找成功,否则“求下一地址 Hi”，直至 rHi.key=NULL(查找不成功)或 rHi.key=K(查找成功)为止。,3,int hashsize=997,.;/一个素数序列typedef struct ElemType*elem;/数据元素存储基址 int count;/当前数据元素个数 int sizeindex;/hashsizesizeindex为当前容量 HashTable;#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE-1,/-开放定址哈希表的存储结构-,4,Status HashSearch(HashTable H,KeyType K,int&p,int&c)/p指示待查数据元素K在表中的位置，c为冲突计数/SearchHash,p=Hash(K);/求得哈希地址,while(H.elemp.key!=NULL/处理冲突,求得下一探查地址 p,if(EQ(K,H.elemp.key)return SUCCESS;/查找成功，返回待查数据元素位置 p,else return UNSUCCESS;/查找不成功,查找算法,5,Status InsertHash(HashTable/重建哈希表/InsertHash,插入算法,6,Status DeleteHash(HashTable&H,Elemtype e)/DeleteHash,else H.elemp=null;-H.count;return OK;,c=0;,if(HashSearch(H,e.key,p,c)=UNSUCCESS)return ERROR;/表中无与 e 有相同关键字的元素,删除算法,H.Infop=deleted;,/将待删除位置置为不可能/出现的值.,/将待删除位置用探测序列/的下一个关键字顺序递补.,/另外定义一个删除标志数组/并置删除标志,p,7,1)选用的哈希函数;2)选用的处理冲突的方法;3)哈希表饱和的程度：装载因子=记录数/表的长度 通常要求 0.5,决定哈希表查找的ASL的因素：,哈希表查找的分析:,从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。,8,查找关键码时所需的平均查找次数,在散列函数中，除留余数法优于其它类型的散列函数，最差的是折叠法。对于冲突处理方法：链地址法优于开放定址法；,链地址法需要增设链接指针,增加了存储？由于开放定址法须保持大量的空闲空间以确保搜索效率，如平方探查法要求装填因子 0.5。而记录所占空间又比指针大得多，故链地址法反而节省存储空间。,9,用不同的冲突处理方法时散列表的平均查找长度,如果取 0.5,1.5,2.5,2,1.25,1.1,10,从以上结果可见，,哈希表的平均查找长度是 的函数，而不是 n 的函数。,这说明，用哈希表构造查找表时，可以选择一个适当的装填因子，使得平均查找长度限定在某个范围内。,这是哈希表所特有的特点。,11,例1：求散列表大小并设计散列函数,条件：设有一个含200个记录的散列表，要求用平方探查法解决冲突，且要求按关键码查询时，找到一个新记录插入位置的平均探查次数不超过1.5。问题：哈希表至少应该多大？并设计哈希函数。分析：对平方探测法，查找不成功的平均搜索长度为 Un1/(1-),解答：根据要求n200，且：Un1/(1-)1.5 1/3=n/m=200/m m 600,12,一、哈希表是什么？,二、哈希函数的构造方法,三、处理冲突的方法,四、哈希表的查找,9.4 哈 希 表,五.可扩充散列,13,五.可扩充散列,问题提出：,1。再散列问题：对于静态散列表，无论使开发定址法还是链址法，都需要静态分配存储空间。如果表的记录太满，则查找和插入的时间将很长，甚至插入操作可能失败。由于静态散列表的长度不能够增加（?），解决的办法只能是另外建立一个新的散列表（原来的两倍），并扫描原来表中的每一个记录，并将其插入到新的散列表中（复制记录）。,数据结构用面向对象方法与C+语言描述清华大学出版社 殷人昆,14,2。哈希表太长，多次访问外存 由于哈希表中的记录数太多，不能够一次装载到内存。只能根据内存缓存区的大小分段载入内存。对于象平方探测这样的开放定址处理冲突方法，进行一次哈希查找就需要进行多次访问外存的操作。,15,可扩充散列是一种动态散列方法，它对传统的散列技术进行了扩充。它采用树型结构实现哈希表的存储结构，使之能够动态（再散列不需要复制）地适应对文件存储容量的需求，并能保持高效（访问外存次数少）的搜索效率。,1.二叉 Trie 树,2.将二叉Trie树转换为目录表,3.插入与目录扩充,4.删除与目录收缩,16,表示关键字集合HAD,HAS,HAVE,HE,HER,HERE,HIGH,HIS,Trie 树,1。多叉2。按字符划分3。查找需要比较,17,根据关键字二进制码的最低 2 位进行划分，可以把这些关键字分成 4 类。假设把它们 4 个页块的文件中,每页最多可以容纳2个关键码。这样就可以利用各关键码的最低2位（00,01,10,11）来决定它们的存储页块。,1.二叉 Trie 树,设关键字序列 A0,A1,B0,B1,C2,C3。若每一个关键码由 2 个字符组成,而每一个字符用 3 个二进制位表示。则有：,页块(桶),18,二叉Trie树：根据各关键码的二进制位表示,从最低位到最高位进行划分,各页块的索引构成一个二叉树结构。二叉Trie树构造方法：首先,在根结点处按各关键码的最低位是 1 还是 0,划分为两组。对于每一组再按次低位是 1 还是 0 继续分组,如此分下去,直到每组剩下不多于 2 个关键码为止。二叉Trie树组成：在二叉Trie树中有两类结点：分支结点和叶结点。分支结点按其相关二进位是 1 还是 0,分为两个分支;叶结点包含指向关键码存放页块的指针。,19,根据关键字二进制码的最低 2 位进行划分，可以把这些关键字分成 4 类。假设把它们 4 个页块的文件中,每页最多可以容纳2个关键码。这样就可以利用各关键码的最低2位（00,01,10,11）来决定它们的存储页块。,1.二叉 Trie 树,设关键字序列 A0,A1,B0,B1,C2,C3。若每一个关键码由 2 个字符组成,而每一个字符用 3 个二进制位表示。则有：,页块(桶),1。二叉2。按二进制位划分3。查找不需要比较,20,二叉trie树是一种树型结构的哈希表 哈希函数：是一种从关键字到二进制码的映射。哈希地址：根据二进制码的最低位进行划分，关键字的二进制码对应trie二叉树从根到叶子结点的路径。叶子结点中存放记录的指针。,二叉trie树 与 哈希表,哈希表的大小：可以动态扩展。？冲突处理方法：？,21,插入 新的关键码 C5（110101）,应把 C5 放到A1,B1所在的第3页中。但是此时该页块已满,发生了溢出（冲突）。为此,将第3页扩充一倍，分裂为两页。,22,再插入 一个新关键码 C1(110001),应将C插入到A1,B1所在的页块中。这时又发生溢出,需要再分裂A1,B1所在页块：根据A1,B1,C1 的最低4位将它们重新分配到这两个页块中。,23,从上面的例子得出两个结论：,如何存储二叉tries树？将二叉Trie树映射为目录表，以避开在二叉Trie树中的长时间搜索过程，根据二进制码直接找到记录存放的页块。,如何生成分布均匀的二进制码？特殊哈希函数，把关键码转换成二进制数字表示的伪随机数集合,1。对某个页块的访问时间取决于区分(搜索)关键字码所需的二进制码位数；2。如果关键字码分布不均匀，最后产生的trie树使倾斜的；,进一步提出两个问题：,24,根据关键字key生成分布均匀的随机二进制数,设：key AB1,1。通过折叠移位累加生成一个十进制数,A B 1,65 66 01,2。采用除留余数法（模为19937的素数）得到一个界于0215 之间的一个十进制数 18617,656601,3。再将这个十进制数转换成一个16位的二进制数 0100 1000 1011 1001,4。取这个二进制数的若干最低位作为随机二进制数,25,2.将二叉Trie树转换为目录表,首先将二叉Trie树的分支结点部分(索引部分)转换为一棵满二叉树，即所有指向叶结点的分支结点都位于同一层次上。,满二叉树,然后再把这棵二叉树映射为指示各个页块的目录表。,满二叉树的深度等于区分关键字所需要的最多二进制位数,有些叶子结点指向同一个页块,26,目录表,满二叉树,目录表由一组目录项（叶子结点）和指向页块的指针组成。每个目录项与二进制码一一对应。如果区分所有的页块需要 k 位二进制数（深度）,则目录项个数应为2k,其编址为 0 到 2k-1。,目录项,项块,27,Trie 二叉树,满二叉树,由于区分4个页块最多需要 2 位二进制数,则目录项个数应为4,28,Trie 二叉树,由于区分 6 个页块最多需要 4 位二进制数,则目录项个数应为 16,29,C5,C3,0000 0001 0010 0011 0100 0101 0110 01111000 1001 1010 1011 1100 1101 1110 1111,B1,C2,A0,B0,A1,C1,30,目录表,二叉trie树,在目录表上如何根据给定值查找页块和记录？,目录项,项块,目录表就是一个哈希表！,给定值B1（101001）,31,访问一个页块的步骤为：1.利用散列函数将给定值散列成随机二进制码；2.根据区分目录项所需二进制位数，取随机二进制码 的若干低位，直接得到目录项的存储地址；3.按此地址检索相关的页块;4.在此页块中查找与给定值相等的记录（成功或失败）；,在目录表上怎样插入和删除记录？插入后页块指针怎样变化？是否需要重新构造目录表？,32,可扩充散列结构：由一个目录表和一组页块构成。定义页块信息：页块的局部深度 PgDepth指明该页块中存放的记录二进码地址的低位部分有多少位是相同的；,PgDepth=2,3.插入与目录扩充,PgDepth=3,PgDepth=2,PgDepth=2,PgDepth=3,33,PgDepth=2,PgDepth=3,PgDepth=2,PgDepth=2,PgDepth=3,定义目录表信息：目录表深度 DirDepth为区分各个页块所需的二进制位数。,DirDepth=3,DirDepth 与 PgDepth 的关系,34,关键码插入及页块分裂,1.在向一个页块插入关键码 key 时,如果该页块不满,可以直接将关键码插入;,C6,C7,插入 C6（110110）和 C7（110111）,35,如果原来指向它的指针唯一(PgDepth=DirDepth)，则在页块分裂后，必须扩充目录表。,插入C5(110101),2.如果该页块已满,需要分裂页块,36,4.若原来页块的 PgDepth=d,分裂后两个兄弟页块的二进制地址都增加一位,它们的局部深度PgDepth=d+1。除了低阶共享的d位外,用更高阶的一位来区分两个兄弟页块。,1.让目录表的深度加1，目录项增加一倍；,3.如果目录项的二进制地址有 k 位,则整个目录 表的深度DirDepth=k,目录项个数有 2k 个。,目录扩充规则,2.原来地址为的目录项改为地址为0，目录项指向的页块不变，同时新增加一个目录项1，目录项的指针与原目录项0的指针相同。,37,插入C4(110 100),如果原来指向它的指针不唯一(PgDepthDirDepth)，则只需要分裂页块，不必扩充目录表。,38,插入C1（100 001）,39,C5,C3,0000 0001 0010 0011 0100 0101 0110 01111000 1001 1010 1011 1100 1101 1110 1111,B1,C2,A0,B0,A1,C1,DirDepth=4,PgDepth=2,PgDepth=4,PgDepth=2,PgDepth=2,PgDepth=3,PgDepth=4,40,1。目录表每次扩大一倍，不需要复制记录。,关于扩大目录的说明：,3。由于插入而引起目录扩大时，散列函数应该不变。这样就能够保证只增加目录表长度，而不影响原来的散列结果。,2。虽然关键字的随机二进制散列地址空间很大，但由于从低位开始划分，区分关键字所需要的二进制位数很小，所需要的空间是动态逐步增加 的。,4。目录表与链址表的区别：目录表：目录项、指针和页块（桶）组成。目录项个增加，页块大小不变 链址表：哈希表头，指针和单链表组成。哈希表头不变，结点可增加。,41,4.删除与目录收缩,在执行关键字删除时:如果被删除关键字所在的页块没有兄弟页块，则只需要删除页块，不需要进行合并。,否则，若两个兄弟页块中关键码个数的总和少于或等于其中一个单独页块的容量时,应将两个页块合并。,如何找某个页块的兄弟页块？,42,求目录项p所指页块的兄弟页块的方法：如果目录项的深度小于目录表深度，即：PgDepth DicDepth 则该目录项没有兄弟页块 否则：若设目录项 p 所指页块的 PgDepth=d,把地址 p 的第 d 位求反,得到一个新的二进制地址 p,地址为 p 的目录项所指页块即为原页块的兄弟页块。,43,删除 C4，,删除 C3，,C4,44,如果目录中指向每一个页块的局部深度都小于目录表的深度,即：PgDepth DicDepth 则需要紧缩目录。其过程与目录扩充的过程相反。,页块中关键码减少可能会导致目录表的紧缩。,删除 B1,45,性能分析,可扩充散列技术是一种非常好的问题解决方法:其目录表的地址空间可以扩充和收缩。在时间方面:用基于目录表的可扩充散列方法进行检索,仅需要 2 次磁盘访问。一次转载目录表，一次转载页块。在空间方面:因增加不均匀分布的关键码可能会导致目录表扩充一倍，许多指针指到同一页块，这样会消耗许多存储空间。,在空间利用率方面评价散列技术的方式仍然用装载因子来衡量:,46,本讲习题,基础知识题（不提交）：9.21，9.22，9.24,