Hashable, niezmienny

Z niedawnego pytania SO (zobacz Tworzenie słownika w Pythonie, który jest indeksowany przez listy ) zdałem sobie sprawę, że prawdopodobnie miałem błędną koncepcję znaczenia obiektów haszowalnych i niezmiennych w Pythonie.

• Co w praktyce oznacza hashable?
• Jaka jest relacja między hashable i immutable?
• Czy istnieją zmienne obiekty, które są hashowalne lub niezmienne, które nie podlegają hashowaniu?

Haszowanie to proces konwertowania dużej ilości danych na znacznie mniejszą ilość (zazwyczaj pojedynczą liczbę całkowitą) w powtarzalny sposób, aby można było je wyszukać w tabeli w stałym czasie ( O(1)), co jest ważne dla wysokiej wydajności algorytmy i struktury danych.

Niezmienność to idea, zgodnie z którą obiekt nie zmieni się w jakiś istotny sposób po jego utworzeniu, zwłaszcza w taki sposób, który mógłby zmienić wartość skrótu tego obiektu.

Te dwa pomysły są powiązane, ponieważ obiekty, które są używane jako klucze skrótu, zwykle muszą być niezmienne, więc ich wartość skrótu nie zmienia się. Gdyby pozwolono na zmianę, położenie tego obiektu w strukturze danych, takiej jak tablica hashy, zmieniłoby się, a wtedy cały cel hashowania dla wydajności zostałby zniweczony.

Aby naprawdę zrozumieć tę ideę, powinieneś spróbować zaimplementować własną tablicę haszującą w języku takim jak C / C ++ lub przeczytać implementację tej HashMapklasy w Javie .

• Czy istnieją zmienne obiekty, które są hashowalne lub niezmienne, które nie podlegają hashowaniu?

W Pythonie krotka jest niezmienna, ale można ją mieszać tylko wtedy, gdy wszystkie jej elementy są mieszalne.

>>> tt = (1, 2, (30, 40))
>>> hash(tt)
8027212646858338501
>>> tl = (1, 2, [30, 40])
>>> hash(tl)
TypeError: unhashable type: 'list'

Hashable Types

• Wszystkie niezmienne typy atomowe są mieszalne, takie jak str, bajty, typy numeryczne
• Zamrożony zestaw jest zawsze hashowany (jego elementy muszą być z definicji hashowane)
• Krotkę można mieszać tylko wtedy, gdy wszystkie jej elementy są mieszalne
• Typy zdefiniowane przez użytkownika są domyślnie mieszane, ponieważ ich wartością skrótu jest ich id ()

Z glosariusza Pythona :

Obiekt jest haszowalny, jeśli ma wartość skrótu, która nigdy się nie zmienia w trakcie swojego życia (potrzebuje __hash__()metody) i może być porównywany z innymi obiektami (potrzebuje metody __eq__()lub __cmp__()). Obiekty z możliwością mieszania, które porównują równe wartości, muszą mieć tę samą wartość skrótu.

Hashability sprawia, że ​​obiekt może być używany jako klucz słownika i element członkowski zestawu, ponieważ te struktury danych używają wartości skrótu wewnętrznie.

Wszystkie niezmienne obiekty wbudowane Pythona są hashowalne, podczas gdy żadne zmienne kontenery (takie jak listy lub słowniki) nie są. Obiekty, które są instancjami klas zdefiniowanych przez użytkownika, są domyślnie mieszane; wszystkie porównują nierówności, a ich wartością skrótu jest id ().

Dykty i zestawy muszą używać skrótu w celu wydajnego wyszukiwania w tablicy skrótów; wartości skrótu muszą być niezmienne, ponieważ zmiana skrótu zepsuje struktury danych i spowoduje niepowodzenie dyktowania lub zestawu. Najłatwiejszym sposobem uczynienia wartości skrótu niezmienną jest uczynienie całego obiektu niezmiennym, dlatego często wspomina się o nich razem.

Chociaż żaden z wbudowanych obiektów podlegających zmianom nie może być mieszany, możliwe jest utworzenie zmiennego obiektu z wartością skrótu, która nie jest modyfikowalna. Zwykle tylko część obiektu reprezentuje jego tożsamość, podczas gdy reszta obiektu zawiera właściwości, które można dowolnie zmieniać. Dopóki wartość skrótu i ​​funkcje porównania są oparte na tożsamości, ale nie na modyfikowalnych właściwościach, a tożsamość nigdy się nie zmienia, wymagania zostały spełnione.

Technicznie hashable oznacza, że ​​klasa definiuje __hash__(). Według dokumentów:

__hash__()powinien zwrócić liczbę całkowitą. Jedyną wymaganą właściwością jest to, że obiekty, które porównują równe wartości, mają tę samą wartość skrótu; zaleca się jakoś wymieszać ze sobą (np. używając wyłącznych lub) wartości skrótu dla składników obiektu, które również odgrywają rolę w porównaniu obiektów.

Myślę, że dla typów wbudowanych Pythona wszystkie typy hashable są również niezmienne.

Byłoby trudne, ale być może nie niemożliwe, mieć zmienny obiekt, który mimo wszystko jest zdefiniowany __hash__().

Istnieje domniemanie, nawet jeśli nie ma wyraźnego związku wymuszonego między niezmiennymi i haszowalnymi ze względu na wzajemne oddziaływanie

1. Obiekty z możliwością mieszania, które porównują równe wartości, muszą mieć tę samą wartość skrótu
2. Obiekt można skasować, jeśli ma wartość skrótu, która nigdy nie zmienia się w trakcie jego życia.

Nie ma tutaj problemu, chyba że przedefiniujesz __eq__tak, aby klasa obiektów definiowała równoważność wartości.

Kiedy już to zrobisz, musisz znaleźć stabilną funkcję mieszającą, która zawsze zwraca tę samą wartość dla obiektów, które reprezentują tę samą wartość (np. Gdzie __eq__), zwraca True i nigdy się nie zmienia w trakcie życia obiektu.

Trudno jest znaleźć aplikację, w której jest to możliwe, rozważ możliwą klasę A, która spełnia te wymagania. Chociaż istnieje oczywisty zdegenerowany przypadek, w którym __hash__zwraca stałą.

Teraz:-

>>> a = A(1)
>>> b = A(1)
>>> c = A(2)
>>> a == b
True
>>> a == c
False
>>> hash(a) == hash(b)
True
>>> a.set_value(c)
>>> a == c
True
>>> assert(hash(a) == hash(c)) # Because a == c => hash(a) == hash(c)
>>> assert(hash(a) == hash(b)) # Because hash(a) and hash(b) have compared equal 
                                 before and the result must stay static over the objects lifetime.

W rzeczywistości oznacza to przy tworzeniu hash (b) == hash (c), mimo że nigdy nie są porównywane równe. W każdym razie staram się znaleźć przydatne zdefiniowanie __hash__() dla zmiennego obiektu, który definiuje porównanie według wartości.

Uwaga : __lt__, __le__, __gt__i __ge__comparsions nie wpływa więc nadal można zdefiniować zamawianie hashable obiektów modyfikowalnych, lub w inny sposób na podstawie ich wartości.

tylko dlatego, że jest to najpopularniejszy hit Google, oto prosty sposób na utworzenie zmiennego obiektu z możliwością mieszania:

>>> class HashableList(list):
...  instancenumber = 0  # class variable
...  def __init__(self, initial = []):
...   super(HashableList, self).__init__(initial)
...   self.hashvalue = HashableList.instancenumber
...   HashableList.instancenumber += 1
...  def __hash__(self):
...   return self.hashvalue
... 
>>> l = [1,2,3]
>>> m = HashableList(l)
>>> n = HashableList([1,2,3])
>>> m == n
True
>>> a={m:1, n:2}
>>> a[l] = 3
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> m.hashvalue, n.hashvalue
(0, 1)

Właściwie znalazłem zastosowanie czegoś takiego podczas tworzenia klasy do rzutowania rekordów SQLAlchemy na coś zmiennego i bardziej użytecznego dla mnie, zachowując ich hashability do użycia jako klucze dyktowania.

Niezmienność oznacza, że ​​obiekt nie zmieni się w żaden znaczący sposób podczas swojego życia. To niejasny, ale powszechny pomysł w językach programowania.

Hashability jest nieco inna i odnosi się do porównania.

hashable Obiekt jest hashable, jeśli ma wartość hash, która nigdy nie zmienia się w trakcie swojego życia (potrzebuje__hash__()metody) i można go porównać z innymi obiektami (potrzebujemetody__eq__()lub__cmp__()). Obiekty z możliwością mieszania, które porównują równe wartości, muszą mieć tę samą wartość skrótu.

Wszystkie klasy zdefiniowane przez użytkownika mają __hash__metodę, która domyślnie zwraca tylko identyfikator obiektu. Zatem obiekt, który spełnia kryteria hashability, niekoniecznie jest niezmienny.

Obiekty dowolnej nowej klasy, które zadeklarujesz, mogą być używane jako klucz słownika, chyba że uniemożliwiasz to, na przykład, rzucając z __hash__

Moglibyśmy powiedzieć, że wszystkie niezmienne obiekty są hashowalne, ponieważ jeśli hash zmienia się w trakcie życia obiektu, oznacza to, że obiekt został zmutowany.

Ale nie całkiem. Rozważmy krotkę, która ma listę (zmienną). Niektórzy twierdzą, że krotka jest niezmienna, ale jednocześnie w pewnym sensie nie można jej haszować (rzuca).

d = dict()
d[ (0,0) ] = 1    #perfectly fine
d[ (0,[0]) ] = 1  #throws

Hashability i niezmienność odnoszą się do instancji obiektu, a nie typu. Na przykład obiekt typu krotka może być hashowany lub nie.

W Pythonie są one w większości zamienne; ponieważ hash ma reprezentować zawartość, więc jest tak samo zmienny jak obiekt, a zmiana obiektu na wartość skrótu uczyniłaby go bezużytecznym jako klucz dict.

W innych językach wartość skrótu jest bardziej związana z „tożsamością” obiektów, a niekoniecznie z wartością. Tak więc w przypadku zmiennego obiektu wskaźnik mógłby zostać użyty do rozpoczęcia haszowania. Zakładając oczywiście, że obiekt nie porusza się w pamięci (jak robią to niektóre GC). Jest to na przykład podejście stosowane w Lua. To sprawia, że ​​zmienny obiekt może być używany jako klucz tabeli; ale stwarza kilka (nieprzyjemnych) niespodzianek dla początkujących.

W końcu posiadanie niezmiennego typu sekwencji (krotek) sprawia, że ​​jest przyjemniejszy w przypadku „kluczy wielowartościowych”.

Hashable oznacza, że ​​wartość zmiennej może być reprezentowana (a raczej zakodowana) przez stałą - ciąg znaków, liczbę itp. Teraz coś, co podlega zmianie (zmienne), nie może być reprezentowane przez coś, co nie jest. W związku z tym żadna zmienna, która jest modyfikowalna, nie może być hashowana i, z tego samego powodu, tylko niezmienne zmienne mogą być hashowane.

Mam nadzieję że to pomoże ...