数据结构第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 0111 1000 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 0111 1000 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