資料結構›Ch8 雜湊第 3 題/共 37 題
3. Double Hashing、開放定址法
#DS-08-003易Double Hashing開放定址法
Assume that there are possible keys and hash table slots with . In double hashing, the probe sequence is . For a fixed key , we want the sequence to visit all table slots before repeating, so that insertion succeeds whenever the table is not full. Which of the following conditions is necessary and sufficient for this property (for that key )?
參考答案與解析
答案 (C): 是雙重雜湊探測序列能走遍所有 m 個槽位、不重複、不提前循環的充分必要條件(因為序列本質上是在模 m 的加法群中,以步長 走訪,只有步長與 m 互質時才能生成整個群)。
📄 台大115
▤完整推導請見《WH 資工筆記 · 資料結構》Ch8 雜湊