将整数映射到整个范围

Question

我使用哈希表（DotNET Dictionary 对象）作为稀疏二维数据集的一部分。哈希表中的大多数条目将靠近在一起。我最终可能会得到 100 ~ 10,000 个条目，所有条目都聚集在接近于零的位置。我读到，当散列分布在整个整数（32 位）范围内时，散列表的性能会更好。

有没有一种廉价的方法可以将连续的整数以 1:1 的方式映射到截然不同的值上？我不必将它们映射回来，这纯粹是单向的事情。

Answer 1

也许我误解了你的意思，但字典已经对你的整数进行了哈希处理。不需要对它们进行预先哈希处理。为什么不尝试默认实现并看看它是如何进行的，而不是尝试进行预优化，这很可能是毫无意义的。

Answer 2

不要使用 Integer，而是编写一个继承 Integer 的类，并重写 GetHashCode 函数。这样你就不需要做任何事情，只需创建这个函数！

我能想到的均匀分布值的最简单方法是执行以下操作：

public class MyInteger:Integer
{
    public override int GetHashCode()
    {
       unchecked
       {
           return (int)Math.Pow(this,this);
       }
    }
}

良好且均匀地分布，同时将工作量降至最低。

Answer 3

如果您知道键集的最大值 (kmax)，则可以按常数因子（乘数）进行扩展，例如乘以固定素数，使乘积保持在最大整数大小 (2^31 - 1) 以下：

即最接近(2^30) / kmax的素数

注意：确保使用的素数与哈希表中的桶数不同。

这是另一个解决方案：自从.NET Random 类将为相同的种子生成相同的值，您可以使用它来分发传入的密钥。