Без учета регистра Боб Дженкинс Хэш? - PullRequest
Новая
       7

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

1 голос
/ 30 октября 2009

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

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 сначала сравнивает хеш-коды, а затем использует предоставленный компаратор при проверке на равенство.

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

Ответы [ 4 ]

8 голосов
/ 30 октября 2009

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

3 голосов
/ 30 октября 2009

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

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

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

3 голосов
/ 30 октября 2009

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

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

0 голосов
/ 22 октября 2016

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

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.

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

...