9

我试图在 0 和非常低的 n 之间散列一些字符串，以便为每个用户提供一种颜色。

这是我的（工作）代码：

 function nameToColor(name) {
            var colors = ['red', 'blue', 'green', 'purple', 'orange', 'darkred', 'darkblue', 'darkgreen', 'cadetblue', 'darkpurple'];
            var hash = hashStr(name);
            var index = hash % colors.length;
            return colors[index];
        }

        //djb2 hash
        function hashStr(str) {
            var hash = 5381;
            for (var i = 0; i < str.length; i++) {
                var charCode = str.charCodeAt(i);
                hash = ((hash << 5) + hash) + charCode; /* hash * 33 + c */
            }
            return hash;    
        }

不幸的是，低数字被大量过度代表。

问题：

如何编写一个确定性的 javascript 函数，该函数将任何字符串作为参数并返回一个良好（尽可能均匀）分布在 0 和 n 之间的数字？

4

3 回答 3

9

Hogan 在评论中给出了javascript 中几个哈希实现的链接。事实证明，最简单的最合适：

function nameToColor(name) {
                var colors = ['red', 'blue', 'green', 'purple', 'orange', 'darkred', 'darkblue', 'darkgreen', 'cadetblue', 'darkpurple'];
                var hash = hashStr(name);
                var index = hash % colors.length;
                return colors[index];
        }

        //very simple hash
        function hashStr(str) {
            var hash = 0;
            for (var i = 0; i < str.length; i++) {
                var charCode = str.charCodeAt(i);
                hash += charCode;
            }
            return hash;
        }

我认为它运作良好，因为它只使用保持模数不变的加法（无移位或乘法），因此保留了初始分布质量。

我也在维基百科上找到了这个，但不必使用它：

在许多应用程序中，程序的每次运行的哈希值范围可能不同，或者可能随着同一运行而改变（例如，当需要扩展哈希表时）。在这些情况下，需要一个带有两个参数的散列函数——输入数据 z 和允许的散列值的数量 n。

一个常见的解决方案是计算一个范围非常大的固定散列函数（例如，0 到 232 - 1），将结果除以 n，然后使用除法的余数。如果 n 本身是 2 的幂，这可以通过位掩码和位移来完成。当使用这种方法时，必须选择散列函数，以便对于应用程序中可能出现的任何 n 值，结果在 0 和 n - 1 之间具有相当均匀的分布。取决于函数，余数可能仅对于某些 n 值是一致的，例如奇数或素数。

我们可以允许表大小 n 不是 2 的幂，并且仍然不必执行任何余数或除法运算，因为这些计算有时成本很高。例如，让 n 明显小于 2b。考虑一个伪随机数生成器 (PRNG) 函数 P(key)，它在区间 [0, 2b - 1] 上是一致的。区间 [0, n-1] 上的均匀散列函数是 n P(key)/2b。我们可以用（可能更快的）右位移来代替除法：nP(key)>> b。

于 2013-06-13T12:33:15.000 回答
1

以下由 Brian White 编写的哈希函数非常通用，可以使用任何类型的输入（包括字符串），附带简单的示例，并且是为 Javascript node.js 编写的。

https://npmjs.org/package/xxhash

希望这可以帮助

于 2013-06-13T12:52:26.637 回答
0

这是上面代码的变体：

function hashValue(theString,size){
  var sum = 0;
  for(i=0;i<theString.length;i++){
    sum += theString[i].charCodeAt(0) * 3;
  }
  return sum % size;
}

只需传递一个字符串和您希望它具有的大小，例如，如果您希望它返回数字 0 到 36，则为 36。 * 3 可以添加变化，但可以是您想要的任何数字。我从这里改变了这个想法（哈希函数可以返回一个基于字符串的整数范围）由 M_callens

于 2021-10-04T22:36:08.150 回答