假设采用双重散列来解决冲突，即所用的散列函数为 。试证明：如果对某个关键字k，m和 有最大公约数 ，则在对关键字k的一次不成功查找中，要返回槽 之前，要检查散列表中第（1/d）1/d的元素。于是，当d=1时，m与 互素，查找操作可能要检查整个散列表。（提示：见第31章）
英文版：
Suppose that we use double hashing to resolve collisions - that is, we use the hash function .Show that if m and have greatest common divisor for some key k, then an unsuccessful search for key k examines (1/d)th of the hash table before returning to slot .Thus, when d = 1, so that m and are relatively prime, the search may examine the entire hash table.(Hint: See Chapter 31.)
题本身没太大难度，写在这里主要是原中文版的关于(1/d)th的翻译有点令人费解，已进行修正
首先m与互素时，在连续的m步中能够遍历0, 1, ... m-1
若不能则存在 i < m，使得 , 可推出 ，结合m与互素，进一步推出 ，但i < m，上一步明显无法成立，于是原命题得证（原题后半部分）
拓展一下，d>1时，上述 m与 均乘以d作为新的 m和，但此时仍仅能按原0, d, ... d(m-1)进行遍历（以d为步长），可知原题前半部分成立（感觉自己写的跟屎一样。。。）
本文发布于:2024-01-28 15:12:59，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/17064259828310.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
