String schnell hashen

Gausi · Verfasst: Di 05.01.10 18:50

Ich bin auf der Suche nach einer schnellen Methode, um Strings zu hashen. Die Größe der Hashtabelle sollte so im Bereich zwischen 256 und 1024 liegen. Dabei sollte die möglichst gleichmäßig gefüllt werden. Etwas wie "(string[1] mod 32) x (string[2] mod 32)" ist zwar schnell, aber nicht besonders schön in der Verteilung.

Hintergrund ist der: Ich habe ca. 1.000.000 Strings. Einige kommen dabei sehr selten vor (1-10mal), andere sehr häufig (10.000mal und mehr). Insgesamt dürften es 1000 - 10.000 verschiedene Strings sein. Ich muss wissen, wie oft welcher String vorkommt.

Eine sortierte Liste ist nicht schnell genug, und auch dynamische Suchstrukturen wie AVL-Bäume, Splaybäume oder Skiplisten halte ich für ungeeignet, da hier die sehr häufig vorkommenden Strings nicht schneller gefunden werden können als andere.
Daher will ich die Strings erst hashen, und an den Hash-plätzen in einer (selbstanordnenden) Liste suchen. D.h. Wenn ein Objekt gefunden wurde, rutscht es ein Stück weit nach vorne.

Dafür brauche ich aber eine halbwegs gute und schnelle Hashfunktion für Strings. Hat da jemand Tipps?

_________________
We are, we were and will not be.

Sirke · Beiträge: 208 Erhaltene Danke: 2

Ich habe Hash-Funktionen selbst noch nicht entworfen, sodass ich auch nicht weiß, wie wahrscheinlich es ist mehrere Ansätze zu kombinieren! Bekannte Verfahren zur Hash-Bildung sind die Suche in Wikipedia

MULTIPLIKATIVE METHODE und die bekannte Suche in Wikipedia

QUERSUMME, wobei man eben eine Quersumme der Ergebnisse der Multiplikativen Methode berechnen kann.

Algorithmus:
x besteht aus n Blöcken der Länge 32-bit/64-bit und die MultMeth liefert ebenfalls eine 32-bit/64-bit Zahl zurück, dann ist die Hashfunktion:
H(x) = ( MultMeth( x[n] ) + ... + MultMeth( x[0] ) ) mod 2^32 bzw. mod 2^64

Was hält dich von einer kryptographischen Hash-Funktion ab?

Flamefire · Verfasst: Di 05.01.10 20:49

mal so ganz intuitiv: homophone verschlüsselung ;-)

Du willst, das das ganz gleichverteilt ist?
Dann bilde die Quersumme der homophonen Verschlüsselung.
Also nimm für jeden Buchstaben die Häufigkeit aus Wikipedia und addiere die zusammen.
Die Häufigkeiten in einem statischen Array und du hast eine sehr schnelle Methode:

Je Buchstabe:
- 1 Subtraktion (zum bestimmen des Index)
- 1 Multiplikation(integer), Addition, Speicherzugriff (zum lesen des Wertes)
- 1 Addition (auf den Zwischenwert)

Fertig.
Überläufe sollte ok sein, wenn du Unsigned Werte verwendest. Das spart das mod bzw den Vergleich.

Astat · Verfasst: Di 05.01.10 21:02

Zitat:

...Hat da wer...
...Methode, um Strings zu hashen.....
...Dafür brauche ich aber eine halbwegs gute und schnelle Hashfunktion für Strings. Hat da jemand Tipps?

Jupp, sogar Threadsave!

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:

unit HashStrings;

interface

uses
  windows, classes, sysutils;

type
  PPHashStringItem = ^PHashStringItem;
  PHashStringItem = ^THashStringItem;
  THashStringItem = record
    Next  : PHashStringItem;
    Key   : string;
    Value : pointer;
  end;

  TStringHash = class
  private
    FLock: TRTLCriticalSection;
    Buckets: array of PHashStringItem;
    function Find(const Key: string): PPHashStringItem;
    function HashOf(const Key: string): Cardinal;
  public
    constructor Create(Size: integer = 256);
    destructor Destroy; override;
    procedure Add(const Key: string; Value: pointer);
    procedure Clear;
    procedure Remove(const Key: string);
    function Modify(const Key: string; Value: pointer): Boolean;
    function ValueOf(const Key: string): pointer;
  end;

implementation

procedure TStringHash.Add(const Key: string; Value: pointer);
var
  Hash: integer;
  Bucket: PHashStringItem;
begin
  EnterCriticalSection(FLock);
  try
    Hash := HashOf(Key) mod Cardinal(Length(Buckets));
    New(Bucket);
    Bucket^.Key := Key;
    Bucket^.Value := Value;
    Bucket^.Next := Buckets[Hash];
    Buckets[Hash] := Bucket;
  finally
    LeaveCriticalSection(FLock);
  end;
end;

procedure TStringHash.Clear;
var
  I: integer;
  P, N: PHashStringItem;
begin
  EnterCriticalSection(FLock);
  try
    for I := 0 to Length(Buckets) - 1 do begin
      P := Buckets[I];
      while P <> nil do begin
        N := P^.Next;
        Dispose(P);
        P := N;
      end;
      Buckets[I] := nil;
    end;
  finally
    LeaveCriticalSection(FLock);
  end;
end;

constructor TStringHash.Create(Size: integer);
begin
  inherited Create;
  InitializeCriticalSection(FLock);
  SetLength(Buckets, Size);
end;

destructor TStringHash.Destroy;
begin
  Clear;
  DeleteCriticalSection(FLock);
  inherited;
end;

function TStringHash.Find(const Key: string): PPHashStringItem;
var
  Hash: integer;
begin
  EnterCriticalSection(FLock);
  try
    Hash := HashOf(Key) mod Cardinal(Length(Buckets));
    Result := @Buckets[Hash];
    while Result^ <> nil do begin
      if Result^.Key = Key then Exit
        else Result := @Result^.Next;
    end;
  finally
    LeaveCriticalSection(FLock);
  end;
end;

function TStringHash.HashOf(const Key: string): Cardinal;
var
  I: integer;
begin
  EnterCriticalSection(FLock);
  try
    Result := 0;
    for I := 1 to Length(Key) do
      Result := ((Result shl 2) or (Result shr (SizeOf(Result) * 8 - 2))) xor
        Ord(Key[I]);
  finally
    LeaveCriticalSection(FLock);
  end;
end;

function TStringHash.Modify(const Key: string; Value: pointer): Boolean;
var
  P: PHashStringItem;
begin
  EnterCriticalSection(FLock);
  try
    P := Find(Key)^;
    if P <> nil then begin
      Result := True;
      P^.Value := Value;
    end else
      Result := False;
  finally
    LeaveCriticalSection(FLock);
  end;
end;

procedure TStringHash.Remove(const Key: string);
var
  P: PHashStringItem;
  Prev: PPHashStringItem;
begin
  EnterCriticalSection(FLock);
  try
    Prev := Find(Key);
    P := Prev^;
    if P <> nil then begin
      Prev^ := P^.Next;
      Dispose(P);
    end;
  finally
    LeaveCriticalSection(FLock);
  end;
end;

function TStringHash.ValueOf(const Key: string): pointer;
var
  P: PHashStringItem;
begin
  EnterCriticalSection(FLock);

  try
    P := Find(Key)^;
    if P <> nil then
      Result := P^.Value else
        Result := nil;
  finally
    LeaveCriticalSection(FLock);
  end;
end;

end.

lg. Astat

BenBE · Verfasst: Di 05.01.10 21:25

Wenn ich dich richtig verstehe, willst du eine Hashtable mit einer angehängten LRU-basierten Liste bauen?

Als Hash-Algo würde ich dir dabei CRC32 empfehlen (es gibt inzwischen Varianten, die bis zu 32 Bit mit einem Schlag können), wobei auch die übliche 1-Byte-je-Zyklus-Variante mit einem einfachen XOR auskommt. Dabei einfach den Hash mit ner Maske auf die Größe deiner Hashtable (Power of Two) begrenzen.

Java nutzt intern ein abwechselndes Multiplizieren mit 7 und 13 IIRC, was aber um einiges langsamer ist, als nen CRC32 zu berechnen.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

alzaimar · Verfasst: Di 05.01.10 21:43

Hi,

ich hab in meiner Stringdictionary (www.delphipraxis.net...ht=tstringdictionary) anfangs auch mit CRC gehashed, das war aber wesentlich langsamer also mit dem ELF-Hash, mit dem ich ganz gute Erfahrungen gemacht habe.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

Function HashFromStr(Const Value: String): Cardinal; // ELF-Hash
Var
  i: Integer;
  x: Cardinal;
Begin
  Result := 0;
  For i := 1 To Length(Value) Do Begin
    Result := (Result Shl 4) + Ord(Value[i]);
    x := Result And $F0000000;
    If (x <> 0) Then
      Result := Result Xor (x Shr 24);
    Result := Result And (Not x);
  End;
End;

Ich würde mal eine SkipList oder einen Trie (DAWG) versuchen (TDawg von negaH, aka Hagen Redmann), das sollte noch schneller sein. Auch ein Judy-Array (en.wikipedia.org/wiki/Judy_array) könnte einen Versuch wert sein, das gibts aber leider nicht in Delphi.

_________________
Na denn, dann. Bis dann, denn.

Gausi · Verfasst: Di 05.01.10 22:08

Danke schonmal für die Anregungen.

Threadsafe brauche ich das nicht. Das ganze soll innerhalb von 1-5 Sekunden passieren (inkl. einiger anderer Dinge), und in dieser Zeit darf die GUI kurzzeitig blockiert sein.

Direkt testen kann ich die Verfahren noch nicht, da ich bisher "erst" eine Datenmenge von ca. 150.000 Strings habe, die aber um knapp den Faktor 10 anwachsen wird. Die Menge der "UniqueStrings" wird vermutlich weitaus weniger stark anwachsen (hoffe ich, sonst bekomme ich vermutlich ein ernsthaftes Problem).
Wenn ich die Methoden implementiert habe, um die anderen Strings zu bekommen (und zu speichern, denn das einmalige besorgen dieser Strings wird vermutlich ein paar Stunden dauern), dann werde ich mal einige der Verfahren hier testen. Es könnte aber auch sein, dass der Flaschenhals noch woanders liegt. ;-)

@BenBE: LRU nicht direkt. Da es höchst unwahrscheinlich ist, das zweimal hintereinander derselbe String gesucht wird, tendiere ich eher zu "tausche mit Vorgänger, falls dessen Count kleiner ist". Das geht auch mit TObjectlist in O(1). ;-)

@alzaimar: Skiplist glaube ich nicht, dass die in meinem recht speziellen Fall schneller ist. Da braucht jeder Zugriff ja O(log(n)), wenn ich das richtig sehe. Bei den anderen Verfahren prinzipiell ja auch, da ändern sich ja nur die Konstanten durch unterschiedlich dicken Overhead.
Von den 150.000 Strings und 10.000 Uniquestrings, die ich zur Zeit habe, fallen ca. 100.000 auf die Top 100 Uniquestrings. Die würde ich gerne in O(1) finden können. Daher die Idee mit den Hashs;-)
Deine Testsuite mit verschiedenen Suchstrukturen habe ich mir aber auch schon angeschaut.

_________________
We are, we were and will not be.

alzaimar · Verfasst: Di 05.01.10 22:24

Gausi hat folgendes geschrieben :

@alzaimar: Skiplist glaube ich nicht, dass die in meinem recht speziellen Fall schneller ist. Da braucht jeder Zugriff ja O(log(n)), wenn ich das richtig sehe.

Probieren geht über studieren. In der Praxis ist eine Skiplist so schnell wie eine Hashmap, jedenfalls bei mir (Habs eben mal ausprobiert: 150.000 Strings suchen und einfügen in einer Verteilung ähnlich wie deiner: 250ms auf meinem Laptop).

Gausi hat folgendes geschrieben :

Bei den anderen Verfahren prinzipiell ja auch, da ändern sich ja nur die Konstanten durch unterschiedlich dicken Overhead.

Der DAWG hat bisher alles in den Schatten gestellt, jedenfalls so lange, bis der Speicher voll war.

Gausi hat folgendes geschrieben :

Deine Testsuite mit verschiedenen Suchstrukturen habe ich mir aber auch schon angeschaut.

Dann solltest Du doch wissen, das eine Skiplist sich ein einen Sch***dreck um O(log n) schert. :mrgreen:

_________________
Na denn, dann. Bis dann, denn.

dummzeuch · Verfasst: Di 05.01.10 22:28

Gausi hat folgendes geschrieben :

Danke schonmal für die Anregungen. :D

Threadsafe brauche ich das nicht. Das ganze soll innerhalb von 1-5 Sekunden passieren (inkl. einiger anderer Dinge), und in dieser Zeit darf die GUI kurzzeitig blockiert sein.

Mir ist gerade wieder diese Artikelserie zum Thema StringPools eingefallen:

blog.gurock.com/post...th-string-pools/450/

Insgesamt ganz nett, wenn auch kein kompletter Delphi Code angegeben wird. In Teil 3 gibt es aber eine Hash-Funktion sowie Links auf weitere, die Dich vielleicht interessieren koennten.

twm

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme