我正在用 C++ 编写一个通用哈希映射，它使用链接来处理冲突。
假设我有一个包含 11 个存储桶的哈希映射，并且我插入了 8 个项目。哈希函数将其分配如下:
bucket[0] = empty
bucket[1] = 2 elements
bucket[2] = empty
bucket[3] = 1 element
bucket[4] = 1 element
bucket[5] = 3 elements
bucket[6] = empty
bucket[7] = 1 element
bucket[8] = empty
bucket[9] = empty
bucket[10] = empty
计算桶的价差为 5/8 = 0.625。
但是，如何将桶的深度考虑在内来计算价差？
我想知道这一点，因为:
假设我添加了 20 个元素，每个桶有 1 个元素，最后一个桶有 11 个元素。
如果我用简单的方法计算，那么点差将为 1，但这显然不正确! (当然，表格会调整大小以避免这种情况，但我希望能够显示点差)我想使用这些信息来调整哈希函数。
提前致谢!
最佳答案
如果您仅使用它来调整哈希函数本身，则可以计算真正的 measure of statistical dispersion ，例如基尼系数。另一方面，如果你试图让它成为哈希映射本身的一个特性，我会建议不要这样做——计算一个复杂的基准作为“必要调整大小”逻辑的一部分有它自己的性能成本；天真的东西可能更好。
关于c++ - 计算使用链接的哈希映射的哈希函数的传播，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3950360/