MAD方法压缩功能 [英] MAD method compression function

问题描述

我在一次旧考试中遇到了以下问题.我的回答有点简短和不足.我可以研究的任何其他想法或被我忽略的原因都很好.谢谢

I ran across the question below in an old exam. My answers just feels a bit short and inadequate. Any extra ideas I can look into or reasons I have overlooked would be great. Thanx

请考虑MAD方法压缩功能，将具有哈希码i的对象映射到具有6000个元素的存储桶数组的元素[(3i + 7)mod9027] mod6000.解释为什么这是压缩功能的较差选择，以及如何对其进行改进.

Consider the MAD method compression function, mapping an object with hash code i to element [(3i + 7)mod9027]mod6000 of the 6000-element bucket array. Explain why this is a poor choice of compression function, and how it could be improved.

我基本上只是说，可以通过将p(或9027)的值更改为质数并为a(或3)选择其他常数来改善此功能.

I basically just say that the function could be improved by changing the value for p (or 9027) to an prime number and choosing an other constant for a (or 3) could also help.

推荐答案

Rup的注释本质上是正确的答案. 3和9027都可被3整除，因此3i + 7仅映射到0-9026范围的1/3.然后，映射模块6000将值的2/3映射到下半部分.因此，存储桶1将包含大约1/1500的值(如果我对数学正确无误)，而不是您想要的1/6000.桶0将为空.

Rup's comment is essentially the correct answer. 3 and 9027 are both divisible by 3, so 3i + 7 maps onto only 1/3 of the range 0-9026. Then the mapping mod 6000 maps 2/3 of the values to the lower half. So bucket 1 will contain roughly 1/1500 of the values [if I've done the math right] rather than the 1/6000 you would want. Bucket 0 will be empty.

这篇关于MAD方法压缩功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！