javascript - 単純な一方向ハッシュの作成

Question

任意の 9 桁の整数を別の (一意の) 9 桁の整数にマップする標準的なハッシュ関数/メソッドはありますか?

ハッシュは衝突してはならないため、すべての出力1 ≤ y < 10^9は の 1 つの入力値のみからマッピングする必要があります1 ≤ x < 10^9。

Answer 1

約 30 ビットしかない衝突しないハッシュ関数が必要です。これは、ハッシュ関数にとって難しい注文になるでしょう。実際に必要なのは、ハッシュなどの疑似ランダム関数ではなく、疑似ランダム順列です。

これには暗号化関数を使用できますが、明らかに鍵を秘密にしておく必要があります。さらに、暗号化は通常、ビットを入力と出力として機能10^9し、正確な数のビットを使用することはほとんどありません。したがって、そのようなオプションを使用する場合は、フォーマット保持暗号化を使用する必要がある場合があります。

グループ 0..10^9-1 内の PRP である他の関数を使用することもできます (値を 1 で減らした後)。オリジナルに。例としては、10^9-1 を法として 10^9-1 と互いに素な数の乗算があります。

Answer 2

これは私が思いつくことができるものです:

var used = {};

var hash = function (num) {
    num = md5(num);
    if (used[num] !== undefined) {
        return used[num];
    } else {
        var newNum;
        do {
            newNum = Math.floor(Math.random() * 1000000000) + 1;
        } while (contains(newNum))
        used[num] = newNum;
        return newNum;
    }
};

var contains = function (num) {
    for (var i in used) {
        if (used[i] === num) {
            return true;
        }
    }
    return false;
};

var md5 = function (num) {
    //method that return an md5 (or any other) hash
};

do..whileただし、乱数を生成して既に生成された数値と比較するため、多くの異なる数値をハッシュしようとすると問題が発生することに注意してください。すでに多くの数値を生成している場合、残りの数値を見つける可能性はますます低くなります。