湘潭大学 数据结构 课件 Ch05 Hashing_图文.pptVIP

§3 分离链接法 ? 在散列表中查找key Position Find ( ElementType Key, HashTable H ) { Position P; List L; L = H-TheLists[ Hash( Key, H-TableSize ) ]; P = L-Next; while( P != NULL P-Element != Key ) /* Probably need strcmp */ P = P-Next; return P; } 你的散列函数 等同于第三章中给出的执行Find 的程序 -- List ADT §3 分离链接法 ? 向散列表中插入 key void Insert ( ElementType Key, HashTable H ) { Position Pos, NewCell; List L; Pos = Find( Key, H ); if ( Pos == NULL ) { /* Key is not found, then insert */ NewCell = malloc( sizeof( struct ListNode ) ); if ( NewCell == NULL ) FatalError( Out of space!!! ); else { L = H-TheLists[ Hash( Key, H-TableSize ) ]; NewCell-Next = L-Next; NewCell-Element = Key; /* Probably need strcpy! */ L-Next = NewCell; } } } ? 再一次?! ?Tip: 使表的大小与预期的keys的数量大致相等 (即使装填因子 ??1). ? 开放定址法（Open Addressing） 【定义】所谓开放定址法，就是一旦产生了冲突，即该地址已经存放了其它数据元素，就去寻找另一个空的散列地址。 ? 若发生了第 i 次冲突，试探的下一个地址将增加f(i)，基本公式是： hi(key) = (h(key)+f(i)) mod TableSize ( 1≤ i TableSize ) ? f(i)决定了不同的解决冲突方案：线性探测、二次探测、双散列。 在没有装满的散列表中， 空的散列地址是否总能找到？ f(i)= i f(i) = ± i2 f(i) = i*h2(key) Algorithm: insert key into an array of hash table { index = hash(key); initialize i = 0 ------ the counter of probing; while ( collision at index ) { index = ( hash(key) + f(i) ) % TableSize; if ( table is full ) break; else i ++; } if ( table is full ) ERROR (“No space left”); else insert key at index; } 冲突解决函数 f(0) = 0. ?Tip: 平均 ? 0.5. 〖例8〗 将n = 11个C的库函数映射到一个散列表 ht[ ] ，其中b = 26 buckets ， s = 1. 1. 线性探测法（Linear Probing） ? 以增量序列 1，2，……，（TableSize -1）循环试探下一个存储地址。 §4 开放定址法 f ( i ) = i ; /* 线性函数 */ acos atoi char define exp ceil cos float atol floor ctime bucket x 0 1 2 3 4 5 6 7 8 9 10 … … 25 search time acos 1 atoi 2 char 1 define 1 exp 1 ceil 4 cos 5 float 3 atol 9 floor 5 ctime 9 装填因子 ? = 11 / 26 = 0.42 平均有哪些信誉好的足球投注网站次数 = 41 / 11 = 3.73 虽然 p 不大, 但最坏情形可能会 很大. 使用线性探测的预期探测次数： = 1.36 造成一次聚集( primary cluste