數(shù)據(jù)結構散列hashing-免費閱讀
【正文】 di分別有三種取法： (1) di=1,2,3,… ,m1 線性探測再散列 (2) di=12,12,22,22,… , k2, k2,(k≤m/ 2) —— 二次探測再散列 特別注意：要求表長 m為形如 4*j+3的素數(shù) (3) di=偽隨機數(shù)序列 ， 偽隨機探測再散列 說明： ? 如果 Him， 則 Hi= Hi m*n。 ? 在應用平方取中法時 ， 若關鍵字不是整數(shù)而是字符串時 ， 可以把每個字符串轉換成整數(shù) 。 ? 示例：有一個關鍵字 key = 962148，散列表大小 m = 25，即 HT[25]。 如果 r = 3， 所取得的散列地址參看 圖的最右一列 。 20210203 9 4 2 1 4 8 9 4 1 2 6 9 9 4 0 5 2 7 9 4 1 6 3 0 9 4 1 8 0 5 9 4 1 5 5 8 9 4 2 0 4 7 9 4 0 0 0 1 ① ② ③ ④ ⑤ ⑥ 數(shù)字分析法僅適用于事先明確知道表中所有關鍵字每一位數(shù)值的分布情況，它完全依賴于關鍵字集合。 20210203 構造散列函數(shù)時的幾點要求： ? 散列函數(shù)的定義域必須包括需要存儲的全部關 鍵碼，如果散列表允許有 m個 地址時 ,其值域必 須在 0 到 m1 之間。20210203 散列 (Hashing) ? 在線性表、樹結構中查找紀錄是通過與關鍵 字的 “ 比較 ” 完成的。 ? 散列函數(shù)計算出來的地址應能均勻分布在整個 地址空間中：若 key是從關鍵字集合中隨機抽 取的一個關鍵字，散列函數(shù)應能以同等概率取 0到 m1 中的每一個值。如果換一個關鍵字集合，選擇哪幾位要重新決定。 2021020
試題試卷相關推薦
鄂ICP備17016276號-1