Hashing Problem

[stoxx]

mir ist gerade aufgefallen, dass ein Algorithmen Forum sehr nützlich wäre :-)

ich habe ein Problem, und komme nicht so recht weiter.
Auch weil ich mich nicht genügend mit dem Thema Hashing auskenne.

Ich habe folgende Ausgangsvariablen.
viele aufeinanderfolgende wahr und falsch Sequenzen.

a : array [1..63] of boolean;

das würde dann ungefähr so aussehen.
10001010100010100100 ....1010100

daraus möchte ich eine Integer Zahl machen (da brauche ich INT64 Zahlen )

aus 1110 wird dann z.B. 14

jetzt komm ich hier nicht weiter.
Ich suche ein Hash Funktion, die mir die optimale Adresse liefert.
Mein Problem. Ich weiß zwar, was die angeblichen vorteile eines Hashes sind, bekomme das selber aber irgendwie nicht so recht auf die Reihe.
Weiß jemand Rat ? .. stecke irgendwie in einer Sackgasse.
Binäre Bäume möchte ich nicht nehmen, wegen den vielen Zeigern
(ich möchte nur 4 Byte pro Datensatz speichern), die Zeiger würden das ganze dann auf 4 + 8 = 12 Byte aufblähen

[Pascal]

Hallo,
ich verstehe leider nicht, was du genau machen möchtest.
Du hast doch in deinem array schon alle Informationen, was möchtest du nun in einer Hashtabelle speichern bzw. warum willst du deine Werte in Integer-Zahlen umrechnen. Ist mir nicht ganz klar!

Hashtabellen benützt du normalerweise, um Daten in eine Tabelle zu speichern und möglichst schnell wieder zu finden.

Vielleicht kannst du dein Problem noch mal genauer erklären!

Gruß Pascal

[negaH]

Erstmal kannste dein A: array[0..63] of Boolean optimieren auf 1/8 der jetzigen Größe wenn du A: Int64 nutzt. Jedes Bit in A wäre dann ein Boolean aus A[]. Nun sortierst du diese A's binär in eine Liste ein. Die Suche nach einem A wäre dann die Suche in dieser Liste von Int64 Werten. Angenommen 1024 solcher A's sind in der Liste, dann benötigst du nur maximal 10 Vergleiche per Binärer Suche um das richtige A zu finden. Somit benötigst du überhaupt keinen Hashalgortihmus, er wäre in deinem alle sinnlos und wesentlich langsammer. Die Suche nach der richtigen Einfügeposition in der Liste für ein neues A wäre bei 1024 Einträge ebenfalls nur 10 Vergleiche maximal. Beim Einfügen selber müsste man aber ca. 512 Einträge durchschnittlich im Speicher kopieren.

Gruß Hagen

[stoxx]

Zitat:

Zitat von Pascal

Hallo,

Vielleicht kannst du dein Problem noch mal genauer erklären!

Gruß Pascal

Hallo Pascal,

also ich möchtei die Daten so schnell wie möglich wiederfinden.
Das ist das wichtigste daran.
Sonst stelle ich keine Bedingungen an die Hashtabelle.
Die Daten müssen nicht sortiert ausgegeben werden oder so.

Zitat:

Du hast doch in deinem array schon alle Informationen,

naja .. es treten ja nicht alle Kombinationen von 001010011 auf.
(Aber aus diesem Bereich sind alle möglich)
Also umgerechnet nicht alle Integer Zahlen von 0 bis 2^64.
Weil das nämlich auch die Grenzen meines Computer sprengen würde *g*
Also kann ich nicht für jede Sequenz von 01001 linear eine Array Stelle festlegen.
Also brauch ich ein kleineres array als 2^64, brauche aber nun eine Adress Berechnung, wo die Werte abgespeichert werden, und zum schnellen Finden wäre es halt günstig, wenn das in Form einer Hashtabelle geschehen würde, da ja dort der Schlüssel aus der "information" berechnet wird.
Aber ich seh doch noch nicht so recht durch.

Bin aber schon bissl weitergekommen, mal sehen ob ich das verstehe.
Das hier brauch ich im Prinzip.
http://www.informatik.uni-ulm.de/dbi...ualHashing.pdf

[stoxx]

Zitat:

Zitat von negaH

Die Suche nach der richtigen Einfügeposition in der Liste für ein neues A wäre bei 1024 Einträge ebenfalls nur 10 Vergleiche maximal.
Gruß Hagen

Hi Hagen,

1024 .. also so wenig Einträge sind es halt nicht.
Die Umrechnung von dem array of boolean nach int64 kommt ja ganz zuerst.
Danach will ich 4 Byte grosse Datensätze, wo int64 verschiedene Möglichkeiten vorkommen können, auf die Festplatte speichern.

[jbg]

In 4 Bytes (Int32) bekommt man keine 8 Bytes (Int64).


Durch deine Ausführungen, komme ich noch nicht dahinter, was dein eigentliches Ziel ist. Soll der Hash-Wert 4 Bytes groß sein? Wo kommen dann die Int64s her?

[negaH]

Wieviele solcher Int64 willst du erwartungsgemäß verwalten ?
Das einzigste Problem mit meinem obigen Vorschlag wäre das Einfügen eines neuen Int64 in die Liste. Da dann Speicherkopierungen nötig wären. Wenn du aber nur maximal 2^16 solcher Werte verwalten willst dann wäre der beste Weg ein Array mit verlinkten Int64 Werten zu benutzen. D.h. ein Eintrag sähe so aus

Delphi-Quellcode:

type
  TEntry = packed record
    Value: Int64;   // array[0..63] of Boolean
    Next: Word;     // Index des nächsten Eintrages in TEntryArray
  end;

  TEntryArray = array of TEntry;

TEntryArray wird succesive blockweise vergößert. Also zb. erst 1024, 2048,4096 usw. Bei 65535 max. Einträgen würden so nur 7 Reallokationen dieses Arrays auftreten. Mit 2^16 Einträgen würde das Array 2^16*10 = 650Kb im Speicher benötigen. Das Einfügen eines neuen Wertes benötigt KEINERLEI Kopieroperationen, da der neue Wert nur ans Ende des Arrays angehangen wird. Die Binäre Suche ist dagegen ein bischen komplizierter, da nun das Array über deren .Next Einträge durchsucht werden müsste. Für einen neuen Wert sucht man im Array den Eintrag der der kleinste Eintrag genau vor dem neuen Wert ist. Dessen .Next wird auf die Anzahl der im Array gespeicherten Einträge gesetzt, also auf den neuen Eintrag. Der neue Eintrag wird als letzer im Array eingefügt und dessen Next wird auf das Next des kelinesten Eintrages gesetzt. Danach wird der Counter für die Anzahl der Einträge im Array um eins hochgezählt.

Gruß Hagen

[negaH]

Also, ich glaube du verstehst nicht wie Hash-Listen funktionieren. Beiu einer Hashliste wird der große Datenwert möglichst eindeutig und gleichverteilt auf einen kleineren Datenwert runtergerechnet. Das dieser Hashwert NICHT alle Werte exakt beschreiben kann ist dann auch logisch. Somit muß bei der Verwendung einer Hashtabelle diese Hashtabelle gespeichert werden UND alle exakten Werte die diese Hashtabelle verwaltet. In deinem Falle musst du also einen HashEntry benutzen mit Int32 als HashWert + Int32 als Index ind Wertetabelle + Int64 als eigentlichen Wert. Somit würde eine Hashtabelle viel mehr Speicher benötigen und da die Komprimierung von 64Bit runter auf 32Bit viel zu gering ist, wäre die hashtabelle zudem ineffizient.

Ich weis das Hashtabellen immer wieder als Allheilmittel bezeichnet werden, aber genau dies ist niemals der Fall. Hashtabellen sind Krücken die bei großen Datenstrukturen die aber auf Grund ihrer Wahrscheinlichkeiten des Datenaufkommens nur ein extrem begrenztes Set unterstützen, Anwendung finden. D.h. einen Hashtabelle ist immer dann effizient wenn sie z.b. 1024 HashWerte auf eine mögliche Datenmenge von 256 Bit Werten von denen aber nur 2048 Werte tatsächlich vorkommen würden, mappen kann.

Gruß Hagen

[negaH]

Zitat:

1024 .. also so wenig Einträge sind es halt nicht.

Bei 1024 Einträgen würdest du nach 10 Vergleichen mit Werten aus dem Array herausfinden ob der aktuelle 64Bit Wert schon im Array ist. Bzw. in 10 Vrgleichen würdest du die EInfügeposition ermitteln können.
Bei 2048 Einträgen wären 11 Vergleiche nötig, da 2^11 = 2048. Somit bei 65535 Einträgen nut 16 Vergleiche. Die Anzahl dieser Vergleiche ist die Anzahl im Worst Case, also im schlechtesten Falle. Im Durchschnitt würden man aber bei 2^16 Elementen im Array nur 8 Vergleiche benötigen !

Schneller kann eine Hashfunktion auch nicht sein. Eine hashfunktion würde diese 2^16 Elemente durch ein Array von z.B. 1024 Word's beschreiben. D.h. 1 Eintrag im hasharray ist der Index in eine Int64 Tabelle. Man zieht vom in64 ein 16Bit Hash der dann an die Position im array positioniert. So, bei 1024 Haswerten im hasharray würden 65535/1024 = 64 Duplikate pro hashwert möglich sein. D.h. jeweils 64 Int64 Werte teilen sich ein und selben Hashwert. Somit würde die hashtabelle beim Heraussuchen von 65535 Werten a 64Bit mit einer Berechnung 63/64 aller Werte ausfiltern. Die restlichen 64 Werte müssten wiederum ber Vergleichssuche gefunden werden. Nimmt man dafür eine Binäre Suche so wären 6 Vergleiche nötig. D.h. insgesamt würde eine Hashtabelle 4 Vergleiche im Duerchschnitt benötigen, im Gegensatz zu 8 bei einer reinen binären Suche. Dafür benötigt die hashtabelle ein wesentlich komplexerer Struktur die ihre Zeit kostet. In deinem Falle wäre dieser Zeitliche Aufwand aber der Performancebestimmende Faktor.

Gruß Hagen

[negaH]

Eine sehr einfache Form einer Hashtabelle wäre folgende.
Aus dem Int64 extrahierst du die obersten 2 Bytes = Word. D.h. der Int64 wird in einmal 2 Bytes + 6 Bytes zerlegt. Nun werden 65535 Arrays of Array of TWert angelegt. Die obersten 2 Bytes sind der Index in diese Array of Array Tabelle.
So und nicht anders würde eine Fulldomain-Hashfunktion arbeiten. Wenn du dir das durchrechnest dann siehst du das eine Hashfunktion in deinem Falle ineffizienter als eine binär sortierte verlinkte Liste mit 64 Bit Werten.

Gruß Hagen