Wbudowana funkcja hash () w języku Python

83

Windows XP, Python 2.5:

hash('http://stackoverflow.com') Result: 1934711907

Google App Engine ( http://shell.appspot.com/ ):

hash('http://stackoverflow.com') Result: -5768830964305142685

Dlaczego? Jak mogę skorzystać z funkcji skrótu, która da mi te same wyniki na różnych platformach (Windows, Linux, Mac)?

Denis T.
źródło
14
jest to spowodowane faktem, że Twój winxp jest platformą 32-bitową, podczas gdy Google jest 64-bitowy
Tzury Bar Yochay

Odpowiedzi:

57

Użyj hashlib, który hash() został zaprojektowany do :

szybko porównuj klucze słownika podczas wyszukiwania w słowniku

i dlatego nie gwarantuje, że będzie taki sam we wszystkich implementacjach Pythona.

SilentGhost
źródło
5
Czy funkcje skrótu nie są hashlibnieco powolne do użytku niekryptograficznego?
Brandon Rhodes
8
W rzeczywistości są bardzo powolne w porównaniu do funkcji skrótu ogólnego przeznaczenia, takich jak Jenkins, Bernstein, FNV, MurmurHash i wiele innych. Jeśli chcesz stworzyć własną strukturę przypominającą tabelę skrótów, proponuję zajrzeć na uthash.h uthash.sourceforge.net
lericson
46
Benchmarki: hash95 ns, binascii.crc32570 ns, hashlib.md5.digest()1,42 us, murmur.string_hash234 ns
temoto
hashużywa nowej, losowo generowanej wartości salt z każdą sesją Pythona. Więc będzie się zmieniać między sesjami Pythona.
płyty grzejne
89

Jak stwierdzono w dokumentacji, wbudowana funkcja hash () nie jest przeznaczona do przechowywania wynikowych skrótów gdzieś na zewnątrz. Służy do dostarczania wartości skrótu obiektu, przechowywania ich w słownikach i tak dalej. Jest to również specyficzne dla implementacji (GAE używa zmodyfikowanej wersji Pythona). Sprawdzić:

>>> class Foo:
...     pass
... 
>>> a = Foo()
>>> b = Foo()
>>> hash(a), hash(b)
(-1210747828, -1210747892)

Jak widać, są one różne, ponieważ hash () używa __hash__metody obiektu zamiast „normalnych” algorytmów haszujących, takich jak SHA.

Biorąc pod uwagę powyższe, racjonalnym wyborem jest użycie modułu hashlib .

Mike Hordecki
źródło
Dziękuję Ci! Przyszedłem tutaj, zastanawiając się, dlaczego zawsze otrzymuję różne wartości skrótu dla identycznych obiektów, co skutkuje nieoczekiwanym zachowaniem z dyktami (które indeksują przez hash + typ zamiast sprawdzania równości). Szybkim sposobem na wygenerowanie własnego int hash z hashlib.md5 jest int(hashlib.md5(repr(self)).hexdigest(), 16)(zakładając, że self.__repr__zostały zdefiniowane jako identyczne obiekty iff są identyczne). Jeśli 32 bajty są zbyt długie, możesz oczywiście zmniejszyć rozmiar, przecinając ciąg szesnastkowy przed konwersją.
Alan Plum
1
Po drugie, jeśli __repr__jest wystarczająco unikalny, możesz po prostu użyć str.__hash__(tj. hash(repr(self))), Ponieważ dykty nie mieszają nierównych obiektów z tym samym hashem. Działa to tylko wtedy, gdy obiekt jest na tyle trywialny, że repr może oczywiście reprezentować tożsamość.
Alan Plum
A więc w twoim przykładzie z dwoma obiektami ai bjak mogę użyć modułu hashlib, aby zobaczyć, że obiekty są identyczne?
Garrett,
32

Odpowiedź nie jest żadnym zaskoczeniem: w rzeczywistości

In [1]: -5768830964305142685L & 0xffffffff
Out[1]: 1934711907L

więc jeśli chcesz uzyskać niezawodne odpowiedzi na łańcuchach ASCII , po prostu pobierz niższe 32 bity jako uint. Funkcja skrótu dla ciągów znaków jest 32-bitowa i prawie przenośna.

Z drugiej strony nie możesz w ogóle polegać na uzyskaniu hash()dowolnego obiektu, dla którego nie zdefiniowałeś jawnie __hash__metody jako niezmiennej.

W przypadku ciągów ASCII działa tylko dlatego, że hash jest obliczany na podstawie pojedynczych znaków tworzących ciąg, jak poniżej:

class string:
    def __hash__(self):
        if not self:
            return 0 # empty
        value = ord(self[0]) << 7
        for char in self:
            value = c_mul(1000003, value) ^ ord(char)
        value = value ^ len(self)
        if value == -1:
            value = -2
        return value

gdzie c_mulfunkcją jest mnożenie „cykliczne” (bez przepełnienia) jak w C.

przepisany
źródło
18

Większość odpowiedzi sugeruje, że dzieje się tak z powodu różnych platform, ale to nie wszystko. Z dokumentacjiobject.__hash__(self) :

Domyślnie __hash__()wartości str, bytesa datetimeobiekty są „solone” z nieprzewidywalnym wartości losowej. Chociaż pozostają stałe w ramach pojedynczego procesu Pythona, nie można ich przewidzieć między powtarzającymi się wywołaniami Pythona.

Ma to na celu zapewnienie ochrony przed atakiem typu „odmowa usługi” spowodowanym przez starannie dobrane dane wejściowe, które wykorzystują najgorszą wydajność wstawiania dyktowania, złożoność O (n²). Szczegółowe informacje można znaleźć pod adresem http://www.ocert.org/advisories/ocert-2011-003.html .

Zmiana wartości hash wpływa na kolejność iteracji dicts, sets i innych odwzorowań. Python nigdy nie udzielił gwarancji co do tej kolejności (i zwykle różni się ona między wersjami 32-bitowymi i 64-bitowymi).

Nawet uruchomienie na tej samej maszynie da różne wyniki w różnych wywołaniach:

$ python -c "print(hash('http://stackoverflow.com'))"
-3455286212422042986
$ python -c "print(hash('http://stackoverflow.com'))"
-6940441840934557333

Podczas:

$ python -c "print(hash((1,2,3)))"
2528502973977326415
$ python -c "print(hash((1,2,3)))"
2528502973977326415

Zobacz także zmienną środowiskową PYTHONHASHSEED:

Jeśli zmienna ta nie jest ustawiony lub ustawiony na randomwartość losową służy do materiału siewnego mieszań o str, bytesi datetimeprzedmioty.

Jeśli PYTHONHASHSEEDjest ustawiona na wartość całkowitą, jest używana jako stałe ziarno do generowania hash()typów objętych randomizacją skrótu.

Jego celem jest umożliwienie powtarzalnego mieszania, na przykład autotestów samego interpretera, lub umożliwienie klastra procesów Pythona współdzielenia wartości skrótu.

Liczba całkowita musi być liczbą dziesiętną z zakresu [0, 4294967295]. Określenie wartości 0spowoduje wyłączenie randomizacji skrótów.

Na przykład:

$ export PYTHONHASHSEED=0                            
$ python -c "print(hash('http://stackoverflow.com'))"
-5843046192888932305
$ python -c "print(hash('http://stackoverflow.com'))"
-5843046192888932305
arekolek
źródło
3
Dotyczy to tylko Pythona 3.x, ale ponieważ Python 3 jest teraźniejszością i przyszłością i jest to jedyna odpowiedź, która dotyczy tego, +1.
Alexander Huszagh
8

Wyniki haszowania są różne dla platform 32- i 64-bitowych

Jeśli obliczony hash będzie taki sam na obu platformach, rozważ użycie

def hash32(value):
    return hash(value) & 0xffffffff
Tzury Bar Yochay
źródło
6

Domyślam się, że AppEngine używa 64-bitowej implementacji Pythona (-5768830964305142685 nie zmieści się w 32 bitach), a Twoja implementacja Pythona jest 32-bitowa. Nie można polegać na tym, że skróty obiektów są w znaczący sposób porównywalne między różnymi implementacjami.

George V. Reilly
źródło
6

Oto funkcja skrótu, której Google używa w środowisku produkcyjnym dla Pythona 2.5:

def c_mul(a, b):
  return eval(hex((long(a) * b) & (2**64 - 1))[:-1])

def py25hash(self):
  if not self:
    return 0 # empty
  value = ord(self[0]) << 7
  for char in self:
    value = c_mul(1000003, value) ^ ord(char)
  value = value ^ len(self)
  if value == -1:
    value = -2
  if value >= 2**63:
    value -= 2**64
  return value
Andrin von Rechenberg
źródło
7
Czy możesz podzielić się jakimś kontekstem na temat tego, do czego służy ta funkcja skrótu i ​​dlaczego?
amcnabb
5

A co z kawałkiem znaku?

Na przykład:

Wartość szesnastkowa 0xADFE74A5reprezentuje bez znaku 2919134373i ze znakiem -1375832923. Bieżąca wartość musi być podpisana (bit znaku = 1), ale Python konwertuje ją jako niepodpisaną i mamy niepoprawną wartość skrótu po translacji z 64 do 32 bitów.

Uważaj, używając:

def hash32(value):
    return hash(value) & 0xffffffff
Lew
źródło
3

Hasz wielomianowy dla ciągów. 1000000009i 239są dowolnymi liczbami pierwszymi. Mało prawdopodobne, aby zderzyły się przez przypadek. Arytmetyka modularna nie jest bardzo szybka, ale w zapobieganiu kolizjom jest to bardziej niezawodne niż przyjmowanie jej modulo na potęgę 2. Oczywiście łatwo jest celowo znaleźć kolizję.

mod=1000000009
def hash(s):
    result=0
    for c in s:
        result = (result * 239 + ord(c)) % mod
    return result % mod
Sergey Orshanskiy
źródło
2

Wartość PYTHONHASHSEED może zostać użyta do zainicjowania wartości skrótu.

Próbować:

PYTHONHASHSEED python -c 'print(hash('http://stackoverflow.com'))'
niebieskawy
źródło
-3

Prawdopodobnie po prostu pyta o funkcję dostarczoną przez system operacyjny, a nie o własny algorytm.

Jak mówią inne komentarze, użyj hashlib lub napisz własną funkcję skrótu.

ewanm89
źródło