Frage von 0lli1234, 31

Hashing (Offene Adressierung mit linear probing)?

Hallo!

Ich stecke gerade bei einer Aufgaube bzgl. Hashing.

Folgendes ist gegeben:

Werte A=[1,3,1,2,6,9,4]

A[i] = 13 + 3 * M[i]

Hashfunktion: h`(k)=k * mod?

Daraus folgen die Werte:

A[0] = 16 / Hashwert = 1

A[1] = 48 / Hashwert = 3

A[2] = 16 / Hashwert = 1

A[3] = 32 / Hashwert = 2

A[4] = 96 / Hashwert = 1

A[5] = 144 / Hashwert = 4

A[6] = 64 / Hashwert = 4

Wenn ich jetzt jedoch meine Hashtabelle fülle und 2 mal den key 16 für zB den Index 1 habe, wird dieser dann in den selben Bucket gegeben oder ebenfalls mit der erweiterten Hashfunktion ein freier Platz gesucht?

Da in diesem Fall mehr keys vorhanden sind als freie Buckets?

Bzw. gilt es bei der verketteten Hashtabelle als Kollision wenn 2 mal der selbe key gegeben ist oder nur bei 2 unterschiedlichen pro Bucket?

Danke für jede Hilfe!

LG

Antwort
von HJarausch, 6

Ich verstehe deine Fragestellung nicht. Was ist M[i] ?

Allgemein: Beim open hashing muss die Hashtabelle immer größer sein, als die Zahl der keys, die eingefügt werden, außer ein "bucket" kann mehr als einen Eintrag aufnehmen - dies macht man jedoch nur bei externem hashing, d.h., wenn die buckets auf einer Festplatte liegen.

Bei eine Hashtabelle mit verketteten Listen wird eine Liste verlängert, wenn einem key durch die Hashfunktion derselbe Wert zugewiesen wird.

Da das Durchsuchen einer verketteten List aufwändig ist, sollte man die Hashfunktion und die Größe der Hashtabelle so einrichten, dass im Mittel die Listen eine kleine Länge (meist < 2) haben.

Keine passende Antwort gefunden?

Fragen Sie die Community