Hai una buona funzione hash per una tabella hash C ++?

Question

Ho bisogno di un'implementazione della funzione hash orientata alle prestazioni in C ++ per una tabella hash che codificherò. Mi sono già guardato intorno e ho trovato solo domande che chiedevano cos'è una buona funzione hash & Quot; in generale & Quot ;. Ho considerato CRC32 (ma dove trovare una buona implementazione?) E alcuni algoritmi di crittografia. La mia tabella, tuttavia, ha requisiti molto specifici.

Ecco come sarà la tabella:

100,000 items max
200,000 capacity (so the load is 0.5)
hashing a 6-character string which is a part of English sentence
     examples: "become"    "and he"    ", not "

La priorità numero uno della mia tabella hash è la ricerca rapida (recupero). L'inserimento rapido non è importante, ma verrà fornito con una ricerca rapida. La cancellazione non è importante e il re-hashing non è qualcosa che esaminerò. Per gestire le collisioni, probabilmente userò concatenamento separato come descritto qui . Ho già esaminato questo articolo , ma vorrei un parere di coloro che hanno gestito tale compito prima.

Answer 1

Ora supponendo che tu voglia un hash e desideri qualcosa estremamente veloce che funzioni nel tuo caso, perché le tue stringhe sono lunghe solo 6 caratteri potresti usare questa magia:

size_t precision = 2; //change the precision with this
size_t hash(const char* str)
{
   return (*(size_t*)str)>> precision;
}

CRC è per slowpokes;)

Spiegazione: Funziona lanciando il contenuto del puntatore stringa su & Quot; assomiglia a & Quot; un size_t (int32 o int64 basato sulla corrispondenza ottimale per il tuo hardware). Quindi il contenuto della stringa viene interpretato come un numero non elaborato, non ti preoccupare più dei caratteri e quindi sposta la precisione necessaria (modifica questo numero per ottenere le prestazioni migliori, ho trovato che 2 funziona bene per le stringhe di hash in set di poche migliaia).

Anche la parte davvero pulita è che qualsiasi compilatore decente su hardware moderno avrà una stringa come questa in 1 istruzione di assemblaggio, difficile da battere;)

Answer 2

Questo semplice polinomio funziona sorprendentemente bene. L'ho preso da Paul Larson di Microsoft Research, che ha studiato un'ampia varietà di funzioni di hash e moltiplicatori di hash.

unsigned hash(const char* s, unsigned salt)
{
    unsigned h = salt;
    while (*s)
        h = h * 101 + (unsigned) *s++;
    return h;
}

salt deve essere inizializzato su alcuni casualmente valori scelti prima che venga creato l'hashtable per difendersi da attacchi alla tabella hash . Se questo non è un problema per te, usa semplicemente 0.

Anche la dimensione della tabella è importante, per ridurre al minimo le collisioni. Sembra che il tuo vada bene.

Answer 3

Boost.Functional / Hash potrebbe essere di abituati a te. Non l'ho provato, quindi non posso garantire le sue prestazioni.

Boost ha anche una libreria CRC .

Vorrei prima cercare un Boost.Unordered (es. boost :: unordered_map < >). Usa le mappe hash invece degli alberi binari per i contenitori.

Credo che alcune implementazioni STL abbiano una hash_map < > contenitore nello spazio dei nomi stdext.

Answer 4

La dimensione della tua tabella determinerà quale dimensione hash dovresti usare. Ti piacerebbe minimizzare le collisioni ovviamente. Non sono sicuro di ciò che stai specificando in base a articoli e capacità massimi (mi sembrano la stessa cosa) In ogni caso uno di questi numeri suggerisce che un hash a 32 bit sarebbe sufficiente. Potresti cavartela con CRC16 (~ 65.000 possibilità) ma probabilmente avresti molte collisioni da affrontare. D'altra parte, una collisione potrebbe essere più rapida da gestire rispetto a un hash CRC32.

Direi, vai con CRC32. Non troverai carenza di documentazione e codice di esempio. Dato che hai raggiunto il massimo e la velocità è una priorità, scegli una serie di puntatori. Usa l'hash per generare un indice. In caso di collisione, incrementa l'indice fino a quando non colpisci un secchio vuoto ... veloce e semplice.

Answer 5

Dato che memorizzi parole inglesi, la maggior parte dei tuoi caratteri saranno lettere e non ci saranno molte variazioni nei due bit più significativi dei tuoi dati. Oltre a ciò lo terrei molto semplice, usando solo XOR. Dopotutto non stai cercando forza crittografica ma solo una distribuzione ragionevolmente uniforme. Qualcosa del genere:

size_t hash(const std::string &data) {
  size_t h(0);
  for (int i=0; i<data.length(); i++)
    h = (h << 6) ^ (h >> 26) ^ data[i];
  }
  return h;
}

Oltre a questo, hai visto std :: tr1 :: hash come una funzione di hashing e / o std :: tr1 :: unordered_map come implementazione di una tabella hash? L'uso di questi probabilmente risparmierebbe molto lavoro rispetto all'implementazione delle tue classi.

Answer 6

  

La priorità numero uno della mia tabella hash è la ricerca rapida (recupero).

Bene, allora stai usando la giusta struttura di dati, dato che la ricerca in una tabella hash è O (1)! :)

Il CRC32 dovrebbe andare bene. L'implementazione non è così complessa, si basa principalmente su XOR. Assicurati solo che usi un buon polinomio.

Answer 7

Che ne dici di qualcosa di semplice:

// Initialize hash lookup so that it maps the characters
// in your string to integers between 0 and 31
int hashLookup[256];

// Hash function for six character strings.
int hash(const char *str)
{
    int ret = 0, mult = 1;
    for (const char *p = str; *p; *p++, mult *= 32) {
        assert(*p >= 0 && *p < 256);
        ret += mult * hashLookup[*p];
    }

    return ret;
}

Questo presuppone che gli input a 32 bit. Utilizza 5 bit per carattere, quindi il valore di hash contiene solo 30 bit. Potresti risolvere questo problema, forse, generando sei bit per il primo o due caratteri. Se il set di caratteri è abbastanza piccolo, potresti non aver bisogno di più di 30 bit.

Answer 8

Se devi cercare stringhe brevi e l'inserimento non è un problema, forse potresti usare un albero B o un albero 2-3, non guadagni molto con l'hash nel tuo caso.

Il modo in cui lo faresti è posizionando una lettera in ciascun nodo in modo da verificare prima il nodo " a " ;, quindi controllare " a " i figli di " p " ;, ed i suoi figli per " p " ;, quindi " l " e quindi " e " ;. In situazioni in cui hai & Quot; apple & Quot; e " applica " devi cercare l'ultimo nodo, (poiché l'unica differenza è nell'ultimo " e " e " y ")

Ma nella maggior parte dei casi sarai in grado di ottenere la parola dopo pochi passaggi (" xilofono " = > " x " - > " ylophone "), così puoi ottimizzare in questo modo. Questo può essere più veloce dell'hash

Answer 9

Dal C ++ 11, C ++ ha fornito un std::hash< string >( string ) . È probabile che sia una funzione di hashing efficiente che fornisce una una buona distribuzione dei codici hash per la maggior parte delle stringhe.

Inoltre, se stai pensando di implementare una tabella hash, ora dovresti prendere in considerazione l'uso di un C ++ std::unordered_map invece.