在具有良好分布的两个整数之间散列字符串(统一散列)

Question

我试图在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之间的数字？

Answer 1

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的幂,则可以通过位屏蔽和位移来完成.使用此方法时,必须选择散列函数,以便结果在0和n - 1之间具有相当均匀的分布,对于应用程序中可能出现的任何n值.取决于函数,余数对于n的某些值可以是均匀的,例如奇数或素数.

我们可以允许表大小n不是2的幂,并且仍然不必执行任何余数或除法运算,因为这些计算有时是昂贵的.例如,令n显着小于2b.考虑在区间[0,2b-1]上均匀的伪随机数发生器(PRNG)函数P(密钥).区间[0,n-1]上均匀的散列函数是n P(密钥)/ 2b.我们可以用(可能更快的)右移位替换除法:nP(键)>> b.