Proste haszowanie obiektów

W językach wspierających obiektowość zwykle mamy do czynienia z uniwersalną klasą bazową (Object), od której wszystkie inne muszą dziedziczyć. Składniki tej klasy są więc wspólne dla wszystkich obiektów. Czasami ma to negatywne skutki (vide wait i notify w Javie), ale zazwyczaj jest przydatne, bo wspólne składniki – takie jak toString – są często niezwykle użyteczne.
Istnieje jednak pewna metoda bazowa obiektów, której przeznaczenie nie musi być od razu oczywiste. Nazywa się ona dość podobnie w różnych językach: GetHashCode w C#, hashCode w Javie, zaś w Pythonie jest to po prostu __hash__. Nietrudno się więc domyślić, że ma ona coś wspólnego z hashem obiektu :) O co jednak dokładnie chodzi?

Hash to kompaktowa reprezentacja pewnej porcji danych, uzyskana za pomocą określonego algorytmu. Takim algorytmem może być na przykład MD5, SHA1, SHA256 i inne. Podstawowym wymaganiem, jakie stawia się takim funkcjom, jest determinizm: dla identycznych danych powinny one zwracać dokładnie te same wyniki.
Do czego jednak przydaje się możliwość haszowania< dowolnych obiektów? Otóż pozwala to na tworzenie kontenerów haszujących, takich jak zbiory i mapy. W Javie na przykład chodzi tu o pojemniki HashSet i HashMap, będące jednymi z możliwych implementacji ogólnych interfejsów Set i Map. Takie kontenery używają hashy jako podstawy swojego działania, zakładając, że ich porównywanie jest szybsze niż branie pod uwagę całych obiektów. Dopiero równość ich hashy pociąga za sobą konieczność porównania samych obiektów.

Być może nasuwa się tu od razu słuszny wniosek, że hashe dla obiektów potrzebne są wobec tego jedynie wtedy, gdy implementujemy własny sposób ich porównywania. (Opisywałem kiedyś, jak to się robi w języku C#). Często powinniśmy wtedy zapewnić taką implementację ekwiwalentu metody hashCode, która będzie spójna ze sposobem porównywania. Z grubsza chodzi o to, aby na hash wpływały pola, które bierzemy pod uwagę w metodzie equals/Equals/__eq__ – i tylko one.

W jaki sposób miałyby jednak to robić? No cóż, w teorii możemy zaprząc do pracy wymienione wyżej algorytmy i potraktować nimi połączone wartości pól obiektu (albo po prostu kawałek pamięci, w którym on rezyduje). W praktyce to bardzo kiepskie rozwiązanie (zwłaszcza wydajnościowo), bowiem wspomniane funkcje haszujące niezupełnie do tego służą. Istnieje bowiem różnica między kryptograficzną funkcją haszującą a zwykłą: ta pierwsza ma na celu przede wszystkim uniemożliwienie odtworzenia oryginalnych danych, jeśli znany jest tylko ich hash. W przypadku funkcji używanych wraz z pojemnikami haszującymi bardziej interesuje nas jednorodność, co (w uproszczeniu) oznacza, że hash obiektu powinien być wrażliwy na wartości poszczególnych pól tego obiektu. Z tego też powodu poniższe rozwiązanie:

jest do niczego, mimo że świetnie spełnia teoretyczne wymaganie, aby dwa równe obiekty miały równe hashe.

Dostępna jest oczywiście wyrafinowana wiedza na temat konstruowania dobrych (a nawet doskonałych) funkcji haszujących, ale dokładnie rachunki prawdopodobieństwa kolizji nieczęsto nas interesują – zwłaszcza, jeśli właściwie nie wiemy, w jakich pojemnikach i wśród jakich innych obiektów skończą te nasze. Na szczęście mamy też prostsze warianty. Wśród nich interesująco wygląda na przykład sposób pokazany w znanej książce Effective Java, który wygląda mniej więcej w ten sposób:

1. Zaczynamy od dowolnej liczby dodatniej.
2. Dla każdego znaczącego pola w obiekcie:
   1. bierzemy jego 32-bitową reprezentację (w razie potrzeby używając operacji bitowej xor dla większych pól)
   2. dodajemy ją do wyniku, uprzednio pomnożonego przez małą liczbę pierwszą

Zastosowanie go np. do prostej klasy punktu 3D wyglądałoby na przykład tak:

Wybór 23 jest raczej arbitralny, natomiast 31 ma tę zaletę, że mnożenie przez nią liczby x jest równoważne przesunięciu bitowemu i odejmowaniu, tj. (x << 5) - x. Analogicznie jest zresztą dla innych liczb o jeden mniejszych od potęg dwójki.