Bob Jenkins Hash senza distinzione tra maiuscole e minuscole?

Question

Esiste una variante senza distinzione tra maiuscole e minuscole della funzione hash di Bob Jenkins?

Generics.Defaults.BobJenkinsHash

fornisce una funzione hash veloce. Sfortunatamente non può essere utilizzato in combinazione con una funzione di confronto senza distinzione tra maiuscole e minuscole in questo modo

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;

Questo perché TDictionary confronta prima i codici hash e quindi utilizza il comparatore fornito per verificare l'uguaglianza.

Naturalmente potrei usare UpperCase nella mia funzione GetHashCode , ma mi chiedevo se sarebbe più veloce se potessi in qualche modo modificare la funzione hash stessa.

Answer 1

No, non esiste una versione invariante del caso della funzione hash. Maiuscole o minuscole tutte le stringhe prima di passarle alla funzione hash.

Answer 2

Sarebbe leggermente più veloce, ma danneggia molto la tua manutenibilità. Raramente c'è una buona ragione per questo tipo di micro-ottimizzazione. Converti le stringhe in lettere minuscole o maiuscole prima di eseguire l'hashing come hai suggerito.

  

" Dovremmo dimenticare piccoli   efficienze, dire circa il 97% del   tempo: l'ottimizzazione prematura è il   radice di tutti i mali. Eppure non dovremmo   trasmettere le nostre opportunità in questo   critico 3%. Sarà un buon programmatore   non lasciarsi cullare dalla compiacenza da parte di tali   ragionamento, sarà saggio guardare   attentamente al codice critico; ma   solo dopo che quel codice è stato   identificato " - Donald Knuth

Answer 3

IMO l'intera domanda è sbagliata. Per citare l'articolo di Wikipedia sulle funzioni hash :

  

Una funzione hash è qualsiasi procedura o funzione matematica ben definita che converte una grande quantità di dati, possibilmente di dimensioni variabili, in un piccolo dato, di solito un singolo numero intero che può servire da indice a un array.

Prendi nota della "quantità di dati" - non è stato specificato alcun tipo e in effetti la funzione hash Bob Jenkins ha un parametro non tipizzato const Data che punta ai dati da sottoporre a hash. Poiché i dati di input non sono necessariamente una sequenza di caratteri, non è possibile calcolare una "distinzione tra maiuscole e minuscole" valore hash. E anche se fosse una sequenza di caratteri, la maiuscola o la minuscola dipenderebbero dal set di caratteri e dalla codifica. Quindi avresti bisogno di avere diverse funzioni hash per stringhe ASCII, stringhe codificate UTF-8, stringhe codificate LE UTF-16, ... (ottieni l'idea).

Answer 4

Avevo anche bisogno di una tale funzione in un progetto. Hash one-to-time di Bob Jenkin:

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;        

Se è impostato asciionly, dovrebbe anche dare lo stesso hash per le stringhe utf-8 e latin1.

Non dimenticare di disabilitare il controllo di overflow.