我一直在看《算法导论》。我想知道通用哈希是否从哈希函数集合中选择一个新的来进行下一个映射。例如,给定一个空表和一系列操作:[插入、插入、搜索、删除、插入……],首先,算法从集合中选择一个函数并执行第一个操作,即插入。那么,算法是选择一个新的哈希函数来做第二个操作,插入,还是使用算法开始时选择的函数?提前致谢!
最佳答案
不,没有为每个插入的元素单独选择散列函数——如果是这样,如果有人问你“元素 foo
存在于哈希表中”?这将不可避免地使用确定性算法来完成,因为您不可能在可能的输入和哈希函数之间保持随机的一对一映射。 这反过来意味着攻击者可以利用该算法的知识来选择最终导致冲突的输入,从而有效地抵消通用哈希的优势。
因此:哈希函数是在初始化哈希表时从通用系列中选择的,并且可以(尽管不是必须)在重新哈希发生时更改它——但不能在添加或插入单个元素之后更改它。
关于algorithm - universal hashing是不是每次操作完成后都会重新选择一个新的hash函数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18205106/