0xDEADBEEF

RSS odkazy english edition
««« »»»

Osmibajtový hash

18. 8. 2021 #Java #Scala #DS

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:

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 hash1 . 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.
píše k47 (@kaja47, k47)