0xDEADBEEF

Osmibajtový hash

Dává v JVM jazycích smysl interně uchovávat hash jako osmibajtový long pro zrychlení volání equals()?

Platí že

a.equals(b) => a.hashCode == b.hashCode

a proto se equals může implementovat jako

def equals(x: X) =
  this.longHash == x.longHash &&
  expensiveEquals(this, x)

longHash je tady 8 B long, ale to může být i klasický int hash.

Uchovávat předpočítaný hash se může hodit ve dvou situacích:

• Rychlý hashCode(). Hash se spočítá jednou při konstrukci neměnného objektu nebo když je poprvé potřeba (à la String). To dává smysl jen částečně. Některé implementace hashmap interně uchovávají hashCode klíčů (dělá to mutable.HashMap i immutable.HashMap ve Scale, stejně jako java.util.HashMap) a používají je jako filtr před voláním equals(). Uchovávat předpočítaný hashCode v našem objektu má dopad jen pro hledaný klíč, ne pro ty v hashmapě. Vyplatí se jen, pokud je stejná instance opakovaně používána.

  Ve Scale hashCode generovaný pro case class je implementovaný jako 32 bit MurmurHash3. Jde o pár aritmetických operací pro každé slovo paměti. Sám za sebe bych rád viděl něco jako ahash, protože mám rád divné věci, ale ten potřebuje zvláštní a otravnou péči pro data proměnlivé délky.

• Rychlý equals(). Možná, ale jen když si objekty často nejsou rovny, např. mapa neuchovávající hashCode s mnoha kolizemi.

Jaká je pravděpodobnost kolizí? Řekněme že máme mapu s 128k buckety, která obsahuje 64k položek/klíčů. Kolize sledují Poissonovo rozložení.

Pr(X=k) = λ^k e^-l / k!

Pr(X=k) je pravděpodobnost, že do bucketu spadne k klíčů (λ = průměrný počet klíčů v bucketu). Z toho můžeme vypočítat, že v naší zpola plné mapě bude kolidovat 25786 klíčů, většina z nich (asi 20k) skončí v bucketu se 2 kolizemi.

Teď, kolik práce se provede, když chceme načíst každý klíč? Pro každý z nich musíme projít průměrně půlku řetězu kolizí (mutable.HashMap je uchovává jako seřazené podle hashCode, ale to má dopad jen pro brzký exit pro nepřítomné klíče). Ve výsledku musíme projít 81920 uchovaných klíčů, tedy 25% práce a potenciálně nákladného volání equals() navíc. Tady by mechanismus urychlující volání equals vhod, ale, jak už zaznělo, mapy ve Scale ho uchovávají a používají jako hrubé síto před samotným equals().

Efektivita toho síta záleží na tom, kolik kolizí vznikne v plném čtyřbajtovém. To je v našem případě prakticky nula, něco jako 1.16 * 10^-10. Jde o čísla pro ideální hashe, ty reálné nemusí být tak super (dívám se na String.hashCode). Nebo jak přesně java implementuje hashCode intu? Jako identitu.

Takže delší hash než 4 B nikdy není třeba? Ne tak rychle. V některých situacích můžu mít nepříliš dobrý hash záměrně, protože je rychlý, nebo dělám speciální manévry ve stylu rolling hash¹ . Nebo, když se velikost hashmapy blíží 4G limitu, 4B hashi začne docházet místo pro informace a vznikají kolize v plné délce, ale to nebude tak běžné. (Ještě mě napadá situace, kdy záleží jen na rychlosti a dají tolerovat špatné výsledky a snažíme se je co nejvíce minimalizovat.)

Ale obecně, ne. Delší hash než 4 B int nedává moc smysl.

Co mě přimělo o tomhle poprvé uvažovat byla chyba měření. Udělal jsem změnu délky interního hashe a program zrychlil o 10-15%. Úspěch. Ne tak docela. Šlo o koordinovanou náhodu. Několik měření před změnou bylo pomalých, několik po změně rychlých, zcela náhodou. Další šťourání ukázalo varianci rychlosti mezi běhy až 30%. OpenJDK 17, plně deterministický algoritmus, ale přesto výkyvy v rychlosti byly masivní. Benchmarkování je těžké.

1. Cyklický hash je jednoduchý, rychlý a má vlastnosti univerzálního hashe. Tady je zjednodušená verze v jazyce D.