Una breve introduzione al problema: sto lavorando con un piccolo database in cui ho una tabella di stringhe (URL web, per essere precisi) come coppie: hash|string . Un'altra tabella fa riferimento a queste stringhe per hash, quindi sto risparmiando molto spazio e alcuni cicli della CPU usando gli hash (un identificativo compatto di una stringa). Sapevo che le collisioni sarebbero state un problema con insiemi di dati di grandi dimensioni, ma non mi aspettavo di iniziare a battere collisioni non appena avevo 281 000 stringhe univoche per un hash a 64 bit.
Quindi, ho bisogno di una funzione simile a un hash che non deve essere crittografica e non ha nemmeno bisogno di essere distribuita uniformemente. Potrebbe essere di lunghezza variabile, ma vorrei prima spremere il più possibile da 64 bit di entropia.
Idea n. 1: usa il numero di posizione di una stringa nella tabella come ID univoco. Funzionerebbe, ma non mi piace come si basa su un singolo contatore globale per l'assegnazione di un numero incrementato. Se non altro, è un punto di congestione per un sistema distribuito con più scrittori e lettori.
Idea n. 2: comprime le stringhe. Ma come? Apparentemente, dovrebbe essere un algoritmo di compressione con un dizionario pre-calcolato. Anche allora, quanti personaggi, in media, sarebbe possibile schiacciare a 64 bit?
Idea n. 2.5: comprimibile se comprimibile per il numero di bit di destinazione, altrimenti hash.
Si noti che con "hash-like" intendo che la funzione non deve essere reversibile.