Hallo Daniela,
Weist du wie sich eine Hashingfunktion bei vielen
Dubletten verhält?
Die Hashing-Funktion verhaelt sich gar nicht. Das
Hashtable-Framework (urghs, bloedes Buzzword, aber mir faellt
leider nichts besseres ein) reagiert damit in der Regel
darauf, dass es die Key-Laenge vergroessert und den Hash
komplett restrukturiert.
Eine Hashing-Funktion liefert idR Hash-Summen der Laenge
32 Bit oder 64 Bit (je nach dem, auf welcher Architektur sie
eingesetzt wird). Das ist natuerlich viel zu viel, denn wenn
man garantieren wollte, dass eine Hash-Summe immer innerhalb
des Bereichs der Tabelle ist, muesste man sie 2^32 bzw. 2^64
Eintraege gross machen. Deshalb wird idR mit etwa 10 Bit
angefangen, 2^10 = 1024, mit einem 1024 Elemente grossem
Array kann man noch leben. Wenn jetzt allerdings zu viele
Doubletten auftreten, wird die Keylaenge um ein Bit
vergroessert: statt 10 Bit verwendet man 11 Bit. Dafuer muss
aber jetzt die komplette Hash-Tabelle restrukturiert werden.
Fuer jeden Eintrag muss eine neue Position benutzt werden,
denn mit der neuen Key-Laenge sind die Summen natuerlich
nicht mehr gleich.
Insbesondere interessiert mich natürlich, wie sich
PostgreSQL mit einem Hashingindex dann verhält.
Das kann ich dir nicht sagen, ich habe nicht in den Source
geschaut, sorry.
Ich frag mich nämlich gerade, ob die mühsamen Joins
wirklich nötig sind, oder ob ich direkt die Worte
kombiniert mit dem Eintrag als Key benutzen soll und
darüber einen Hashingindex benutzen kann.
Du meinst wahrscheinlich nicht Dupletten, sondern doppelte
Eintraege. Das ist ein Unterschied. Eine Duplette ist ein
Eintrag, der dieselbe Hashsumme wie ein anderer Eintrag mit
einem anderen Key hat.
Wie PostGreSQL doppelte Eintraege verwaltet, kann ich dir
leider nicht sagen. Ich koennte mir vorstellen, dass es in
jedem Hash-Element eine lin. Liste gibt.
Möglich, wäre aber sehr bequem wenn das geht, würde mir
vorallem beim indizieren n Haufen abfragen und bestehende
Keys holen ersparen.
Mag sein. Es ist aber nicht moeglich, es sei denn, PostGreSQL
wuerde pro Key nicht einen, sondern len Eintraege in die
Tabelle machen, den Key immer um ein Bit kuerzer. Und das
kann ich mir echt nicht vorstellen.
Wenn er aber findet, er braucht etwas zu wenig häufig,
wird er es gar nicht ins Register holen.
Korrekt. Aber idR kann man fuer eine Architektur recht gut
vorraussagen, was im Register landet und was nicht.
Gruesse,
CK