我正在用 C++ 编写通用 HashMap ，它使用链接来处理冲突。
假设我有一个包含 11 个桶的 HashMap ，并且我插入了 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 ，例如基尼系数。另一方面，如果您试图使它成为 HashMap 本身的一个特性，我建议您不要这样做——计算一个复杂的基准作为“是否需要调整大小”逻辑的一部分有其自身的性能成本；一些天真的东西可能更好。
关于c++ - 计算使用链接的散列映射的散列函数的散布，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3950360/