Jaki algorytm mieszania używa mapowanie słownika Pythona?

Question

Robiłem rozmyślania nad parserem wiersza poleceń i zastanawiałem się, jakiego rodzaju algorytmu hashowego używa python dict?

Sposób, w jaki mam to ustawić, Mam algorytm dopasowywania wzorców, który dopasowuje tokenizowane sekwencje wejściowe za pomocą klucza słownika. Niektóre klucze są stosunkowo długie (długość 5 lub 6 krotności po 6-7 ciągów znaków). Zastanawiałem się, czy istnieje punkt, w którym długie klawisze słownika znacznie zmniejszają wydajność kluczowego wyszukiwania.

Answer 1

Wartość skrótu, której używa, zależy od obiektu, który jest używany jako klucz - każda klasa może zdefiniować własną metodę __hash __(), a wartość zwracana dla konkretnej instancji jest używana w słowniku.

Sam Python zapewnia implementację skrótu dla typów str i tuple. Szybkie spojrzenie na źródło powinno ujawnić dokładny algorytm dla nich.

Mieszanie krotki opiera się na hashach jego zawartości. Algorytm jest zasadniczo ten (uproszczona nieznacznie):

def hash(tuple): 
    mult = 1000003 
    x = 0x345678 
    for index, item in enumerate(tuple): 
     x = ((x^hash(item)) * mult) & (1<<32) 
     mult += (82520 + (len(tuple)-index)*2) 
    return x + 97531 

Na strunach, interpreter także iteracje nad każdej postaci, łącząc je z tym (znowu, nieco uproszczony) Algorytm:

def hash(string): 
    x = string[0] << 7 
    for chr in string[1:]: 
     x = ((1000003 * x)^chr) & (1<<32) 
    return x 

Większym problemem martwić się unikaniem kolizji hash. Colliding hash keys spowoduje przeszukiwanie liniowe, ponieważ słownik próbuje znaleźć miejsce do przechowywania nowego obiektu (jest to obecnie rozpoznawane jako problem bezpieczeństwa, a zachowanie może się zmieniać w nadchodzących wersjach pythona)