c ++ - Hvad er den bedste hashingalgoritme til at bruge på en stl-streng, når du bruger hash\_map?

Indlæg af Hanne Mølgaard Plasc

Problem



Jeg har fundet standard hashing-funktionen på VS2005 er smerteligt langsom, når jeg forsøger at opnå high performance look ups. Hvad er nogle gode eksempler på hurtige og effektive hashing-algoritmer, der bør fjerne de fleste kollisioner?

Bedste reference


Jeg arbejdede sammen med Paul Larson fra Microsoft Research på nogle hashtable implementeringer. Han undersøgte en række streng hashing funktioner på en række datasæt og fandt ud af, at en simpel multiplicere med 101 og add loop fungerede overraskende godt. [9]


unsigned int
hash(
    const char* s,
    unsigned int seed = 0)
{
    unsigned int hash = seed;
    while (*s)
    {
        hash = hash * 101  +  *s++;
    }
    return hash;
}

Andre referencer 1


Fra noget gammelt min kode:


/* magic numbers from http://www.isthe.com/chongo/tech/comp/fnv/ */
static const size\_t InitialFNV = 2166136261U;
static const size\_t FNVMultiple = 16777619;

/* Fowler / Noll / Vo (FNV) Hash */
size\_t myhash(const string &s)
{
    size\_t hash = InitialFNV;
    for(size\_t i = 0; i < s.length(); i++)
    {
        hash = hash ^ (s[i]);       /* xor  the low 8 bits */
        hash = hash * FNVMultiple;  /* multiply by the magic number */
    }
    return hash;
}


Det er hurtigt. Freaking virkelig hurtigt.

Andre referencer 2


Boost har et boost :: hash bibliotek, der kan give nogle grundlæggende hash funktioner til de fleste almindelige typer. [10]

Andre referencer 3


Det afhænger altid af dit datasæt.


Jeg for en havde overraskende gode resultater ved at bruge strengens CRC32. Fungerer meget godt med en bred vifte af forskellige inputsæt.


Masser af gode CRC32 implementeringer er nemme at finde på nettet.


 Næsten glemt: Denne side har en nice hash-funktion shootout med præstationsnumre og testdata:


http://smallcode.weblogs.us/< - længere nede på siden. [11]

Andre referencer 4


Jeg har brugt Jenkins hash til at skrive et Bloom filter bibliotek, det har stor ydeevne.


Detaljer og kode er tilgængelige her: http://burtleburtle.net/bob/c/lookup3.c[12]


Dette er, hvad Perl bruger til sin hashing operation, fwiw.

Andre referencer 5


Hvis du har hash et fast sæt ord, er den bedste hash funktion ofte en perfekt hash funktion. Men de kræver generelt, at det sæt af ord, du forsøger at have, er kendt ved kompileringstid. Påvisning af søgeord i en lexer (og oversættelse af søgeord til tokens) er en fælles brug af perfekte hashfunktioner, der genereres med værktøjer som gperf. En perfekt hash lader dig også erstatte hash\_map med et enkelt array eller vector. [13] [14] [15]


Hvis du ikke hylder et fast sæt ord, så virker det naturligvis ikke.

Andre referencer 6


Et klassisk forslag til en streng hash er at gå gennem bogstaverne en ad gangen tilføje deres ascii/unicode værdier til en akkumulator, hver gang multiplicere akkumulatoren med et primært tal. (tillader overløb på hashværdien)


  template <> struct myhash{};

  template <> struct myhash<string>
    {
    size\_t operator()(string &to\_hash) const
      {
      const char * in = to\_hash.c\_str();
      size\_t out=0;
      while(NULL != *in)
        {
        out*= 53; //just a prime number
        out+= *in;
        ++in;
        }
      return out;
      }
    };

  hash\_map<string, int, myhash<string> > my\_hash\_map;


Det er svært at få hurtigere end det uden at smide data ud. Hvis du ved, dine strings kan differentieres af kun få tegn og ikke hele indholdet, kan du gøre hurtigere.


Du kan måske prøve at cache hashværdien bedre ved at oprette en ny underklasse af basic\_string, der husker dens hashværdi, hvis værdien bliver beregnet for ofte. hash\_map skal dog gøre det internt.

Andre referencer 7


Jeg gjorde lidt søgning og sjovt, Paul Larsons lille algoritme viste sig her
http://www.strchr.com/hash\_functions
som at have de mindst kollisioner af nogen testet under en række betingelser, og det er meget hurtigt for en, at det er rullet eller borddrevet. [16]


Larson er den simple multiplicere med 101 og tilføj sløjfe ovenfor.

Andre referencer 8


Python 3.4 indeholder en ny hash-algoritme baseret på SipHash. PEP 456 er meget informativ. [17] [18]

Andre referencer 9


Hvis dine strenge i gennemsnit er længere end en enkelt cache-linje, men deres længde + præfiks er ret unikke, overvej at have kun længden + første 8/16 tegn. (Længden er indeholdt i selve std :: strengobjektet og derfor billigt at læse)

Andre referencer 10


Fra Hashfunktioner hele vejen ned: [19]



  MurmurHash blev ganske populær, i hvert fald i spiludviklercirkler, som en 'general hash-funktion'. [20]

  
  Det er et godt valg, men lad os se senere, hvis vi generelt kan gøre det bedre. Et andet fint valg, især hvis du ved mere om dine data end 'det bliver et ukendt antal bytes', er at rulle din egen (se f.eks. Won Chuns svar eller Runes ændrede xxHash/Murmur, der er specialiseret i 4-byte nøgler etc.). Hvis du kender dine data, prøv altid at se, om den viden kan bruges til god effekt!



Uden mere information vil jeg anbefale MurmurHash som en almennyttig ikke-kryptografisk hash funktion. For små strenge (af størrelsen af ​​den gennemsnitlige identifikator i programmer) er den meget enkle og berømte djb2 og FNV meget god. [21] [22] [23] [24]



  Her (datastørrelser <10 bytes) kan vi se, at ILP-smidigheden af ​​andre algoritmer ikke kommer til at vise sig, og super-simpliciteten af ​​FNV eller djb2 vinder i performance.



djb2



unsigned long
hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}


FNV-1



hash = FNV\_offset\_basis
for each byte\_of\_data to be hashed
     hash = hash × FNV\_prime
     hash = hash XOR byte\_of\_data
return hash


FNV-1A



hash = FNV\_offset\_basis
for each byte\_of\_data to be hashed
     hash = hash XOR byte\_of\_data
     hash = hash × FNV\_prime
return hash


En note om sikkerhed og tilgængelighed



Hash-funktioner kan gøre din kode sårbar over for deial-of-service-angreb. Hvis en hacker kan tvinge din server til at håndtere for mange sammenstød, kan din server muligvis ikke klare anmodninger. [25] [26] [27]


Nogle hashfunktioner som MurmurHash accepterer et frø, som du kan yde for drastisk at reducere angriberens evne til at forudse de hashser, din serversoftware genererer. Husk det. [28]