How to get hash of entire TStringList? lazarus / 21-General ---------------------------------------------------------------------- AlexTP · 2024-12-07 20:15 In CudaText, I want to calc some hash (any good algo, stringlist usually has 10...1000 items) for entire StringList. If hash is the same on the next call of menu-like-dialog, editor can keep old filter text in the menu-like-dialog. If hash is different, dialog will clear last filter-text. Pls show an example how to calc the hash? THashedStringList is not ok here - it calcs hash per each stringlist line. Getting of hash of List.Text is not nice, better not to calculate List.Text. ---------------------------------------------------------------------- Warfley · 2024-12-07 20:30 Using the hash function that java uses for strings: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i function AddToHash(AHash: Integer; AValue: Integer): Integer; inline;begin  Result := AHash*31 + AValue;end; function HashString(const AString: String): Integer;var  i: Integer;begin  Result := 0;  for i := Length(AString) downto 1 do    Result := AddToHash(Result, Ord(AString[i]));end; function HashStrings(AStrings: TStrings): Integer;var  i: Integer;begin  Result := 0;  for i := AStrings.Count-1 downto 0 do    Result := AddToHash(Result, HashString(AStrings[i]));end; ---------------------------------------------------------------------- AlexTP · 2024-12-08 08:58 Thanks, it is good. I only need to add AddToHash(#10) to respect EOLs. Are you sure the algo is so simple? x*31+y. And, it is 32-bit int. How to use Int64? ---------------------------------------------------------------------- Thaddy · 2024-12-08 09:54 because it is a multiplication it is likely that it gets expanded to 64 bit anyway. Otherwise it would raise a rangecheck error and/or overflow. There are other simple hashes, like shift/mods, but this is indeed used in java. Here is a simple hash without multiplication, stays 32 bit:Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i function SimpleHash(const S: string): Integer;inline;var  i: Integer;begin  result := 0;  for i := 1 to Length(S) do  begin    result := (result shl 5) or (result shr 27);     result := result + Ord(S[i]);  end;end; In most cases this is also faster and has similar characteristics. I wonder why you do not want to use the text property, because that may still be faster than per line hashing + addition. ---------------------------------------------------------------------- AlexTP · 2024-12-08 10:49 @Thaddy, thanks. I like that I won't have overflow. I can adapt your code to stringlist. ---------------------------------------------------------------------- Fibonacci · 2024-12-08 11:07 This may be even better, and similar speed Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i function fletcher32(data: pointer; len: dword): dword;var  s0, s1: word;  i: integer;begin  s0 := 0;  s1 := 0;  i := 0;  while i < len do begin    if i+2 > len then s0 := (s0+pbyte(data+i)^) mod 65535    else s0 := (s0+pword(data+i)^) mod 65535;    s1 := (s0+s1) mod 65535;    inc(i, 2);  end;  result := s1 shl 16 or s0;end; ---------------------------------------------------------------------- Thaddy · 2024-12-08 11:12 No, because of the modulo operation it is always slower than 2 shifts + 1 or + 1 addition. These are all i cycle operations. Mod is extremely costly and depending on cpu can take between 7 and 14 cycles. If you see a mod, it means it is slow. Btw, forgot to add inline. Done. ---------------------------------------------------------------------- Fibonacci · 2024-12-08 11:16 Quote from: Thaddy on December 08, 2024, 12:12:00 pmNo, because of the modulo operation it is always slower than 2 shifts + 1 or + 1 addition. Mod is extremely costly. Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   message := 'test';   q := GetTickCount64;  for i := 1 to 100000000 do d := fletcher32(@message[1], length(message));  writeln('fletcher32 took ms ', GetTickCount64-q);   q := GetTickCount64;  for i := 1 to 100000000 do d := SimpleHash(message);  writeln('SimpleHash took ms ', GetTickCount64-q);   writeln;   message := 'a little longer test string';   q := GetTickCount64;  for i := 1 to 100000000 do d := fletcher32(@message[1], length(message));  writeln('fletcher32 took ms ', GetTickCount64-q);   q := GetTickCount64;  for i := 1 to 100000000 do d := SimpleHash(message);  writeln('SimpleHash took ms ', GetTickCount64-q); fletcher32 took ms 672 SimpleHash took ms 625 fletcher32 took ms 4359 SimpleHash took ms 7078 Quote from: Thaddy on December 08, 2024, 12:12:00 pmBtw, forgot to add inline. Done. Both inlined fletcher32 took ms 625 SimpleHash took ms 328 fletcher32 took ms 4219 SimpleHash took ms 3812 ---------------------------------------------------------------------- Warfley · 2024-12-08 11:22 Quote from: Fibonacci on December 08, 2024, 12:07:42 pmThis may be even better, and similar speed And you get a free buffer overflow if len is not even  Quote from: Thaddy on December 08, 2024, 10:54:10 ambecause it is a multiplication it is likely that it gets expanded to 64 bit anyway. Otherwise it would raise a rangecheck error and/or overflow. There are other simple hashes, like shift/mods, but this is indeed used in java. Here is a simple hash without multiplication, stays 32 bit:Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i function SimpleHash(const S: string): Integer;inline;var  i: Integer;begin  result := 0;  for i := 1 to Length(S) do  begin    result := (result shl 5) or (result shr 27);     result := result + Ord(S[i]);  end;end; In most cases this is also faster and has similar characteristics. I wonder why you do not want to use the text property, because that may still be faster than per line hashing + addition. Well you also get an overflow here (or over shift to be precise). But yeah this is also a very common and easy hashing algorithm, I like the java one because it's easy to remember. In both cases overflows are expected (it's a hashing algorithm so information loss is inevitable) ---------------------------------------------------------------------- Thaddy · 2024-12-08 11:27 I misread. The mod is not per line. ---------------------------------------------------------------------- Fibonacci · 2024-12-08 11:28 Quote from: Warfley on December 08, 2024, 12:22:11 pmAnd you get a free buffer overflow if len is not even  Where? ---------------------------------------------------------------------- Warfley · 2024-12-08 11:29 Oh mistead the if statement, my bad 😅 ---------------------------------------------------------------------- Fibonacci · 2024-12-08 11:30 ---------------------------------------------------------------------- bytebites · 2024-12-08 11:32 Replace mod with and? ---------------------------------------------------------------------- Thaddy · 2024-12-08 11:35 From the literature I see that Fletcher is a checksum and not a hash. I will check out the collsion probabilities as compared to simplehash, which is a hash and not a checksum. ---------------------------------------------------------------------- Warfley · 2024-12-08 12:30 Compared to normal hashing algorithms, Fletcher does not seem to spread the result. Simple hash scrambles the bits around with the shift and the java hash basically does 4 shifts with that multiplication. While Fletcher just does additions. So if all values are in a similar range (as is typical in ASCII text) meaning small differences in the text will give only small differences in the result. While this may not result in more collisions (but not really sure about that), it may result in less uniform usage in a hashmap.