Kleine Implementierung: Bucketindex

Bucketindex aus hashCode und Tabellenlänge: typisch (hash & 0x7fffffff) % capacity oder bit masking bei Zweierpotenz.

$$i=(h\mathbin{\&}\mathtt{0x7fffffff})\bmod m$$

Wo gebraucht

Modulo bzw. Bitmaske auf die Kapazität ist der Kern jedes Hash-Containers. Fehler hier (negativer Hash, falsche Kapazität) sind typische Implementierungsbugs.

Vertiefung

Ein Bucketindex muss für jeden möglichen Hashwert im Bereich von null bis Kapazität minus eins liegen. In Java ist Math.floorMod(hash, capacity) eine direkte Formulierung dieser Invariante. Eine blosse Betragsbildung ist bei Integer.MIN_VALUE problematisch, weil sein positiver Gegenwert im int-Bereich nicht darstellbar ist.

Die Kapazität muss positiv sein. Bei Kapazitäten als Zweierpotenzen verwenden manche Implementierungen Bitmasken, mischen zuvor aber oft hohe und niedrige Hashbits. Ohne diese Mischung könnten regelmässige Bitmuster die unteren Positionen übermässig belasten.

Schwierigkeitsstufen

1. Indizes für positive und negative Hashwerte bestimmen.
2. Den Sonderfall des kleinsten int-Werts erklären.
3. Moduloabbildung und Bitmaske unter passenden Voraussetzungen vergleichen.

Fallstricke

Math.abs(hash) % capacity ist nicht für alle int-Werte sicher. Ebenso führt eine Kapazität von null nicht zu einem sinnvollen Bucket, sondern zu einem arithmetischen Fehler.