Hashtable zur Zuordnung von Zahlen zu Strings [Interface]

Beitrag von **NicTheQuick** » 21.09.2005 22:25

Hi Leute!

Ich brauchte einen Algorithmus, der es mir erlaubt viele unterschiedliche
Strings zu speichern und ihnen einen Wert (Zahl) zuzuordnen. Und wenn
ich nach diesen Strings wieder suchen wollte, sollte das richtig schnell
gehen. Wenn man nämlich alle Strings in einer LinkedList oder einem
Array speichern würde und jedes einzelne Element überprüfen würde,
könnte das im schlimmsten Falle richtig lange dauern.
Ich mache das jetzt aber anders, und zwar über den Umweg des MD5-
Fingerprints. Nachteil ist deshalb erstmal, dass bei riesigen Strings oder
Speicherbereichen der MD5-Fingerprint schon ziemlich lange dauert. Aber
diesen Nachteil werde ich wohl noch ändern.

Und hier ist der ganze Code mit kleinem Beispiel auch schon.

///Edit 1:
Hab den Code jetzt mal für zu große Strings schneller gemacht.
Mir ist noch ein Nachteil eingefallen:
Es kann mit einer Wahrscheinlichkeit von 1 zu 34028236692093846346337460743177 * 10.000.000 davon ausgegangen werden, dass ein falscher Wert zu einem String zurückgegeben wird.

///Edit 2:
Jetzt als Interface verfügbar!

Code: Alles auswählen

Interface TB
  TB_EmptySize.l()
  TB_TotalSize.l()
  TB_Add.l(*EntryM, Length.l, Value.l)
  TB_Search.l(*EntryM, Length.l)
  TB_Del.l(*EntryM, Length.l)
  TB_Free.l()
EndInterface

Structure TB_Struc
  VTable.l
  
  ;Functions
  fTB_EmptySize.l
  fTB_TotalSize.l
  fTB_Add.l
  fTB_Search.l
  fTB_Del.l
  fTB_Free.l
  
  ;Data
  Accuracy.l
  Entries.l
  *pTable.LONG ; Enthält die Tabelle mit den Einträgen (Size = Entries * 4)
EndStructure
;Struktur von einem Eintrag
;4 Bytes : Anzahl der Einträge
;for 1 to Einträge {
;4 Bytes : *s\s Zugriff auf MD5-Hash
;4 Bytes : Value
;}


#TB_MaxLength = 1000
;Gibt die Größe in Bytes der leeren Tabelle zurück
Procedure.l TB_EmptySize(*TB.TB_Struc)
  If *TB
    ProcedureReturn *TB\Entries * 4 + SizeOf(TB_Struc)
  EndIf
  ProcedureReturn #False
EndProcedure

;Gibt die Größe in Bytes der gesamten Tabelle samt Einträge zurück
Procedure.l TB_TotalSize(*TB.TB_Struc)
  Protected *Entry.LONG, a.l, Size.l
  If *TB
    Size = *TB\Entries * 4 + SizeOf(TB_Struc)
    *Entry = *TB\pTable
    For a = 1 To *TB\Entries
      If *Entry\l
        Size + PeekL(*Entry\l) * 41 + 4
      EndIf
      *Entry + 4
    Next
    ProcedureReturn Size
  EndIf
  ProcedureReturn #False
EndProcedure

;[intern] Gibt zu einem Wert (0..1, a..f, A..F) den entsprechenden Wert zurück
Procedure.l TB_GetPos(ASCII.l)
  If ASCII >= '0' And  ASCII <= '9'
    ProcedureReturn ASCII - '0'
  ElseIf ASCII >= 'a' And ASCII <= 'f'
    ProcedureReturn ASCII - 'a' + 10
  ElseIf ASCII >= 'A' And ASCII <= 'F'
    ProcedureReturn ASCII - 'A' + 10
  EndIf
  ProcedureReturn 0
EndProcedure

;Fügt der Tabelle einen neuen Eintrag hinzu
;*EntryM  - Pointer zu einem String oder einem Speicherbereich
;Length   - Länge des Strings oder Speicherbereiches (bei 0 wird auf Nullterminierung geprüft)
;Value    - Wert, der zu dem String oder Speicherbereich gehört
Procedure.l TB_Add(*TB.TB_Struc, *EntryM, Length.l, Value.l)
  Protected *c.BYTE, a.l, MD5.s, Pos.l, *Entry.LONG, Entries.l, *s.STRING
  
  If *TB
    
    If Length
      If Length > #TB_MaxLength : Length = #TB_MaxLength : EndIf
      MD5 = MD5Fingerprint(*EntryM, Length)
    Else
      MD5 = PeekS(*EntryM, #TB_MaxLength)
      MD5 = MD5Fingerprint(@MD5, Len(MD5))
    EndIf
    
    *c = @MD5
    
    a = 0
    Pos = 0
    While *c\b
      a + 1
      If a <= *TB\Accuracy
        Pos * 16 + TB_GetPos(*c\b)
      Else
        Break
      EndIf
      *c + 1
    Wend
    
    *Entry = *TB\pTable + Pos * 4
    
    If *Entry\l = 0
      *Entry\l = AllocateMemory(4 + 8)
      If *Entry\l = 0 : ProcedureReturn #False : EndIf
      PokeL(*Entry\l, 1)
      *s = *Entry\l + 4
      *s\s = MD5
      PokeL(*Entry\l + 8, Value)
    Else
      Entries = PeekL(*Entry\l)
      *Entry\l = ReAllocateMemory(*Entry\l, 12 + Entries * 8)
      If *Entry\l = 0 : ProcedureReturn #False : EndIf
      PokeL(*Entry\l, Entries + 1)
      *s = *Entry\l + 4 + Entries * 8
      *s\s = MD5
      PokeL(*s + 4, Value)
    EndIf
    ProcedureReturn #True
  EndIf
  
  ProcedureReturn #False
EndProcedure

;Sucht nach einem String oder Speicherbereich und gibt den dazugehörigen Wert zurück (s. TB_Add)
Procedure.l TB_Search(*TB.TB_Struc, *EntryM, Length.l)
  Protected MD5.s, *c.BYTE, a.l, Pos.l, *Entry.LONG, Entries.l, *s.STRING
  
  If *TB
    
    If Length
      If Length > #TB_MaxLength : Length = #TB_MaxLength : EndIf
      MD5 = MD5Fingerprint(*EntryM, Length)
    Else
      MD5 = PeekS(*EntryM, #TB_MaxLength)
      MD5 = MD5Fingerprint(@MD5, Len(MD5))
    EndIf
    
    *c = @MD5
    
    a = 0
    Pos = 0
    While *c\b
      a + 1
      If a <= *TB\Accuracy
        Pos * 16 + TB_GetPos(*c\b)
      Else
        Break
      EndIf
      *c + 1
    Wend
    
    *Entry = *TB\pTable + Pos * 4
    If *Entry\l = 0
      ProcedureReturn #False
    Else
      Entries = PeekL(*Entry\l)
      *s = *Entry\l + 4
      For a = 1 To Entries
        If *s\s = MD5 : ProcedureReturn PeekL(*s + 4) : EndIf
        *s + 8
      Next
    EndIf
  EndIf
  ProcedureReturn #False
EndProcedure

;Löscht einen bestimmten Eintrag anhand eines Strings oder Speicherbereiches
Procedure.l TB_Del(*TB.TB_Struc, *EntryM, Length)
  Protected MD5.s, *c.BYTE, a.l, Pos.l, *Entry.LONG, Entries.l, *s.STRING, Rest.l, *mem
  
  If *TB
    
    If Length
      If Length > #TB_MaxLength : Length = #TB_MaxLength : EndIf
      MD5 = MD5Fingerprint(*EntryM, Length)
    Else
      MD5 = PeekS(*EntryM, #TB_MaxLength)
      MD5 = MD5Fingerprint(@MD5, Len(MD5))
    EndIf
    
    *c = @MD5
    
    a = 0
    Pos = 0
    While *c\b
      a + 1
      If a <= *TB\Accuracy
        Pos * 16 + TB_GetPos(*c\b)
      Else
        Break
      EndIf
      *c + 1
    Wend
    
    *Entry = *TB\pTable + Pos * 4
    If *Entry\l = 0
      ProcedureReturn #False
    Else
      Entries = PeekL(*Entry\l)
      *s = *Entry\l + 4
      For a = 1 To Entries
        If *s\s = MD5
          Rest = Entries - a
          If Rest : CopyMemory(*s + 8, *s, Rest * 8) : EndIf
          Entries - 1
          PokeL(*Entry\l, Entries)
          *mem = ReAllocateMemory(*Entry\l, Entries * 8 + 4)
          If *mem : *Entry\l = *mem : EndIf
          ProcedureReturn #True
        EndIf
        *s + 8
      Next
    EndIf
  EndIf
  
  ProcedureReturn #False
EndProcedure

;Gibt die gesamte HashTable wieder frei
Procedure.l TB_Free(*TB.TB_Struc)
  Protected *Entry.LONG, a.l, *s.STRING, b.l, Entries.l
  
  If *TB
    *Entry = *TB\pTable
    For a = 1 To *TB\Entries
      If *Entry\l
        Entries = PeekL(*Entry\l)
        *s = *Entry\l + 4
        For b = 1 To Entries
          *s\s = ""
          *s + 8
        Next
        FreeMemory(*Entry\l)
      EndIf
      *Entry + 4
    Next
    FreeMemory(*TB)
    ProcedureReturn #True
  EndIf
  ProcedureReturn #False
EndProcedure

;Erstellt eine neue HashTable mit eine festgelegten Genauigkeit
Procedure.l TB_Create(Accuracy.l)
  Protected *TB.TB_Struc, Size.l, a.l
  
  If Accuracy <= 0 : Accuracy = 3 : EndIf
  
  *TB = AllocateMemory(SizeOf(TB_Struc))
  If *TB = 0 : ProcedureReturn #False : EndIf
  *TB\VTable = *TB + 4
  *TB\fTB_EmptySize = @TB_EmptySize()
  *TB\fTB_TotalSize = @TB_TotalSize()
  *TB\fTB_Add       = @TB_Add()
  *TB\fTB_Search    = @TB_Search()
  *TB\fTB_Del       = @TB_Del()
  *TB\fTB_Free      = @TB_Free()
  
  *TB\Accuracy = Accuracy
  Size = 4 : For a = 1 To Accuracy : Size * 16 : Next
  
  *TB\Entries = Size / 4
  
  *TB\pTable = AllocateMemory(Size)
  If *TB\pTable = 0 : FreeMemory(*TB) : ProcedureReturn #False : EndIf
  
  ProcedureReturn *TB
EndProcedure

;Genauigkeiten:
; 0     - (Standard: 3)
; 1     - Ab         16 Einträgen (64     B)
; 2     - Ab        256 Einträgen ( 1,00 kB)
; 3     - Ab      4.096 Einträgen (16,00 kB) (Standard)
; 4     - Ab     65.536 Einträgen ( 0,25 MB)
; 5     - Ab  1.048.576 Einträgen ( 4,00 MB)
; 6     - Ab 16.777.216 Einträgen (64,00 MB)
; ...
*TB.TB = TB_Create(3)

Debug "EmptySize: " + Str(*TB\TB_EmptySize()) + " Bytes"
Debug "TotalSize: " + Str(*TB\TB_TotalSize()) + " Bytes"

Debug "Adding some elements"
*TB\TB_Add(@"eins", 0, 1)
*TB\TB_Add(@"zwei", 0, 2)
*TB\TB_Add(@"drei", 0, 3)
*TB\TB_Add(@"vier", 0, 4)

Debug "TotalSize: " + Str(*TB\TB_TotalSize()) + " Bytes"

Debug *TB\TB_Search(@"zwei", 0)
If *TB\TB_Del(@"zwei", 0) : Debug "'zwei' gelöscht" : EndIf
If *TB\TB_Search(@"zwei", 0) = 0 : Debug "'zwei' nicht mehr auffindbar" : EndIf
Debug *TB\TB_Search(@"drei", 0)

If *TB\TB_Free() : Debug "'Table' gelöscht" : EndIf

ToDo:

Ausgabe mehrerer Werte (Zahlen), wenn ein Fingerprint öfter als einmal vorkommt

Froggerprogger · Beitrag von **Froggerprogger** » 22.09.2005 09:54

Ich habe jetzt den Code nicht ganz durchgearbeitet, aber eine Frage:
Wie löst Du Kollisionen auf ? Also was machst Du, wenn 2 Strings denselben Hashwert haben ?

Beitrag von **NicTheQuick** » 22.09.2005 15:18

Tja, das ist eben das Problem.

Ich hoffe einfach, dass es keine geben wird.
Wenn PB den SH1-Algorithmus nativ unterstützen würde, würde ich den
auch benutzen, da er sicherer ist und dort bisher noch keine Kollisionen
festgestellt wurden.
Mit MD5 gibt es eben immer noch diese geringe Gefahr von Kollisionen,
aber die Wahrscheinlichkeit war mir gering genug um das Risiko
einzugehen.

Für einfache Texte sollte das Verfahren 100%ig sicher sein.
Wer die erste Kollision neben den bereits bekannten entdeckt, kriegt von mir ein Bier ausgegeben.

Beitrag von **Kiffi** » 22.09.2005 23:50

> Tja, das ist eben das Problem.

wieso nimmst Du dann nicht GUIDs? Die dürften so ziemlich unique sein.

Ich weiss allerdings nicht, wie das performance-technisch aussieht.

Grüße ... Kiffi

Froggerprogger · Beitrag von **Froggerprogger** » 23.09.2005 00:24

[Infostream on...]

Beim Hashing gibt es verschiedene Verfahren, die sich insbesondere in den Strategien zum Umgang mit Kollisionen unterscheiden, was dann wiederum Vor- und Nachteile mit sich bringt.
Eine einfache, aber sehr flexible und schnelle Methode ist, in ein Array mit N Plätzen (z.B. 10000) zu hashen, in dem sich an jedem Platz eine eigene (ggf. sogar sortierte) Liste befindet. (Allerdings nicht die PB-Listen, da diese ja global über je einen eigenen Namen definiert werden müssen)
Beim Einfügen wird dann zunächst der Hashwert des Strings berechnet, die entsprechende Liste angesprungen, und dort das Element dann einsortiert.
Solange das Verhältnis von der Anzahl einsortierter Elemente zu N klein ist (der sog. loadfactor), solange ist dies trotz der Listen immernoch superschnell. Außerdem lässt sich ebensoleicht suchen, und Elemente lassen sich ganz einfach wieder entfernen.
Die Hashfunktion muss dabei auch nicht dermaßen kompliziert sein, sondern muss ja lediglich jeden der N möglichen Plätze etwa gleichwahrscheinlich anspringen. Eine solch komplizierte Hashfunktion wie ein MD5-Fingerprint des ganzen Strings ist also nicht notwendig, sondern etwas einfacheres, schnelleres tut es da auch, obwohl es dann manchmal zu Kollisionen kommen kann.

Alternative Maßnahmen sind offene Adressierung, doppeltes Hashen etc. die noch schneller sind (und keine Listen benötigt werden), aber andere Einschränkungen mitbringen (z.B. nur eingeschränkte Löschmöglichkeit und kein Überladen des Tables):
Ein paar Folien als Überblick finden sich hier:
http://wwwcs.upb.de/cs/ag-bloemer/lehre/dua_SS2004/
(zu 'Hashing' und 'Offene Adressierung')

Auch interessant könnten für deine Zwecke Suchbäume sein. Bei diesen kann man im Gegenteil zum Hashtable jederzeit sämtliche Elemente in sortierter Reihenfolge auslesen, wobei das Einfügen/Suchen nur wenig langsamer ist.