algorithm - 通用哈希是否在每次操作完成后再次选择一个新的哈希函数？

Question

我一直在阅读“算法简介”。我想知道通用散列是否从散列函数集合中选择一个新的来进行下一个映射。例如，给定一个空表，以及一系列操作：[插入，插入，搜索，删除，插入，...]，首先，算法从集合中选择一个函数并执行第一个操作，插入。那么，算法是选择新的哈希函数进行第二次操作，插入，还是使用算法开始时选择的函数呢？提前致谢！

Answer 1

不，散列函数不是为每个插入的元素单独选择的——如果是的话，如果有人问你“该元素是否存在于散列表中”，你需要一种方法来知道使用哪个散列函数foo？这将通过必要的确定性算法来完成，因为您不可能在可能的输入和散列函数之间保持随机的一对一映射。这反过来意味着攻击者可以使用该算法的知识来选择最终导致冲突的输入，从而有效地消除通用散列的优势。

因此：在初始化哈希表时，哈希函数是从通用家族中选择的，并且可以（尽管没有必要）在重新哈希发生时更改它——但不是在添加或插入单个元素之后。