您好, 欢迎来到 !    登录 | 注册 | | 设为首页 | 收藏本站

为什么散列表的大小127(素数)比128好?

为什么散列表的大小127(素数)比128好?

所有数字(经过散列处理)仍然仍然是127的k的p个最低位。

那是错误的(或者我误会了..)。k % 127取决于k的所有位。k % 128仅取决于最低的7位。

编辑:

如果您的理想分布在1到10,000之间。10,000 % 12710,000 % 128两者都将在一个优秀的小分布开启此。所有存储桶将包含10,000 / 128 = 78(或79)个项目。

如果您的分布在1到10,000之间是有偏差的,因为{x,2x,3x,..}发生的频率更高。然后,如该答案中所述,素数大小将提供更好得多的分布。(除非x恰好是该素数。)

因此, 低位的分布足够好,则切断高位(使用大小为128)就没有问题。但是,使用真实数据和错误设计的真实哈希函数,您将需要这些高位。

其他 2022/1/1 18:15:23 有445人围观

撰写回答


你尚未登录,登录后可以

和开发者交流问题的细节

关注并接收问题和回答的更新提醒

参与内容的编辑和改进,让解决方法与时俱进

请先登录

推荐问题


联系我
置顶