Qual è la migliore funzione di hash a 32 bit per stringhe relativamente corte?Qual è la migliore funzione di hash a 32 bit per le stringhe corte (nomi di tag)?
Le stringhe sono nomi di tag composti da lettere inglesi, numeri, spazi e alcuni caratteri aggiuntivi (#, $, ., ...). Ad esempio: Unit testing, C# 2.0.
Sto cercando "migliore" come in "collisioni minime", le prestazioni non sono importanti per i miei obiettivi.
Se le prestazioni non sono importanti, è sufficiente prendere un hash sicuro come MD5 o SHA1 e troncarne l'output a 32 bit. Questo ti darà una distribuzione di codici hash che è indistinguibile da casuale.
md5 è perfetto per questo scenario –
MD4 (vedi http://tools.ietf.org/html/rfc1320) potrebbe essere ancora migliore, poiché è leggermente più semplice da implementare rispetto a MD5. Si noti che né MD4 né MD5 sono indistinguibili da casuali (entrambi sono stati "crittograficamente interrotti") ma sono comunque abbastanza vicini per lo scopo in questione. –
Pensi che avrebbe avuto meno collisioni della risposta di Nick D?Sono un po 'indeciso su cosa approvare/utilizzare. –
io non sono sicuro se è la scelta migliore, ma qui è una funzione di hash per le stringhe: (. Tabelle hash, pg 57)
/* hash: compute hash value of string */
unsigned int hash(char *str)
{
unsigned int h;
unsigned char *p;
h = 0;
for (p = (unsigned char*)str; *p != '\0'; p++)
h = MULTIPLIER * h + *p;
return h; // or, h % ARRAY_SIZE;
}
Empiricamente, i valori 31 e 37 hanno dimostrato di essere buone scelte per il moltiplicatore in una funzione di hash per stringhe ASCII.
Sì, usiamo questa funzione di hashing esatta con MULTIPLIER = 37 per stringhe e percorsi. Funziona bene per noi e devo ancora riscontrare un problema di collisione anche dopo 2 anni (ovviamente non c'è alcuna garanzia che non lo faremo) – zebrabox
Questo sicuramente sembra abbastanza semplice. Qualche idea sul perché FNV è stato creato se funziona un approccio molto più semplice? –
@Andrey Shchekin, utilizzo l'hash FNV quando gestisco i byte grezzi (blob). Forse, la funzione sopra riportata produce risultati migliori in particolare con le stringhe. Non ne sono sicuro. –
Si potrebbe verificare murmurhash2. È veloce, anche per le stringhe più piccole, e ha una buona fase finale di mixaggio, quindi è anche ben miscelato per stringhe molto piccole.
Se è raro che gli utenti aggiungano nuovi tag, è possibile utilizzare un cancelletto perfetto (http://en.wikipedia.org/wiki/Perfect_hash_function) che viene ricalcolato ogni volta che viene aggiunto un nuovo tag. Certamente, senza conoscere il problema che stai veramente cercando di risolvere, è una congettura per capire cosa potresti fare.
funzione hash Uso MaPrime2c:
static const unsigned char sTable[256] =
{
0xa3,0xd7,0x09,0x83,0xf8,0x48,0xf6,0xf4,0xb3,0x21,0x15,0x78,0x99,0xb1,0xaf,0xf9,
0xe7,0x2d,0x4d,0x8a,0xce,0x4c,0xca,0x2e,0x52,0x95,0xd9,0x1e,0x4e,0x38,0x44,0x28,
0x0a,0xdf,0x02,0xa0,0x17,0xf1,0x60,0x68,0x12,0xb7,0x7a,0xc3,0xe9,0xfa,0x3d,0x53,
0x96,0x84,0x6b,0xba,0xf2,0x63,0x9a,0x19,0x7c,0xae,0xe5,0xf5,0xf7,0x16,0x6a,0xa2,
0x39,0xb6,0x7b,0x0f,0xc1,0x93,0x81,0x1b,0xee,0xb4,0x1a,0xea,0xd0,0x91,0x2f,0xb8,
0x55,0xb9,0xda,0x85,0x3f,0x41,0xbf,0xe0,0x5a,0x58,0x80,0x5f,0x66,0x0b,0xd8,0x90,
0x35,0xd5,0xc0,0xa7,0x33,0x06,0x65,0x69,0x45,0x00,0x94,0x56,0x6d,0x98,0x9b,0x76,
0x97,0xfc,0xb2,0xc2,0xb0,0xfe,0xdb,0x20,0xe1,0xeb,0xd6,0xe4,0xdd,0x47,0x4a,0x1d,
0x42,0xed,0x9e,0x6e,0x49,0x3c,0xcd,0x43,0x27,0xd2,0x07,0xd4,0xde,0xc7,0x67,0x18,
0x89,0xcb,0x30,0x1f,0x8d,0xc6,0x8f,0xaa,0xc8,0x74,0xdc,0xc9,0x5d,0x5c,0x31,0xa4,
0x70,0x88,0x61,0x2c,0x9f,0x0d,0x2b,0x87,0x50,0x82,0x54,0x64,0x26,0x7d,0x03,0x40,
0x34,0x4b,0x1c,0x73,0xd1,0xc4,0xfd,0x3b,0xcc,0xfb,0x7f,0xab,0xe6,0x3e,0x5b,0xa5,
0xad,0x04,0x23,0x9c,0x14,0x51,0x22,0xf0,0x29,0x79,0x71,0x7e,0xff,0x8c,0x0e,0xe2,
0x0c,0xef,0xbc,0x72,0x75,0x6f,0x37,0xa1,0xec,0xd3,0x8e,0x62,0x8b,0x86,0x10,0xe8,
0x08,0x77,0x11,0xbe,0x92,0x4f,0x24,0xc5,0x32,0x36,0x9d,0xcf,0xf3,0xa6,0xbb,0xac,
0x5e,0x6c,0xa9,0x13,0x57,0x25,0xb5,0xe3,0xbd,0xa8,0x3a,0x01,0x05,0x59,0x2a,0x46
};
#define PRIME_MULT 1717
unsigned int
maPrime2cHash (unsigned char *str, unsigned int len)
{
unsigned int hash = len, i;
for (i = 0; i != len; i++, str++)
{
hash ^= sTable[(*str + i) & 255];
hash = hash * PRIME_MULT;
}
return hash;
}
e guardare www.amsoftware.narod.ru/algo2.html per MaFastPrime, MaRushPrime, ecc test.
Se il programma ha bisogno di comunicare con un altro sistema, è meglio utilizzare un algoritmo ben noto. Il modo rapido & è utilizzando prima Diversi caratteri dell'hash md5. Non hai bisogno di trascorrere ore o giorni per inventare ruote nel tuo progetto.
Lo svantaggio è molto più elevato per le collisioni. Tuttavia, se il tuo hash è per una sessione con timestamp o una breve durata. Non c'è nessun problema a usarlo.
Questo dipende dal vostro hardware. Su hardware moderno, ad esempio Intel/AMD con SSE4.2 o arm7, è necessario utilizzare gli intrinseci interni _mm_crc32_uxx, poiché sono ottimali per le stringhe brevi. (Anche per chiavi lunghe, ma meglio usare la versione con thread di Adler, come in zlib)
Su hardware vecchio o sconosciuto, sonda di runtime per la funzionalità SSE4.2 o CRC32 o semplicemente usarne una se l'hash della buona semplice funzioni. Per esempio.Murmur2 o Città
Una panoramica delle qualità e delle prestazioni è qui: https://github.com/rurban/smhasher#smhasher
Ci sono anche tutti gli adempimenti. Favorito sono https://github.com/rurban/smhasher/blob/master/crc32_hw.c e https://github.com/rurban/smhasher/blob/master/MurmurHash2.cpp
Se conoscete le chiavi in anticipo, utilizzare una perfetta hash , non una funzione di hash. Per esempio. gperf o il mio phash: https://github.com/rurban/Perfect-Hash#name
generazione di hash Oggi perfetta tramite un compilatore C è così veloce, si può anche crearli al volo, e dynaload esso.
: Murmur2 e City non possono più essere definiti semplici funzioni hash. Il più veloce sarebbe FNV1 o CRC32-C, meglio sarebbe Metro o Farmhash. – rurban
Mi dispiace per la risposta molto tarda su questo. All'inizio di quest'anno ho composto una pagina dal titolo Hashing Short Strings che potrebbe essere utile in questa discussione. In sintesi, ho scoperto che CRC-32 e FNV-1a sono superiori per le stringhe brevi di hashing. Sono efficienti e hanno prodotto hash largamente distribuiti e senza collisioni nei miei test. Sono stato sorpreso di scoprire che MD5, SHA-1 e SHA-3 producevano un piccolo numero di collisioni quando l'uscita era piegata a 32-bit da.
possibile duplicato http://stackoverflow.com/questions/251346/best-hashing-algorithm-in-terms-of-hash-collisions-and-performance –
Non del tutto, perché la mia domanda è più specifica in termini di hash size e ignora le prestazioni. Inoltre non sto solo cercando la funzione hash _a_, sto cercando una scelta significativa - so che ci sono CRC32 e FNV32, ma quale è meglio per il mio dominio? –
Il tuo elenco di tag è fisso su un set di stringhe o crescerà in modo dinamico nel tempo? –