27

frozenset現在、Python の組み込みデータ型に対して定義されているハッシュ関数の背後にあるメカニズムを理解しようとしています。実装は参照用に下部に示されています。私が特に興味を持っているのは、この散乱操作を選択した理由です。

lambda h: (h ^ (h << 16) ^ 89869747) * 3644798167

h各要素のハッシュはどこにありますか。これらがどこから来たか知っている人はいますか？(つまり、これらの数字を選ぶ特別な理由はありましたか?) それとも単に恣意的に選ばれたのでしょうか?

これは、公式の CPython 実装のスニペットです。

static Py_hash_t
frozenset_hash(PyObject *self)
{
    PySetObject *so = (PySetObject *)self;
    Py_uhash_t h, hash = 1927868237UL;
    setentry *entry;
    Py_ssize_t pos = 0;

    if (so->hash != -1)
        return so->hash;

    hash *= (Py_uhash_t)PySet_GET_SIZE(self) + 1;
    while (set_next(so, &pos, &entry)) {
        /* Work to increase the bit dispersion for closely spaced hash
           values.  The is important because some use cases have many
           combinations of a small number of elements with nearby
           hashes so that many distinct combinations collapse to only
           a handful of distinct hash values. */
        h = entry->hash;
        hash ^= (h ^ (h << 16) ^ 89869747UL)  * 3644798167UL;
    }
    hash = hash * 69069U + 907133923UL;
    if (hash == -1)
        hash = 590923713UL;
    so->hash = hash;
    return hash;
}

およびPython での同等の実装:

def _hash(self):
    MAX = sys.maxint
    MASK = 2 * MAX + 1
    n = len(self)
    h = 1927868237 * (n + 1)
    h &= MASK
    for x in self:
        hx = hash(x)
        h ^= (hx ^ (hx << 16) ^ 89869747)  * 3644798167
        h &= MASK
    h = h * 69069 + 907133923
    h &= MASK
    if h > MAX:
        h -= MASK + 1
    if h == -1:
        h = 590923713
    return h
4

3 に答える 3

42

解決されている問題は、Lib/sets.pyの以前のハッシュ アルゴリズムが、多数のグラフ アルゴリズムで発生するデータセットに対して恐ろしいパフォーマンスを示していたことです (ノードはfrozensetsとして表されます)。

# Old-algorithm with bad performance

def _compute_hash(self):
    result = 0
    for elt in self:
        result ^= hash(elt)
    return result

def __hash__(self):
    if self._hashcode is None:
        self._hashcode = self._compute_hash()
    return self._hashcode

パフォーマンスが大幅に向上したため、新しいアルゴリズムが作成されました。以下は、新しいアルゴリズムの重要な部分の概要です。

h ^= (hx ^ (hx << 16) ^ 89869747) * 36447981671)アルゴリズムが可換であるため、xor-equal inが必要です(ハッシュは集合要素が検出される順序に依存しません)。セットには順序付けされていない等値テストがあるため、 のハッシュfrozenset([10, 20])は と同じである必要がありますfrozenset([20, 10])。

2) の xorは、別の興味深いビット パターンを持つランダムに選択された大きな素数を乗算する前に、近くのハッシュ値のシーケンスを分割するために使用される89869747興味深いビット パターンのために選択されました。1010101101101001101101100113644798167

3) xor withhx << 16が含まれていたため、下位ビットが結果に影響を与える可能性が 2 回ありました (その結果、近くのハッシュ値の分散が改善されました)。この中で、CRC アルゴリズムがビットをシャッフルして自分自身に戻す方法に触発されました。

4) 私の記憶が正しければ、特別な定数は69069 だけです。これには、線形合同乱数ジェネレーターの世界からの歴史がありました。参照については、 https://www.google.com/search?q=69069+rngを参照してください。

5) 計算の最終ステップhash = hash * 69069U + 907133923ULが追加され、ネストされたfrozensetのケースを処理し、アルゴリズムを他のオブジェクト(文字列、タプル、intなど)のハッシュアルゴリズムと直交するパターンで分散させました。

6) 他の定数のほとんどはランダムに選択された大きな素数です。

ハッシュ アルゴリズムの神のインスピレーションを主張したいのですが、現実には、パフォーマンスの悪いデータセットを大量に取得し、それらのハッシュが分散しない理由を分析し、衝突の統計が恥ずかしくなくなるまでアルゴリズムをいじりました。

たとえば、拡散の少ないアルゴリズムで失敗した Lib/test/test_set.py の有効性テストは次のとおりです。

def test_hash_effectiveness(self):
    n = 13
    hashvalues = set()
    addhashvalue = hashvalues.add
    elemmasks = [(i+1, 1<<i) for i in range(n)]
    for i in xrange(2**n):
        addhashvalue(hash(frozenset([e for e, m in elemmasks if m&i])))
    self.assertEqual(len(hashvalues), 2**n)

その他の失敗した例には、文字列のパワーセットと小さな整数範囲、およびテスト スイートのグラフ アルゴリズムが含まれていました。

于 2014-01-05T08:13:47.670 に答える