Dynamic Hashing

Gast #798008
Lesenswert?

Hallo, einen schönen Abend zusammen!
Ich bin grad dabei, mir zu erarbeiten, was dynamisches Hashing ist.
Das normale Hashing und die Lösungen von Koolisionen habe ich problemlos 
nachlesen können.
Beim dynamischen bekomme ich Verständnisprobleme.

In einer Beschreibung habe ich gelesen, dass anfangs nur ein Behälter da 
ist. Wenn ein neuer Eintrag reinkommt, läuft der Behäter über und 
spaltet sich in 2 Behälter auf.Alle Einträge, deren Hash Werte mit 0 
beginnen, kommen in den einen Behälter, alle deren Has Wert mit 1 
beginnt in den zweiten Behälter. Diese spalten sich dannn jeweils wieder 
so  auf usw, es entsteht eine Baumstruktur.
Dabei habe ich eine Frage:
Das setzt doch vorraus, dass ein Hash Wert eine Folge aus einsen und 
Nullen ist.
Und man findet z.B. für den Hash Wert 00110 einen Pfad in dem Baum. 
Soweit die Beschreibung.

Was ist aber, wenn die Hash Funtktion nur einen Wert liefert, wie beim 
normalen Hash (s.o).
Da ist ja eine  Funktion z.: h(s) = s % 5. Es entsteht immer nur ein 
einstelliger Hash Wert.
Wie kann man jetzt so eine Baumstruktur aufbauen, wenn man z.B. mit 
dieser Hash Funktion und dynamsischen hashen erst die Zahl 6 und dann 
die Zahl 9 und dann die Zahl 13 einfügt.
Wie sieht der Baum dann aus ?

Darüber hinaus habe ich im Anhang einen Auszug aus unseren 
Vorlesungsfolien. Die zu verstehen ist das wichtigste für mich :)
Die Beschreibung von mir eben aus dem Internet mit den überlaufenden 
Behältern und der Baumstruktur kann ich in diesen Folien nicht 
wiederfinden.
Wie sind die Folien aus dem Skipt zu verstehen und im Einklang mit 
meiner Beschreibung ?


Danke schön ;)
Angehängte Dateien:
#798097
Lesenswert?

jochen wrote:

> Dabei habe ich eine Frage:
> Das setzt doch vorraus, dass ein Hash Wert eine Folge aus einsen und
> Nullen ist.

Das soll ja in einem Digitalcomputer nicht unbedingt so selten
sein.

> Was ist aber, wenn die Hash Funtktion nur einen Wert liefert, wie beim
> normalen Hash (s.o).
> Da ist ja eine  Funktion z.: h(s) = s % 5. Es entsteht immer nur ein
> einstelliger Hash Wert.

Auch dieser Wert ist letztendes nur eine Binärzahl, besteht
also nur aus 0-en und 1-en

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

oder

Mit Google-Account einloggen

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren