create - Python frozenset hashing algoritmo/implementación

python set

Question

Actualmente estoy tratando de entender el mecanismo detrás de la función hash definida para el tipo de datos frozenset incorporado de Python. La implementación se muestra en la parte inferior para referencia. Lo que me interesa en particular es la justificación de la elección de esta operación de dispersión:

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

donde h es el hash de cada elemento. ¿Alguien sabe de dónde vienen estos? (Es decir, ¿hubo alguna razón en particular para elegir estos números?) ¿O simplemente fueron elegidos arbitrariamente?

Aquí está el fragmento de la implementación oficial de 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;
}

y una implementación equivalente en 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

Answer 1

A menos que Raymond Hettinger (el autor del código) se involucre, nunca lo sabremos con seguridad ;-) Pero generalmente hay menos "ciencia" en estas cosas de lo que podrías esperar: tomas algunos principios generales, un conjunto de pruebas, y tocas el Constantes casi arbitrariamente hasta que los resultados se vean "suficientemente buenos".

Algunos principios generales "obviamente" funcionan aquí:

1. Para obtener la rápida "dispersión de bits" deseada, desea multiplicar por un entero grande. Como el resultado de hash de CPython tiene que caber en 32 bits en muchas plataformas, un entero que requiere 32 bits es el mejor para esto. Y, de hecho, (3644798167).bit_length() == 32 .

2. Para evitar perder sistemáticamente el (los) bit (s) de orden inferior, desea multiplicar por un entero impar. 3644798167 es impar.

3. De manera más general, para evitar la combinación de patrones en los hashes de entrada, se debe multiplicar por un primo. Y 3644798167 es primo.

4. Y también desea un multiplicador cuya representación binaria no tenga patrones de repetición obvios. bin(3644798167) == ''0b11011001001111110011010011010111'' . Eso es bastante desordenado, lo cual es bueno ;-)

Las otras constantes me parecen completamente arbitrarias. los

if h == -1:
    h = 590923713

la parte es necesaria por otra razón: internamente, CPython toma un valor de retorno de -1 de una función C de valor entero en el sentido de que "se debe generar una excepción"; Es decir, es un error de retorno. Por lo tanto, nunca verá un código hash de -1 para ningún objeto en CPython. El valor devuelto en lugar de -1 es completamente arbitrario, solo necesita ser el mismo valor (en lugar de -1) cada vez.

EDITAR: jugando

No sé qué Raymond solía probar esto. Esto es lo que habría usado: mirar las estadísticas de hash para todos los subconjuntos de un conjunto de enteros consecutivos. Esos son problemáticos porque el hash(i) == i para una gran cantidad de enteros i .

>>> all(hash(i) == i for i in range(1000000))
True

El simple hecho de xor''ing hashes producirá una cancelación masiva en entradas como esa.

Así que aquí hay una pequeña función para generar todos los subconjuntos, y otra para hacer un xor simple en todos los códigos hash:

def hashxor(xs):
    h = 0
    for x in xs:
        h ^= hash(x)
    return h

def genpowerset(xs):
    from itertools import combinations
    for length in range(len(xs) + 1):
        for t in combinations(xs, length):
            yield t

A continuación, un controlador y una pequeña función para mostrar las estadísticas de colisión:

def show_stats(d):
    total = sum(d.values())
    print "total", total, "unique hashes", len(d), /
          "collisions", total - len(d)

def drive(n, hasher=hashxor):
    from collections import defaultdict
    d = defaultdict(int)

    for t in genpowerset(range(n)):
        d[hasher(t)] += 1
    show_stats(d)

Usar el hacendado tan simple es desastroso:

>> drive(20)
total 1048576 unique hashes 32 collisions 1048544

¡Ay! OTOH, utilizando el _hash() diseñado para frozensets hace un trabajo perfecto en este caso:

>>> drive(20, _hash)
total 1048576 unique hashes 1048576 collisions 0

Luego puedes jugar con eso para ver lo que hace, y no hace, una diferencia real en _hash() . Por ejemplo, todavía hace un trabajo perfecto en estas entradas si

    h = h * 69069 + 907133923

es removido. Y no tengo idea de por qué esa línea está ahí. De manera similar, continúa haciendo un trabajo perfecto en estas entradas si se ^ 89869747 el ^ 89869747 en el bucle interno, tampoco sé por qué está ahí. Y la inicialización se puede cambiar desde:

    h = 1927868237 * (n + 1)

a:

    h = n

sin daño aquí también. Todo lo contrario a lo que esperaba: es la constante multiplicativa en el bucle interno lo que es crucial, por las razones ya explicadas. Por ejemplo, agregue 1 a él (use 3644798168) y luego ya no es primo o impar, y las estadísticas se degradan a:

total 1048576 unique hashes 851968 collisions 196608

Todavía bastante utilizable, pero definitivamente peor. Cámbialo a una prima pequeña, como 13, y es peor:

total 1048576 unique hashes 483968 collisions 564608

Use un multiplicador con un patrón binario obvio, como 0b01010101010101010101010101010101 , y peor aún:

total 1048576 unique hashes 163104 collisions 885472

¡Jugar! Estas cosas son divertidas :-)

Answer 2

El problema que se está resolviendo es que el algoritmo hash anterior en Lib / sets.py tuvo un rendimiento horrible en los conjuntos de datos que surgen en una serie de algoritmos gráficos (donde los nodos se representan como 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

Se creó un nuevo algoritmo porque tenía un rendimiento mucho mejor. Aquí hay una visión general de las partes salientes del nuevo algoritmo:

1) El xor-igual en h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167 es necesario para que el algoritmo sea commutative (el hash no depende del orden en que se encuentran los elementos establecidos). Dado que los conjuntos tienen una prueba de igualdad no ordenada, el hash para frozenset([10, 20]) debe ser el mismo que para frozenset([20, 10]) .

2) Se 89869747 xor con 89869747 por su interesante patrón de bits 101010110110100110110110011 que se usa para dividir secuencias de valores hash cercanos antes de multiplicar por 3644798167 , un primo grande elegido al azar con otro interesante patrón de bits.

3) Se incluyó el xor con hx << 16 para que los bits más bajos tuvieran dos posibilidades de afectar el resultado (lo que resulta en una mejor dispersión de los valores de hash cercanos). En esto, me inspiré en cómo los algoritmos CRC se barajaban los bits de nuevo a sí mismos.

4) Si recuerdo correctamente, la única de las constantes que es especial es 69069 . Tenía algo de historia del mundo de los generadores de números aleatorios lineales congruentes . Consulte https://www.google.com/search?q=69069+rng para ver algunas referencias.

5) Se agregó el paso final de calcular hash = hash * 69069U + 907133923UL para manejar casos con conjuntos de imágenes anidados y hacer que el algoritmo se disperse en un patrón ortogonal a los algoritmos de hash para otros objetos (cuerdas, tuplas, pies, etc.).

6) La mayoría de las otras constantes fueron números primos grandes elegidos al azar.

Aunque me gustaría reclamar la inspiración divina para el algoritmo hash, la realidad era que tomé un montón de conjuntos de datos con mal rendimiento, analicé por qué no se estaban dispersando sus hashes, y luego jugué con el algoritmo hasta que las estadísticas de colisión dejaron de ser tan embarazosas.

Por ejemplo, aquí hay una prueba de eficacia de Lib / test / test_set.py que falló para algoritmos con menos difusión:

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)

Otros ejemplos fallidos incluyeron conjuntos de cadenas y rangos de enteros pequeños, así como los algoritmos de gráficos en el conjunto de pruebas: vea TestGraphs.test_cuboctahedron y TestGraphs.test_cube en Lib / test / test_set.py.

Answer 3

En

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

El entero multiplicativo es un primo grande para reducir las colisiones. Esto es especialmente relevante ya que la operación está bajo módulo.

El resto es probablemente arbitrario; No veo ninguna razón para que el 89869747 sea ​​específico. El uso más importante que obtendrías es aumentar hashes de números pequeños (la mayoría de los enteros hash para ellos mismos). Esto evita colisiones altas para conjuntos de enteros pequeños.

Eso es todo lo que puedo pensar. ¿Para qué necesitas esto?