Sto cercando un modo per creare un ID a 16 bit con circa 100 bit di dati. La soluzione dovrebbe essere facile da implementare, o dovrebbe essere già implementata in c ++, dovrebbe essere rapida da valutare e, soprattutto, i valori dell'ID dovrebbero essere distribuiti uniformemente, vale a dire che un valore non dovrebbe avere una maggiore possibilità di essere preso più di un altro.
Come accennato in la domanda Rook linked, 16bits è molto molto debole, riducendo Da 100 a 16 porta a ~ 6 possibili collisioni per hash.
Sei sicuro di aver bisogno di un hash per questo? 16 bit è sufficiente per essere memorizzato in un numero intero e potrebbe essere semplicemente incrementato se hai solo bisogno di un modo per identificare un oggetto (limitato a 65536).
Se tuttavia si desidera utilizzare una funzione di hash, si potrebbe provare a utilizzare qualcosa di molto semplice come Pearson hashing che produrrà un hash a 8 bit.
h := 0
for each c in C loop
index := h xor c
h := T[index]
end loop
return h
Cito Wikipedia, i vantaggi di questa funzione sono:
L'adattamento a 16 bit non dovrebbe essere troppo difficile. Ad esempio, questa pagina fornisce un esempio di adattamento ma penso che l'autore dimentichi di cambiare la dimensione del tavolo in 65535, il codice sarebbe:
static unsigned short T[] = {
// The values 0..65535 shuffled into random order.
};
static inline unsigned hashOf(unsigned h,const char* s) {
for (int c = *s++; c; c = *s++) {
h = T[h ^ (65535 & c)];
}
return h;
}
Leggi altre domande sui tag hash