1

次のハッシュ関数を使用しています

function hash_djb2($str){
    $hash = 5381;
    $length = strlen($str);

    for($i = 0; $i < $length; $i++) {
        $hash = (($hash << 5) + $hash) + ord(strtolower($str[$i])) - 96;        
    }
    return $hash;
}

ハッシュテーブルのバケット数はどこにあるのでしょう$hashか?$hash % $numBuckets$numBuckets

前者は非常に大きな数を返し、ハッシュの衝突を不可能にしますが、後者は 0 から$numBuckets-1 の間の値のみを返しますが、ハッシュの衝突は可能にします

4

1 に答える 1

2

の出力はhash_djb2()整数値のスペクトル全体をカバーする必要があるため、ハッシュチェーンを実装している場合 (つまり、バケットの数が制限されている場合)、モジュロを使用して範囲を短縮する必要があります。

ところで、ハッシュ衝突のリスクは、関数出力のみを使用することにした場合にのみ減少します。範囲を小さくすると、明らかにそのリスクが増加します。複数のアイテムを同じハッシュ値で保存できるようにすることで、そのリスクを管理することになっています。

于 2013-02-20T07:18:21.590 に答える