Forum: Offtopic Dynamic Hashing


von jochen (Gast)


Angehängte Dateien:

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 ;)

von Karl H. (kbuchegg)


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

von Michael G. (linuxgeek) Benutzerseite


Lesenswert?

Dieser Jochen macht hier nen Info ;) Naja ich koennt jetzt ja mal 
nachschauen, oder denken... aber ich hab heute keine Lust mehr. Aber ich 
komm auf Dich zurueck ;)

von jochen (Gast)


Lesenswert?

ok dann ist das schonmal klar, dann wandelt man die Zahl einfach in eine 
Digitalzahl um.

Sagt das Bild das gleiche aus?

von Uhu U. (uhu)


Lesenswert?

jochen wrote:
> ok dann ist das schonmal klar, dann wandelt man die Zahl einfach in eine
> Digitalzahl um.

Du meinst Binärzahl - aber das ist sie in den gängigen Computern eh 
schon...

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.