Wbudowana funkcja hash () w języku Python

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)?

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.

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 .

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.

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

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

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.

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

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

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

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

Próbować:

PYTHONHASHSEED python -c 'print(hash('http://stackoverflow.com'))'

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.