9

ユーザーごとに 1 つの色を与えるために、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;    
        }

残念ながら、低い数値は非常に過剰に表現されています。

質問：

任意の文字列を引数として取り、0 から n までの数値を適切な (できるだけ均一な) 分布で返す決定論的な JavaScript 関数を作成するにはどうすればよいですか?

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 という 2 つのパラメーターを取るハッシュ関数が必要です。

一般的な解決策は、非常に大きな範囲 (0 から 232 - 1 など) の固定ハッシュ関数を計算し、結果を n で除算し、除算の余りを使用することです。n 自体が 2 の累乗である場合、これはビット マスキングとビット シフトによって行うことができます。このアプローチを使用する場合、アプリケーションで発生する可能性のある n の値に対して、結果が 0 と n − 1 の間でかなり均一に分布するように、ハッシュ関数を選択する必要があります。関数によっては、奇数や素数など、n の特定の値に対してのみ剰余が一様になる場合があります。

テーブル サイズ n が 2 の累乗にならないようにすることもできますが、これらの計算にはコストがかかる場合があるため、剰余または除算を実行する必要はありません。たとえば、n を 2b より大幅に小さくします。区間 [0, 2b − 1] で一様な疑似乱数発生器 (PRNG) 関数 P(key) を考えます。区間 [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 に答える