資料結構›Ch8 雜湊
第 3 題/共 37 題
◀ DS 3/37
3. Double Hashing、開放定址法
#DS-08-003易Double Hashing開放定址法

Assume that there are KK possible keys {1,2,…,K}\{1,2,\dots,K\} and mm hash table slots {0,1,…,m−1}\{0,1,\dots,m-1\} with m>1m>1. In double hashing, the probe sequence is h(k,i)=(h1(k)+i⋅h2(k))mod  mh(k,i) = (h_1(k) + i \cdot h_2(k)) \mod m. For a fixed key kk, we want the sequence h(k,0),h(k,1),…h(k,0), h(k,1), \dots to visit all mm 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 kk)?

📄 台大115
跳轉到第題
▤完整推導請見《WH 資工筆記 · 資料結構》Ch8 雜湊
本章題號 · 1–20 / 37