淺談hashppt課件-在線瀏覽
2025-06-16 03:10本頁(yè)面
【正文】 od 13=12 46 mod 13=7 5 mod 13=5 15 mod 13=2 31 mod 13=5 哈希表、哈希函數(shù)、沖突 如何解決沖突，下面再說(shuō) A:(18,75,60,43,54,90,46) C=2(負(fù)的也可以 ) m[20]:=18 m[77]:=75 m[62]:=60 m[45]:=43 m[56]:=54 m[92]:=90 m[48]:=46 C=0時(shí) 直接定址法 以關(guān)鍵字 Key 本身或關(guān)鍵字加上某個(gè)數(shù)值常量 C 作為散列地址的方法?，F(xiàn)在要儲(chǔ)存和使用下面的線性表： A: (1,75,324,43,1353,90,46). 我們可以定義一維數(shù)組 a:array[1..n] of longint。 我們需要用 O(n)的時(shí)間來(lái)查找某個(gè)元素 也可以定義 a:array[1..1353] of longint 使 a[key]:=key。散列函數(shù)為： h(Key)=Key+C，若 C 為 0，則散列地址就是關(guān)鍵字本身。假設(shè)取 m=1000 ，則哈希函數(shù)分類的標(biāo)準(zhǔn)實(shí)際上就 變成了按照關(guān)鍵字末三位數(shù)分類，這樣最多 1000 類，沖突會(huì)很多。 簡(jiǎn)單的證明：假設(shè) m 是一個(gè)有較多約數(shù)的數(shù)，同時(shí)在數(shù)據(jù)中存在 q 滿足 gcd(m,q)=d 1 ，即 有 m=a*d,q=b*d,則有以下等式： q mod m= q – m* [q div m] =q – m*[b div a] 。也就是說(shuō)， [b div a]的值只有 b+1 種可 能，而 m 是一個(gè)預(yù)先確定的數(shù)。這樣，雖然 mod 運(yùn)算之后 的余數(shù)仍然在 [0， m1]內(nèi)，但是它的取值僅限于等式可能取到的那些值。容易看出， m 的約數(shù)越多，發(fā)生這種余數(shù)分布不均勻的情況就越頻繁，沖突的幾率越 高。記住 “ 素?cái)?shù)是我們的得力助手 ” 數(shù)字分析法 常有這樣的情況：關(guān)鍵碼的位數(shù)比存儲(chǔ)區(qū)域的地址的位數(shù)多，在這種情況下可以對(duì)關(guān)鍵碼的 各位進(jìn)行分析，丟掉分布不均勻的位留下分布均勻的位作為地址。 【 例 2】 對(duì)下列關(guān)鍵碼集合（表中左邊一列）進(jìn)行關(guān)鍵碼到地址的轉(zhuǎn)換，要求用三位地址。丟掉哪 6 位呢？顯然前 3 位 是沒(méi)有任何區(qū)分度，第 5 位 1 太多、第 6 位基本都是 8 和 第 7 位都是 5，這幾位的區(qū)分 度都不好
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1