Hashtable, wie benutzen?

[himitsu]

Dennoch sagen die Code- und Speicherpositionen manchmal was aus.

Also warum sollte man dann die Texte der Fehlermeldungen unterschlagen?

[isilive]

Es ist eine Zugriffsverletzung "Lesen von Adresse 00000001" und bezieht sich nur auf die abgewandelte .pas Datei von Horst, der sie ja primär auf Freepascal geschrieben hat. Der Fehler tritt unregelmässig und nur bei 500-2000 Schleifendurchläufen auf, was darauf hindeutet, dass es dann knallt wenns eine Kollision in der Hashtable gibt. (Aber um das genau zu wissen versteh ich das ganze Konstrukt noch etwas zu wenig.)

Die orginale .pas läuft und die hab ich jetzt auch verbaut. Also für mich ist die Exception hier kein Problem mehr.

Hab jetzt leider keine Zeit, kann aber morgen mehr posten wenns gewünscht ist.

[Iwo Asnet]

Zitat von himitsu:

Dennoch sagen die Code- und Speicherpositionen manchmal was aus.

Also warum sollte man dann die Texte der Fehlermeldungen unterschlagen?

Zitat von isilive:

Es ist eine Zugriffsverletzung "Lesen von Adresse 00000001"

Grmmel Grmmel... Ja ja himitsu, hast ja Recht

[isilive]

Um nochmal auf die Hauptroutine von Horst zurückzukommen (warum seine dictionary.pas bei mir knallt ist momentan nicht so wichtig. Die orginale funzt ja tadellos.)

Delphi-Quellcode:

  j := low(A64);             
  For i := low(A64) to High(A64) do
    begin
    Wert := random(RANDOMRANGE);
    IF TestHash.Add(Wert,Pointer(j)) then  
   begin
         A64[j] := Wert;
         inc(j);
   end;
    end;
  setlength(A64,j);   

//wieder auslesen aus der Hashtable:
    TestHash.find(A64[i],dummy)
    writeln (integer(dummy));

Das mit der Hashtable und dem Key ist klar und läuft auch.
Aber was kann ich denn als Data abspeichern und somit als Pointer übergeben? Nur Integer? Und was wird dann abgespeichert, ein Adresspointer auf die übergebene Variable oder deren Wert? Also darf ich diese Variable danach verändern?
Ist das Auslesen generell so vorgesehen wie in den unteren beiden Zeilen? Bei einem ersten Test hat's funktioniert.

[Horst_]

Hallo,

man kann der Hash-table den Schlüssel und einen Zeiger auf irgendwelche Daten übergeben.
Da aber da ja nur Index in das Feld gebraucht wird, reicht es, den integer Index in einen Pointer zu casten.
Beim Auslesen wird der Pointer eben wieder in ein integer gecastet.
Das geht aber nur, solange die Daten maximal soviel Speicher wie der type Pointer brauchen, bei 32 Bit-Systemem 4 Byte== LongInt und bei 64 Bit eben 8 byte = Int64.

Gruß Horst
P.S.
csdictionary ist von alzaimar für Delphi hier aus der code-library.
Ich habe nur den Typ des Schlüsselwertes geändert.

Probiere mal Dictfind in http://www.delphipraxis.net/1163327-post17.html testen.

[isilive]

Die geht (mit deiner Version von csDictionary, das ich csDictionaryh getauft habe um Verwechslungen zu vermeiden).

Es liegt an "RANDOMRANGE" mit high(Int64). Bei "MyRandom" oder einer Randomrange:=high(Integer) funktioniert es problemlos.

Rufe ich allerdings Dict.add (Testhash.add) mit random(high(Int64)) als key auf, dann kommt irgendwann die Exception. Tracen ist ein bisschen schwierig, weil es erst beim x-ten Schleifendurchlauf (500<x<5000) passiert.

Delphi-Quellcode:

Function TIntegerDictionary.FindHash(aKey : TDictIntType; Out h: Cardinal): Pointer;
Begin
  h := HashFromInt(aKey) Mod fHashMod;
  Result := fHashList[h];
  While PIntHashEntry(Result) <> Nil Do
    With PIntHashEntry(Result)^ Do
      If heKey = aKey Then
        Exit
      Else
        Result := heNext;
End;

Aber es passiert in der Zeile "If heKey = aKey then", also nur wenn ein Hashentry gefunden wurde.

[Horst_]

Hallo,

ich wollte mit myrandom eben keine Zufallszahlen erzeugen, sondern Zahlen, die in der Hashtable alle an der selben Stelle landen.
Damit erzwinge ich im Beispiel 25 Mio -1 Kollisionen und die Erzeugung einer linearen Liste.
Du hattest doch mal vermutet, das bei der ersten Kollision der Fehler mit dem Zugriff auf Speicheradresse 0...01 erfolgt sein könnte.
Das kann man jetzt wohl ausschließen.

Gruß Horst
P.S:
2008 wusste alzaimar das sein csDictionary aus
http://www.delphipraxis.net/45571-hash-tabellen.html
nicht Int64 sondern cardinal ist,
http://www.delphi-forum.de/viewtopic...=501690#501690

[isilive]

Wie auch immer, auf jedenfall konnte ich schon erfolgreich die orginale csDictionary verwenden. Ich hab mit grossen Zahlen gerechnet - mpArith von Wolfgang Ehrhardt. Das BigNumberErgebnis wollte ich zusammen mit einem Integer in eine Hashtable schreiben.
Wenn man die bigNumber als String ausgibt kann man sie problemlos im Stringdictionary verwenden. Es ist praktisch, dass man Strings verschiedener Länge ohne Performanceverlust verwenden kann, da ja einfach gehasht wird.

Und mit deinem Pointertrick konnte ich den zugehörigen Integer speichern und wieder lesen. Danke!!!

Delphi-Quellcode:

var dummy:pointer;
begin
    j:=someinteger;
    IF TestHash.Add  (Wert, Pointer(j)) then ...

    TestHash.Find    (Zahl, dummy);
    j:=integer(dummy)
end;

Zwei Sachen:

- Dein "Pointertrick" ist cool. Aber wie lautet die Syntax die für den 2. Parameter normalerweise vorgesehen ist? (Übergibt man die Adresse eines Arrayelements um diese bei .Find wiederzubekommen?)

- dict.add als function statt als procedure ist wirklich eine starke Verbesserung! Vielleicht würde es Alzeimar einbauen?!

PS: Wen's interessiert, interessehalber hab ich dieselbe Hashmap danach mit Generics.collections inplementiert. Die Syntax ist sehr ähnlich, die Funktionalität auch und die resultierende Geschwindigkeit für 1 Mio. Einträge auch. Evtl. ist Generics um geschätzte 2-3 Prozent schneller. Zeigt, dass alzeimar hier einen guten Job geliefert hat.