PureBoard

Verfasst: **18.10.2006 21:46**

Hi Leute!

Ich hab heute mal eine kleine Hashtabelle gecodet, die ich für meine
Datenbank benötige. Ich hab daraus aber ein eigenes Interface gemacht,
damit man sie auch so benutzen kann.

Man kann einem Long, Quad, Float, Double, String oder Speicherbereich ein
Long zuweisen, das man zurückerhält, wenn wieder das selbe Long, usw.
angibt. Da das alles wahlweise über MD5 oder CRC32 funktioniert, kann es
natürlich zu Überschneidungen kommen, wodurch es mehr als nur einen
Rückgabewert geben kann, die man abfragen kann.

Ich hab die Codes auf meinen Lycos-Webspace gepackt und ihr könnt mal
testen.

///Edit 1:
+Added: DelL(), DelQ(), DelS(), DelF(), DelD(), DelM() zum Löschen eines Eintrags durch Angeben von Long, Quad, String, ... und ID
+Added: DelL_IgnID(), DelQ_IgnID(), ... zum Löschen eines Eintrags durch Angeben von Long, Quad, ... und keiner ID
+Added: Clear() leert die ganze Hashtabelle
+Added: Gibt den Speicher wieder frei und das Interface ist nicht mehr benutzbar

///Edit 2:
+Added: ChangeL(), ... zum Ändern der ID eines Eintrags
+Added: ChangeL_IgnID(), ... ignoriert auch die ID und ändert die ID eines Eintrags

///Edit 3:
+Added: SetHashCallback() zum Setzen einer eigenen Hash-Funktion
+Added: CountEntries() gibt die Anzahl der Einträge zurück

Im Beispiel ist auch ein Callback zum Demonstrieren der Hashfunktion
enthalten. Und die Hashfunktion ist auch noch selbst gemacht.

///Edit 4:
Speicherleck in fast allen Funktionen gefunden und eliminiert.
Der Dank geht an Ingo Platte.

HT.pbi (Das Interface)

Link funktioniert nicht, weil Lycos letztes Jahr alles gelöscht hat.
Beispiele.pb (Das Beispiel)

(Entweder einfach draufklicken oder "Ziel speichern unter...")

Verfasst: **19.10.2006 16:58**

Verfasst: **20.10.2006 16:03**

Die Löschfunktion geht jetzt auch schon. Allerdings ist noch nichts
hochgeladen. Das kann ich aber wahrscheinlich gleich machen, wenn ich zu
Hause bin. (Bin gerade noch auf der Arbeit)

Danach baue ich noch eine Ändern-Funktion ein und dann ist die Hashtabelle
eigentlich fertig.

Aber ich wäre dennoch offen für weitere Vorschläge!

Übrigens:
Die Procedure HT_Debug(*HT) zeigt die komplette Hashtabelle an, wen es
interessiert. Ich benutze die Funktion momentan aber nur zu
Debug-Zwecken, was man wohl aus dem Namen erschließen kann.

Verfasst: **20.10.2006 16:50**

Und da ist auch schon das Update! (s. 1. Post)

Zum Testen freigegeben!

Eine Bitte:
Ich hätte gern dahingehend Feedback, wer sowas gebrauchen kann oder
einfach, ob es bei jedem funktioniert / nicht funktioniert.

Verfasst: **21.10.2006 02:25**

Und da ist auch schon das zweite Update! (s. 1. Post)

Bitte wieder testen!

Verfasst: **23.10.2006 15:12**

Und das dritte Update mit selbstgebastelter Hashfunktion als Beispiel.

Alles weitere steht wie immer im ersten Post.

Antwortet hier nur niemand, weil keiner weiß, was eine Hashtabelle ist, oder
weil sie niemand braucht oder weil das hier kein Feedbackforum ist oder weil
niemand eine Hashfunktion braucht?

Vielleicht sollte ich mal ein Speedtest dazu legen.

Verfasst: **23.10.2006 15:15**

Also ich weiß nicht, was eine Hashtabelle ist.

Verfasst: **23.10.2006 15:19**

Alves hat geschrieben:Also ich weiß nicht, was eine Hashtabelle ist.

Du weisst aber schon, was eine Suchmaschine ist?

Grüße ... Kiffi

Verfasst: **23.10.2006 15:21**

Verfasst: **23.10.2006 16:42**

@Alves:
Eine Hashtabelle verwendet man, um z.B. Strings in einer großen Liste von
Strings wieder zu finden, ohne umständlich die ganze Liste durchzugehen,
indem man Hashfunktionen wie CRC32 oder MD5 verwendet und geschickt
eine Baumstruktur oder ähnliches bastelt.

@all:
Hier mal ein Speedvergleich. Beim Starten öffnet sich ein PathRequester().
Dann sollte man ein möglichst großes Verzeichnis auswählen. Das wird
dann dreimal rekursiv durchlaufen. Das erste Mal ist nur, weil das erste
Einlesen eines Verzeichnis oft am längsten dauert, ab dem zweiten Mal
geht es dann schneller.
Beim zweiten Durchlauf werden dann alle Dateinamen in die Hashtabelle
geschrieben, solange sie nicht schon vorhanden sind. Und das ist der auch
der springende Punkt, wo es auf die Geschwindigkeit ankommt. Beim
dritten Einlesen werden nämlich alle Dateinamen in eine LinkedList
geschrieben und vorher wird sie immer komplett durchgegangen um zu
schauen, ob die Datei nicht schon existiert.
Nach dem Hinzufügen der Dateien meldet sich ein MessageRequester(),
das die Zeit zum Einfügen angibt, die Dateien, die momentan in der Liste
sind und die Anzahl der Dateien, die gerade eingelesen wurden.

Aber testet einfach mal selbst:

Code: Alles auswählen

Global NewList HTList.s(), *HT.HT
Global NewList List.s()

Procedure HTFileCallback(Path.s, File.s)
  Protected *s.String, Add.l
  
  Add = #True
  Path = Path + File
  *s = *HT\GetS(Path)
  While *s
    If *s\s = Path : Add = #False : Break : EndIf
    *s = *HT\GetNext()
  Wend
  
  If Add
    If AddElement(HTList())
      HTList() = Path
    EndIf
    *s = AllocateMemory(SizeOf(String))
    *s\s = Path
    *HT\AddS(Path, *s)
  EndIf
EndProcedure

Procedure FileCallback(Path.s, File.s)
  Protected Add.l
  
  Path = Path + File
  
  Add = #True
  ForEach List()
    If List() = Path : Add = #False : Break : EndIf
  Next
  
  If Add
    If AddElement(List())
      List() = Path
    EndIf
  EndIf
EndProcedure

Procedure Recursive(Path.s, *procFile)
  Protected Name.s, Count.l
  Static NewList Dir.l()
  
  If Right(Path, 1) <> "\" : Path + "\" : EndIf
  
  LastElement(Dir())
  If AddElement(Dir())
    Dir() = ExamineDirectory(#PB_Any, Path, "")
    If Dir()
      While NextDirectoryEntry(Dir())
        Name = DirectoryEntryName(Dir())
        If DirectoryEntryType(Dir()) = #PB_DirectoryEntry_Directory
          If Name <> "." And Name <> ".."
            Count + Recursive(Path + Name + "\", *procFile)
          EndIf
        Else
          Count + 1
          If *procFile : CallFunctionFast(*procFile, Path, Name) : EndIf
        EndIf
      Wend
      LastElement(Dir())
      FinishDirectory(Dir())
      DeleteElement(Dir())
      LastElement(Dir())
    EndIf
  EndIf
  
  ProcedureReturn Count
EndProcedure

Define Path.s, time1.l, time2.l, files1.l, files2.l

*HT = HT_Create()
If *HT = 0 : End : EndIf

*HT\SetMaxTreeSize(5)

Repeat
  Path.s = PathRequester("Pfad auswählen...", "c:\")
  
  If Path
    Recursive(Path, 0) ;weil der erste Durchlauf immer länger braucht als der zweite
    
    time1 = ElapsedMilliseconds()
      files1 = Recursive(Path, @HTFileCallback())
    time1 = ElapsedMilliseconds() - time1
    
    time2 = ElapsedMilliseconds()
      files2 = Recursive(Path, @FileCallback())
    time2 = ElapsedMilliseconds() - time2
    
    MessageRequester("Zeiten", "(Dateien in Liste) [Dateien im Verzeichnis]" + Chr(13) + "Mit Hashtable: " + Str(time1) + " ms (" + Str(CountList(HTList())) + ") [" + Str(files1) + "]" + Chr(13) + "Ohne Hashtable: " + Str(time2) + " ms (" + Str(CountList(List())) + ") [" + Str(files2) + "]")
  EndIf
Until Path = ""

Noch etwas allgemeines zu meiner Hashtabelle. Die Zugriffszeiten sind
sehr wahrscheinlich unterschiedlich bei den versch. Hashverfahren.

Hier mal die zwei Beispiele CRC32 und MD5 und ihre maximale Weglänge
bis zum passenden Hash:

CRC32: 4 Bytes, jedes Byte hat 256 Zustände
MD5: 32 Bytes, jedes Byte hat 16 Zustände

Extremfälle:
CRC32: 4 * 256 + x = 1024 + x Einträge müssen durchlaufen werden zum Finden des passenden Hashes
MD5: 32 * 16 + x = 512 + x Einträge müssen durchlaufen werden zum Finden des passenden Hashes

x steht für die geringe Wahrscheinlichkeit, dass zwei oder mehr Einträge
den gleichen Hash haben und dementsprechend nebeneinander stehen.

Selbst wenn in der Tabelle 1.000.000 Strings liegen, bräuchte man mit
MD5 nur maximal 512 Schritte um ihn wiederzufinden. Durchschnittlich
liegt die Anzahl der Schritte aber ca. bei 256, also der Hälfte, was logisch
erscheint.

Vielleicht hat das dem ein oder anderen ja geholfen und er weiß jetzt, was
eine Hashtabelle ist.

PureBoard

Eine kleine Hashtabelle (jetzt ohne Speicherlecks!)

Eine kleine Hashtabelle (jetzt ohne Speicherlecks!)