Abschätzung für die Größe einer HashTabelle
-
Hallo zusammen,
ich benötige eine allgemeine Abschätzung für einen Allgorithmus und die darin verwendeten Hashtabllen. Die Zugriffszeit ist erst einmal zweitrangig. Heißt, ich müßte wissen wie groß eine Tabelle wird. Ich nehm mal an wenn ich einen 8-Bit Wert über diese Tabelle verwalten will und N Bukets zulasse, habe ich mindestens N*8Bit, jedoch wird das ja noch nicht alles sein, oder?
Jemand nen Tip? Steh gerade etwas auf der Leitung.
mfg
und dank
-
die hash tabelle ist so groß, wie du sie machst. sie "wächst" nicht, wenn du sie nicht explizit erweiterst.
wenn du in der tabelle nur 8 bit werte ablegen willst, hat sie natürlich n * 8 bit. aber so wie ich das verstanden habe, sind die 8 bit werte die schlüssel. d.h. deine hash tabelle hat nur die funktion, dass sie dir sagen kann, ob ein schlüssel vorhanden ist oder nicht. außerdem sind 8 bit gerade mal ein byte und du kannst ganz einfach ein array verwenden und das mit dem schlüssel indizieren und bekommst eine perfekte tabelle.
-
hi,
also das ist soweit klar. ich benötige meine hash funktion, sowie die eingentliche tabelle, welche ich dann addressiere über den hash wert. die einzelnen felder enthalten dann die elemente (wenn ich mal ein system ohne dynamische speicherverwaltung annehme). allerdings weiß ich nicht wie man die bucket überläufe abschätzt. wenn ich eine max. anzahl von A kollisionen annehme, kann ich dann sagen ich habe ein mehrdimensionales array mit 8xNxA Bit? Also NxA Byte? Scheint so, oder?
danke. uwe
-
http://de.wikipedia.org/wiki/Hashtabelle#Varianten_des_Hashverfahrens
das erklärt, wie man mit kollisionen umgeht. das problem mit hash tabellen ist, dass du eben die verteilung nicht gut abschätzen kannst. sie hängt von den schlüsseln wie auch von der verwendeten hash funktion und der größe der tabelle ab. wenn du mit sehr vielen kollisionen rechnest (weil du eine schlechte hash funktion verwendest, die schlüssel alle sehr ungünstig sind oder die tabelle sehr klein sein muss) solltest du mal über eine andere datenstruktur nachdenken.
-
hi,
also ich will das verfahren nicht implementieren, sondern bestehende algorithmen vergleichen, welche unter anderem hash verfahren einsetzten. am ende will ich eine ungefähre abschätzung haben, wie groß der gesamtspeicherverbrauch der einzelnen verfahren so pie mal daumen ist. von daher such ich soetwas wie eine formel für die mittlere größe einer hashtabelle, bei annahme von gleichverteilten werten. hätte ich vielleicht besser gleich dazu gesgt.
danke aber auf jeden fall, hat wirklich sehr geholfen.
uwe
-
Der Speicherplatzverbrauch eine Hashtabelle, die mittels Chaining implementiert ist ist O(n + m) mit n = Anzahl der Eingefuegten Elemente und m = Anzahl der Slots. Der versteckte Faktor ist unterschiedlich je nachdem, wie du das Chaining Implementierst (Array, einfach oder doppelt verkettete Liste): Wenn du ein Array verwendest (deine Hashtabelle also im Grunde nix anderes ist als z. B. ein Object**) haengts davon ab, wie gross deine Buckets sind. Bei einfach verketteter Liste brauchst du fuer Jedes Element einen Zeiger, bei doppelter Verkettung 2.
Bei offenem Hashing (1 Speicherplatz pro Slot, kein Chaining) ist der Speicherplatz ganz simpel m*sizeof(speicherbare Objekte).Du muesstest genauer sagen, welches Verfahren verwendet wird, sonst laesst sich die Groesse nicht genau angeben.
-
Blue-Tiger schrieb:
Der Speicherplatzverbrauch eine Hashtabelle, die mittels Chaining implementiert ist ist O(n + m) mit n = Anzahl der Eingefuegten Elemente und m = Anzahl der Slots.
das würde aber bedeuten, dass keiner der slots verbraucht wurde, selbst wenn du schon elemente drin hast. m muss die anzahl der ungenutzten slots sein.
was der threadersteller braucht, ist eine abschätzung, wie lang die überlauflisten maximal werden können. aber so eine abschätzung ist schwer bis unmöglich.
da viele bei hashing sehr optimistisch sind, geht man von einer gleichverteilung über alle slots aus. dh, bei m slots und n elementen hast du durchschnittlich in jedem slot genau ein element. verdoppelst du n, bekommst du pro slot zwei elemente, usw. aber wie schon gesagt, ist das nur der optimale fall. der wird wohl nicht unbedingt eintreten.hashtabellen mit einem zweidimensionalen array zu implementieren halte ich für unmöglich. man müsste die maximale anzahl an elementen pro slot im voraus wissen. irrt man sich, muss man die ganze matrix anpassen.
wenn du ein beispiel brauchst, schau dir beim programm readelf die option --histogram an. sie gibt dir eine statistik über die überlauflisten bei den symbol hashtabellen von elf binaries.
in einer arbeit an der uni hab ich mal vorgeschlagen, diese hashtabellen zu entfernen und stattdessen patricia tries dafür zu verwenden. ich denke, dass die besser dafür geeignet sind.