Хэш Боба Дженкинса без учета регистра?

Question

Существует ли вариант хэш-функции Боба Дженкинса без учета регистра?

Generics.Defaults.BobJenkinsHash

обеспечивает быструю хэш-функцию.К сожалению, он не может быть использован в сочетании с нечувствительной к регистру функцией сравнения следующим образом

TCustomStringComparer = class (TEqualityComparer <String>)
  function Equals(const Left, Right: String): Boolean; override;
  function GetHashCode(const Value: String): Integer; override;
end;
function TCustomStringComparer.Equals (const Left, Right : String) : Boolean;
begin
  Result := CompareText (Left, Right) = 0;
end;
function TCustomStringComparer.GetHashCode (const Value : String) : Integer;
begin
  Result := Generics.Defaults.BobJenkinsHash (Value [1], Length (Value) * SizeOf (Char), 0);
end;

Это связано с тем, что TDictionary сначала сравнивает хэш-коды, а затем использует предоставленный компаратор при проверке на равенство.

Конечно, я мог бы использовать заглавные буквы в своем GetHashCode функция, но я подумал, было бы быстрее, если бы я мог каким-то образом изменить саму хэш-функцию.

Answer 1

Нет, не существует инвариантной к регистру версии хэш-функции. Все строки в нижнем или верхнем регистре перед передачей их хэш-функции.

Answer 2

Это было бы немного быстрее, но сильно повредило вашей поддержке. Существует редко хорошая причина для этого типа микрооптимизации. Просто преобразуйте строки в нижний или верхний регистр перед хэшированием, как вы предложили.

  

" Мы должны забыть о маленьких   эффективность, скажем, около 97%   время: преждевременная оптимизация   корень всех зол. Все же мы не должны   упустить наши возможности в этом   критический 3%. Хороший программист   не успокаиваться такими   рассуждения, он будет мудрым, чтобы посмотреть   внимательно на критический код; но   только после того, как этот код был   идентифицированы & Quot; - Дональд Кнут

Answer 3

ИМО, весь вопрос неправильный.Процитирую Статья в Википедии о хэш-функциях:

A хэш-функция это любая четко определенная процедура или математическая функция, которая преобразует большой объем данных, возможно, переменного размера, в небольшие данные, обычно одно целое число, которое может служить индексом массива.

Обратите внимание на "объем данных" - тип не указан, и действительно, хэш-функция Боба Дженкинса имеет нетипизированный параметр const Data указывает на данные, которые должны быть хэшированы.Поскольку входные данные не обязательно представляют собой последовательность символов, нет способа вычислить хэш-значение без учета регистра.И даже если бы это была последовательность символов - заглавный или строчный регистр зависел бы от набора символов и кодировки.Таким образом, вам понадобятся разные хэш-функции для строк ASCII, строк в кодировке UTF-8, строк в кодировке UTF-16 LE, ...(вы поняли идею).

Answer 4

Мне также нужна была такая функция в проекте. Единственный хэш Боба Дженкина:

function hash(const s: string): cardinal;
var
  p, last: PByte;
begin
  if s = '' then exit(1);
  p := pbyte(pointer(s));
  last := p + length(s);
  result := 0;
  while p < last do begin
    if {$ifdef asciionly}p^ < 128{$else}true{$endif}  then begin
      result := result + p^;
      if (p^ >= ord('a')) and (p^ <= ord('z')) then result := result - ord('a') + ord('A');
      result := result + (result shl 10);
      result := result xor (result shr 6);
    end;
    inc(p);
  end;

  result := result + (result shl 3);
  result := result xor (result shr 11);
  result := result + (result shl 15);
end;        

Если asciionly установлен, он также должен давать одинаковый хеш для строк utf-8 и latin1.

Не забудьте отключить проверку переполнения.