Hashing

[friednoodles]

Hi, ich befasse mich gerade mit Hashing und will sichergehen das ich folgende Dinge richtig verstanden habe.

1. Dem von uns angegebenen Key wird über eine Hash-Funktion eine Hash Adresse zugeteilt.
2. Diese Hash Adresse ist die Referenz auf einen "Bucket".
3. Diese Buckets enthalten das ursprüngliche key&value pair.
4. Diese Buckets sind in einem Array angeordnet und jeder Bucket enthält ein Objekt.

5. Die Hashtable Klasse ist eine Legacy-Klasse und sollte in neuem Code nicht mehr verwendet werden.
6. Methoden aus der Hashtable Klasse sind synchronized, was diese Thread-Safe machen. Dadurch performed die Hashtable Klasse langsamer
7. Die HashMap Klasse macht im Prinzip das selbe wie die Hashtable Klasse, nur Ihre Methoden sind unsychronized -> Thread-unsafe -> performed schneller

 

[kneitzel]

Also die meisten Punkte sind richtig. Aber nur fast.

Zum einen sind die Hashcodes von Instanzen nicht immer unterschiedlich und zum anderen werden ja aus den HashCodes alle Instanzen, die hinzugefügt werden, auf ein Array einer bestimmten Größe verteilt (z.B. per hashcode % Arraysize)

Daher muss in einem Array Element mehr als ein Element rein passen -> ein Bucket enthält also nicht ein Objekt sondern eine Liste von Objekten.

Also unter https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/ wird dies auch beschrieben.

Da wird aber jetzt nur generell gezeigt, wie man Objekte (z.B. Strings) so speichern kann. Bei einer Map sind diese Objekte dann halt Key/Value Paare, bei denen der Zugriff über den Key erfolgt, d.h. der Hashcode vom Key wird verwendet.

 

[friednoodles]

Also können je nach Hash-Funktion durchaus mehrere Objekte in eine Stelle des Arrays passen? Danke, Gut das ich hier nochmal nachgefragt habe

Noch eine Sache zu den Anwendungsgebieten und Vorteilen die Hashing mit sich bringt:

Der Vorteil vom Hashing ist doch, dass egal wie groß der Key ist, immer Hashcodes in der selben Größe erstellt werden, richtig?
Dadurch lassen sich große Datenmengen schnell vergleichen da nur die Hash-Adressen verglichen werden.
Gibt es noch weitere Vorteile weswegen man Hashing Collections mit anderer Datenstruktur vorziehen könnte?

 

[mihe7]

Also können je nach Hash-Funktion durchaus mehrere Objekte in eine Stelle des Arrays passen?

Natürlich. Kollisionen gehören zum Hashing dazu (perfektes Hashing, also ohne Kollisionen, gibt es zwar, ist aber selten und funktioniert praktisch nur für unveränderliche Daten).

Dadurch lassen sich große Datenmengen schnell vergleichen da nur die Hash-Adressen verglichen werden.

Jein. Mittels eines Hashwerts lässt sich die Ungleichheit feststellen, nicht aber die Gleichheit. Es gilt nur: unterscheiden sich die Hashwerte zweier Objekte, dann sind die Objekte garantiert verschieden.

Das ist wie ein Vergleich von Personen anhand der Nachnamen: sind die Nachnamen verschieden, weißt Du, dass es verschiedene Personen sind. Sind die Nachnamen dagegen gleich, bedeutet das nicht automatisch, dass es sich um gleiche oder gar die selbe Person handelt.

Beim Hashing geht es einfach darum, Speicheradressen anhand des Schlüssel zu berechnen. Das bedeutet nicht, dass dies gleich die Adresse des gesuchten Objekts ist, das hängt wiederum von der Kollisionsbehandlung ab.

Einfaches Beispiel: Du hast drei Eimer, in die sollst Du Bälle unterschiedlicher Farbe einsortieren. Den Hashwert eines Balls soll ermittelt werden, indem einfach für jeden Buchstaben der Farbbezeichnung die Position im Alphabet ermittelt und aufsummiert wird. Beispiel: ROT = 18 + 15 + 20 = 53.

Um die so erhaltenen Werte auf drei Eimer aufzuteilen, ermittelst Du einfach den Rest, der sich bei der Division des Hashwerts durch 3 ergibt (% = Modulo-Operator).

Du hast also drei Eimer: 0, 1, 2 und ich gebe Dir jetzt einen roten Ball (ROT = Hashwert 53). Du berechnest jetzt 53 % 3 = 2, also kommt der Ball in den Eimer 2. Jetzt gebe ich Dir einen blauen Ball (BLAU = Hashwert 36). Du berechnest jetzt 36 % 3 = 0, also kommt der Ball in den Eimer 0. Jetzt gebe ich Dir einen gelben Ball (GELB = Hashwert 26). Du berechnest jetzt 26 % 3 = 2, der Ball würde also im gleichen Eimer landen wie der rote. Das ist eine Kollision. Die kann man nun unterschiedlich behandeln, wir machen es uns einfach und sagen, dass sich in jedem Eimer beliebig viele Bälle befinden können (also eine Menge von Bällen enthalten kann) und schmeißen den blauen Ball zum roten dazu.

Jetzt bitte ich Dich, mir einen braunen Ball zu geben. Du kannst - ohne einen Blick auf die Eimer werfen zu müssen - sagen, in welchem Eimer sich der braune Ball befinden müsste: dazu berechnest Du einfach den Index des Eimers - wie vorhin: Hashwert von BRAUN = 56, 56 % 3 = 2, also kann sich der braune Ball nur in Eimer 2 befinden, wenn er denn überhaupt vorhanden ist.

Um das zu überprüfen, musst Du im Eimer nach dem Ball suchen. Das kann man so machen, dass Du blind einen Ball nach dem nächsten aus dem Eimer nimmst und schaust, ob er braun ist. Gibt es keine weiteren Bälle, enthält kein Eimer einen braunen Ball. Hast Du dagegen einen braunen Ball gefunden, kannst Du ihn mir geben -> Suche erfolgreich.

Im Beispiel würdest Du z. B. erst mal einen roten Ball herausnehmen. Der ist nicht braun, also weiter. Jetzt würdest Du den blauen Ball aus dem Eimer fischen. Der ist auch nicht braun, also weiter. Jetzt stellst Du fest: oh, der Eimer ist leer -> Ergebnis: kein brauner Ball vorhanden.

 

[friednoodles]

Vielen Dank für dieses Beispiel, habe dazu eine Frage.
Was genau bezeichnet man hier als Hashcode? Die 53 für die roten Bälle oder die 0, 1, 2 die nach der Hashfunktion den Eimern zugeteilt werden? Und als was kann man dann den jeweils anderen Wert bezeichnen?

 

[mihe7]

Was genau bezeichnet man hier als Hashcode?

Es werden ja zwei Hashfunktionen h1 und h2 verwendet: h1 bildet Wörter auf 32-Bit-Ganzzahlen ab, h2 bildet 32-Bit-Ganzzahlen auf eine Indexmenge (Teilmenge der 32-Bit-Ganzzahlen ab). Durch Komposition entsteht eine Hashfunktion h3, die Wörter auf eine Indexmenge abbilden.

Aus Sicht von h1 ist die 53 also der Hashcode (ROT -> 53), aus Sicht von h2 der Schlüssel (53 -> 2). In h3 taucht die 53 nicht mehr auf (ROT -> 2).