Hashtable- Rehashing

Question

有人告诉我,Hashtable在.NET使用中重复以减少/避免碰撞.

IE浏览器."Rehasing的工作原理如下:假设我们有一组散列不同的函数,H1 ... Hn,并且当从散列表中插入或检索项目时,最初使用H1散列函数.如果这导致碰撞,则尝试使用H2,然后再尝试Hn,以避免在Hashtable中发生碰撞."

假设:我们有一个哈希表,其中n(其中n <Infinity)元素的渐近时间复杂度为o(1); 我们(CLR)在应用一些散列函数(Hn-1散列函数,其中n> 1)时实现了这一点.

问题:当我们寻找(检索)任何元素时(如果使用了不同的散列函数),有人可以解释一下CLR map如何键入哈希码？CLR如何跟踪(如果是)任何活动对象(哈希表)的哈希函数？

提前致谢

Answer 1

随机选择散列函数称为通用散列方法.AFAIK每个初始化过程选择一次哈希函数,因此当在单个哈希表的范围内使用多个哈希函数时,这不是一个真实的情况.

编辑:更多细节

回到家里,打开"算法简介"T. Cormen预定并在11.3.3通用散列部分中找到:

通用散列背后的主要思想是在执行开始时从精心设计的函数类中随机选择散列函数

您可以在此处的Google图书网站预览图书,以了解更多信息