Man*_*uel 4 algorithm hashtable data-structures
我知道有关创建哈希码,冲突,.GetHashCode和.Equals等之间的关系.
我不太明白的是如何使用32位哈希值来获得~O(1)查找.如果你有一个足够大的数组来分配32位数字中的所有可能性,那么你确实得到了~O(1)但这会浪费内存.
我的猜测是,Hashtable类内部创建一个小数组(例如1K项),然后将32位数重新转换为3位数,并将其用作查找.当元素数量达到某个阈值(比如说75%)时,它会将数组扩展为10K项目,并将内部哈希值重新计算为4位数,当然基于32位哈希值.
顺便说一句,我在这里使用~O(1)来解释可能的碰撞及其分辨率.
我是否有正确的要点,或者我是否完全脱离了标记？
我的猜测是,Hashtable类内部创建一个小数组(例如1K项),然后将32位数重新转换为3位数,并将其用作查找.
这正是发生的情况,除了表的容量(箱数)通常设置为2的幂或素数.然后以该数字为模取取哈希码,以找到要插入项目的bin.当容量是2的幂时,模数运算变为简单的位掩码运算.
当元素数量达到一定阈值时(比如说75%)
如果您指的是Java Hashtable实现,那么是的.这称为负载系数.其他实现可以使用2/3而不是3/4.
它会将数组扩展为类似10K的项目
在大多数实现中,容量不会增加十倍而是增加一倍(对于两倍大小的哈希表)或者乘以大约1.5 +到下一个素数的距离.