Hash Tables

[Markus28]

Hi,
ich schreibe gerade ein Suchprogramm mit Java und soll nun irgendwas mit Hash-Tables und inverted Index einführen, wovon ich überhaupt nichts verstehe. Ist hier jemand, der das einem Normal-Sterblichen erklären kann?
Danke im Voraus.

 

[kopfsalat]

Wer sagt, dass Du das sollst und gibt dir keine weiteren Infos darüber ?

 

[Markus28]

Meine Dozenten. Informationen haben sie gegeben, aber keine, die ich eben so verstehen könnte. Könnt Ihr mir nicht helfen und erklären, worum es eigentlich geht? Ich weiß, daß es die Suche verschnellern soll, durch Indizierung. Habe aber keine Ahnung, wie ich das praktisch angehen könnte.

 

[kopfsalat]

Leider sagt mir inverted Index als Schlagwort nichts.
Würde mich aber wundern, wenn das etwas völig Abgedrehtes wäre.

Zu Hashtables hier das Script einer Vorlesung:
http://wwwcs.upb.de/cs/ag-bloemer/lehre/dua_SS2004/material/folien16.pdf
Da wird direkte Adressierung, und dann Hashen mit Listen als Kollisionsverwaltung erklärt.

Die Folie kommt von hier:
http://wwwcs.upb.de/cs/ag-bloemer/lehre/dua_SS2004/
Dort findet sich dann auch das Folgekapitel "Offene Adressierung", welche das Hashing-Konzept erweitert.

Allerdings ist dort nichts, was "inverted Index" heißen könnte.
Vielleicht bedeutet "inverted Index" auch nur eine spezielle Art und Weise, einen Hashwert für einen String zu berechnen ??

 

[KSG9|sebastian]

ich weiß es auch net, aber google wär schonma nen anfang..

 

[Bleiglanz]

Denk mal an ein Telefonbuch, nach Namen sortiert

Abraham 234234
Bummerln 89234802
Cicero 11ß32481ß
...
Zipfe 2828745672

klar ist, dass das suchen nach einem Namen sehr leicht ist, weil das ganze Teil ja so schön vorsortiert ist. Aber was tun, wenn du eine Telefonnummer gegeben hast, und den dazugehörigen Namen
suchst?

keine Chance, du musst das ganze Ding von vorne bis hinten lesen
(in sql würde man sagen: full table scan), das dauert

da wäre es doch schön, wenn irgendwer einen INDEX erstellen würde (auf die Nummern), d.h. das ganze nochmal, aber diesmal nach Nummern sortiert

111112342 Garldiblab
11113452 Alonso
2342234 Dummsky
2828745672 Zipfe
3234234 Schuble
...
999999 Bertram

ja wenns sowas gibt, dann kann man auch leicht nach der Nummer suchen...

bei der technischen Umsetzung gibts natürlich ein paar Schmankerl , man schreibt z.B. im index buch die einzelnen seiten immer nur zu 75% voll, damit man einen neuen datensatz leicht einfügen kann

usw. usf.