"Intelligente" Hashtables/-listen

[Jan Krüger]

Hallo.
Für eine Realtime-Anwendung, die eine größere Menge von Strings mit einer Länge von bis zu ca. 30 Zeichen in einer Hashtable/liste aufbewahren soll, versuche ich gerade, einen effektiven Algorithmus zu finden.
Dieser Algorithmus soll folgende Kriterien erfüllen:
- schnell sein (Hashtable wird in jeder Sekunde mehrfach benutzt)
- wenn ein Slot der Hashtable überdurchschnittlich voll wird, die Gewichtungskriterien des Algorithmus dynamisch so abändern, dass der Slot sich in zwei andere aufteilt und dafür die beiden leersten Slots zusammengelegt werden. Dadurch wird auf Dauer eine gleichmäßige Verteilung der Strings auf die einzelnen Slots gewährleistet, so dass die Suchzeiten insgesamt kürzer werden. Allerdings soll diese "intelligente" Komponente auch nicht zu lahm sein, weil sie wohl auch öfters zum Einsatz kommen wird.

Hat jemand eine Idee?
Hat das überhaupt jemand so verstanden? ;)

[xOOn]

naj verstanden habe ich es schon so ca aber ka wie man das am besten macht

[jenz]

Hi,

ich habe mir da mal ein paar gedanken gemacht.
ich glaube eine dynamische anpassung der hashfunktion ist vielleicht ein bischen schwierig.
ich würde deshalb folgendes vorschlagen.
zu jedem slot wird gespeichert wieviele einträge er enthält.
sollten es zu viele werden, wird ein leerer slot gesucht. auf den dann von dem ersten zu vollen verlinkt wird.
in dem neuen slot muss dann noch ne info gesetzt werden, das er nicht mehr normal benutzt werden kann.
wenn man dann noch die einträge in dem vollen slot sortiert vorliegen hat kann man mit einem vergleich mit dem letzten element in diesem slot schnell feststellen wo man suchen muss, hier oder in dem verlinkten. dieser verlinkte slot könnte dann wieder genauso aufgebaut sein.
wenn jetzt ein eintrag kommt, der eigentlich in einen fremd benutzten slot muss, muss dieser slot enweder freigeräumt werden, oder man setzt dafür auch einen status und verlinkt wiederrum.
was man noch dynamisch machen könnte wäre die maximale anzahl von einträgen für einen slot, dann könnte man die tabelle imemr gleichmässig auffüllen.
wobei das dann natürlich einen relativ langen aufräumzyklus mit sich bringt.

vielleicht kann das helfen.

ciao jens

[Jan Krüger]

naja, durch das verlinken der slots wird die geschwindigkeit nur leider nicht besser, weil dann ja beide slots durchsucht werden müssten.
naja, ich hab jetzt ne grundsätzliche idee für den algorithmus, muss allerdings noch ein bisschen daran feilen.
wer noch vorschläge hat, bitte trotzdem posten.
ich meld mich, wenn mein algorithmus doch fertig werden sollte. :D

[Decorator]

hi jast,

sag mal kann es sein, daß du die antwort bzw. lösung von jenz nicht ganz verstanden hast ? wieso beide slots durchsuchen ? DU MUSST LEDIGLICH DIE LETZTEN ELEMENTE DES SLOTS VERGLEICHEN UND WEISST WO DU SUCHEN MUSST. also das klingt nach einer recht vernünftigen lösung. das es viel schneller geht kann ich mir kaum vorstellen aber wir sind gespannt auf deinen algorithmus !!!!


bis dann
decorator

[jenz]

ich wollte nur noch mal eben das von Dekorator bestätigen.
wenn die strings sortiert sind, dann muss du wirklich nur mit dem letzten element vergleichen und zack weisst du wo du weitersuchen musst.

sonst habe ich noch das gefunden

http://citeseer.nj.nec.com/cache/papers/cs/22640/http:zSzzSzwww-cs-students.stanford.eduzSz~csilverszSzpaperszSzperfhash-dimacs.pdf/silverstein98practical.pdf

durchgelesen habe ich es nicht ganz, aber es hört sich ganz gut an. perfektes hashing eben.

ciao jens

[Jan Krüger]

naja, sortieren ist etwas, was mir zu lange dauert. außerdem muss ich die strings aus geschwindigkeitsgründen anders sortieren.