數(shù)據(jù)結(jié)構(gòu)散列hashing(文件)
【正文】 33 11 00 .. 55 33 除留余數(shù) 10 .20 22 .42 25 .79 移位折疊 21 .75 65 .10 71 11 分界折疊 22 .97 48 .70 69 .63 91 數(shù)字分析 30 .62 89 .20 12 理論值 10 .50 查找關(guān)鍵字時(shí)所需對桶的平均訪問次數(shù) 從圖中可以看出，鏈地址法優(yōu)于開放定址法；在散列函數(shù)中，用除留余數(shù)法作散列函數(shù)優(yōu)于其它類型的散列函數(shù)，最差的是折疊法。 其中 n為整數(shù) ? 如果 Hi0, 則 Hi= Hi+ m*n。 ? 把字符串的每一段都轉(zhuǎn)換成一個(gè)整數(shù)后，再把各段轉(zhuǎn)換成的整數(shù)加起來。 20210203 ?轉(zhuǎn)換的方法： ? 把字符串從右向左，按一個(gè)固定長度 (例如 4 ) 進(jìn)行分段，必要時(shí)可在最左端添一些空格。 20210203 ? 以上介紹了幾種常用的散列函數(shù) 。取質(zhì)數(shù) p= 23。 20210203 ? 一般當(dāng)關(guān)鍵字的位數(shù)很多 ， 而且關(guān)鍵字每一位上數(shù)字的分布大致比較均勻時(shí) ， 可用這種方法得到散列地址 。 20210203 4. 折疊法 ? 此方法把關(guān)鍵字自左到右分成位數(shù)相等的幾部分，每一部分的位數(shù)應(yīng)與散列表地址位數(shù)相同，只有最后一部分的位數(shù)可以短一些。 因?yàn)閮?nèi) 碼平方數(shù)的中間幾位一般是由標(biāo)識符所有字符決定 ， 所以對不同的標(biāo)識符計(jì)算出的散列地址大多不相同 ， 即使其中有些字符相同 。如果換一個(gè)關(guān)鍵字集合，選擇哪幾位要重新決定。 20210203 2. 數(shù)字分析法 設(shè)有 n個(gè) d位數(shù)，每一位可能有 r種不同的符號。 ? 散列函數(shù)計(jì)算出來的地址應(yīng)能均勻分布在整個(gè) 地址空間中：若 key是從關(guān)鍵字集合中隨機(jī)抽 取的一個(gè)關(guān)鍵字，散列函數(shù)應(yīng)能以同等概率取 0到 m1 中的每一個(gè)值。 哈希表的定義 20210203 ? 散列方法在表項(xiàng)的存儲位置與它的關(guān)鍵字
試題試卷相關(guān)推薦
鄂ICP備17016276號-1