Hashtable, wie benutzen?

[isilive]

Hallo Leute,

ich habe ein sehr grosses Array mit mehreren Millionen Einträgen vom Typ INT64.
Nun möchte ich diese Zahlen schnell auffinden können bzw. nachschauen, ob sie schon im Array existiert.
Ich denke dazu würde sich wohl eine Hashtable anbieten und ich hab diese hier gefunden.
Blöde Frage: Wie benutz ich die Hashtable?
Als TIntegerDictionary erwartet sie von mir bei Add(Key, Data) als Key einen Int64/Cardinal und als Data einen Pointer.
Heisst das ich erstelle mein Array wie gewohnt und liefere dann als Key den Index vom aktuellen Element und als Pointer einen Pointer zum aktuellen Element vom Array? Oder ersetzt die Hashtabelle das Array?
Hab noch nie Hashtabellen benutzt und verstehe grad das Grundprinzip nicht.

[Aphton]

Die Hashtabelle funktioniert im Prinzip ca so:
- Für jeden Input (Int64 in deinem Fall) wird ein Hash (Pseudo Hash Funktion; liefert in meisten Fällen eine Zahl im Bereich von 2^8 oder 2^16) berechnet
- Dieser Hash dient als Array Index (es existiert ein Array mit der festen Größe 2^8 oder 2^16 (Hash Max-Wert).
Das Array ist in meisten Fällen vom Typ <einfach verkettete Liste>
Dieser Liste werden die Daten angehängt.

Wenn du nun nach Input xyz suchst, musst du zuerst den Hash bilden, diesen als Index benützen und dann die Liste so lange durchiterieren, bis du das Element findest!

Edit:
Achja, evt. wäre hier die binäre Suche angebrachter, sofern die Daten sortiert vorliegen!
Bei genau 1.000.000 Datensätzen bräuchtest du nur ~20 Abfragen (=log2(1.000.000))

Edit2:
Man könnte ja auch beides Kombinieren und ein 2 dimensionales Array verwenden, wobei man auf die erste mit dem Hashindex zugreift und auf die Zweie die binäre Suche drüberjagt!

[mjustin]

Zitat von isilive:

Hallo Leute,

ich habe ein sehr grosses Array mit mehreren Millionen Einträgen vom Typ INT64.
Nun möchte ich diese Zahlen schnell auffinden können bzw. nachschauen, ob sie schon im Array existiert.
Ich denke dazu würde sich wohl eine Hashtable anbieten und ich hab diese hier gefunden

Delphi 2009 verwendet Hashtables in Generics.Collections,
man kann z.B. die Klasse TDictionary<Key, Value> nutzen:

Delphi-Quellcode:

type
  TMyInt64HashTable = TDictionary<Int64, Boolean>;
   ...

  // Hashtable mit fünf Millionen Einträgen Anfangskapazität 
  Table := TMyInt64HashTable.Create(5000000);

  ...

  Table.Add(1, True);

  if Table.ContainsKey(1) then ...

[bit4bit]

Wenn Du wissen willst, ob die Zahl schon in Deinem Array drin ist, benutzt Du am besten ein Bloom Filter.

Ein negatives Ergebnis ist absolut verlässlich, die Zahl ist also 100%ig nicht im Array vorhanden.
Ein positives Ergebnis kann mit einer geringen Wahrscheinlichkeit falsch sein, d.h. Du musst das
Ergebnis mit einer anderen, etwas aufwendigeren Methode überprüfen um sicher zu sein.

Bloom Filter sind sehr schnell. Ich hab jedenfalls gute Ergebnisse damit erzielt.
Such einfach mal nach dem Begriff (z.B. Wikipedia).

[Furtbichler]

So ein Bloom Filter ist ja ganz lustig, aber ich bezweifle, das er schneller als eine Hashmap ist.

[BUG]

Ein Bloomfilter der Hashmap vorgeschalten werden und verhindern, dass bei einer Kollision (bei Millionen unterschiedlichen Werten nicht unwahrscheinlich) die Liste in einem Hashmap-Eintrag durchsucht werden muss.

Anders herum könnte man mit einem kleinem Filter und einer großen Hashmap ein bisschen vom Cache und davon profitieren, dass nicht ständig zufällig Speicherseiten eingeswap werden müssen, die zur Hashmap gehören.

Das könnte also schon was bringen.
Bei weiteren Überlegungen wäre es interessant zu wissen: wieviel Prozent der Werte, die du prüfen möchtest, sind denn in dem Array?

Wenn du noch Probleme hast, dir vorzustellen, wie du Hashmaps benutzt:
Sie implementieren ein assoziatives Array (wie es in Scriptsprachen überall genutzt wird).

[Iwo Asnet]

Zitat von BUG:

Ein Bloomfilter der Hashmap vorgeschalten werden und verhindern, dass bei einer Kollision (bei Millionen unterschiedlichen Werten nicht unwahrscheinlich) die Liste in einem Hashmap-Eintrag durchsucht werden muss.

Eine gute Hashmap skaliert, d.h. die Anzahl der Kollisionen ist dann relativ gering.

Zitat:

Das könnte also schon was bringen.

Das wäre denkbar. Bei den mir bekannten Bloomfilter-Implementierungen werden jedoch verschiedene Hashfunktionen verwendet. Dies dürfte der Pferdefuß werden.

[isilive]

Danke für eure Antworten!

Mein Array hat 25 Mio. Einträge und obwohl die lineare suche bei < 1 Mio Einträge noch ganz ok ist wenn man sie flott programmiert, wird es bei mehreren Mio. Einträgen eine Katastrophe.

Delphi-Quellcode:

for i:=0 to arraysize do   // arraysize=25 Mio.
array1[i]:=int64_x;        //irgendeine zahl, zB: Zufallszahl
  for j:=0 to i-1 do
    if int64_x = array1[j] then
      found:=true;

Der Rechenaufwand steigt zum Quadrat. O(n²)
Hab das Pgm 24h laufen gelassen und er ist bis 8 Mio. gekommen

Hab dann mjustins Vorschlag ausprobiert und die Generics.Collections verwendet.
Das TDictionary wie im Beispiel hat perfekt funktioniert und die Zeit auf O(n) reduziert!
Das ermöglicht die Abfrage der gesamten Tabelle auf einen doppelten Eintrag in <2 min !
Danke!

Trotzdem würde mich noch interessieren, wie man Alzaimars Hashtable benützt. Hat jemand einen kleinen Beispielcode?

[Iwo Asnet]

Delphi-Quellcode:

MyDict:= TIntegerDictionary.Create;
For i:=0 to Samples.Count do MyDict.Add(Samples[i],nil);

...
If MyDict.contains(SomeValue) Then ....

so ähnlich sollte es gehen.

[Horst_]

Hallo,

@isilive:
Was tut denn dies Programm?

Delphi-Quellcode:

for i:=0 to arraysize do // arraysize=25 Mio.
 begin 
 array1[i]:=int64_x; //irgendeine zahl, zB: Zufallszahl
 for j:=0 to i-1 do
  if int64_x = array1[j] then
    found:=true;
 end;

Es kann ja nichts finden. Du fügst eine Zahl bei Index i ein suchst aber bis Index i-1

Wie Aphton schon schrieb:
Du könntest die Daten sortieren oder stattdessen ein IndexFeld anlegen, dass dort die Daten sortiert vorliegen und dort dann die binäre Suche durchführen.

Delphi-Quellcode:

function VergleichsFunktion(i,j: integer):integer;
var
  Test : Int64;
begin
  result := 0;
  Test := array[Index[i]]-array[Index[j]];
  IF Test> 0 then
    result := 1;
  else
    IF Test< 0 then
      result := -1;
end;
...
//Daten auffüllen
 if array[Index[i]]< array[Index[i]]
for i:=0 to arraysize do // arraysize=25 Mio.
 begin
 array1[i]:=int64_x;
 Index[i]:= i;
 end;

QuickSort(Index,VergleichsFunktion);

Wenn Du schon während des Aufbauens der Felder Doppelte vermeiden willst, kannst Du ja sortieren durch Einfügen anwenden.

Gruß Horst