Qual è la funzione di hash predefinita utilizzata in C++ std :: unordered_map?

Question

Sto usando

unordered_map<string, int> 

e

unordered_map<int, int> 

Quale funzione hash viene utilizzato in ogni caso e che cosa è la possibilità di collisione in ogni caso? Inserirò una stringa univoca e univoci int come rispettivamente in ciascun caso.

Sono interessato a conoscere l'algoritmo della funzione di hash in caso di chiavi stringa e int e le loro statistiche di collisione.

Answer 1

Viene utilizzato l'oggetto funzione std::hash<>.

Le specializzazioni standard esistono per tutti i tipi incorporati e alcuni altri tipi di libreria standard come std::string e std::thread. Vedi il link per l'elenco completo.

Per altri tipi da utilizzare in un std::unordered_map, è necessario specializzarsi su std::hash<> o creare il proprio oggetto funzione.

La possibilità di collisione è completamente dipendente dall'implementazione, ma considerando il fatto che gli interi sono limitati tra un intervallo definito, mentre le stringhe sono teoricamente infinitamente lunghe, direi che c'è una possibilità molto migliore di collisione con le stringhe.

Per quanto riguarda l'implementazione in GCC, la specializzazione per i tipi incorporati restituisce semplicemente il modello di bit. Ecco come vengono definiti in bits/functional_hash.h:

/// Partial specializations for pointer types. 
    template<typename _Tp> 
    struct hash<_Tp*> : public __hash_base<size_t, _Tp*> 
    { 
     size_t 
     operator()(_Tp* __p) const noexcept 
     { return reinterpret_cast<size_t>(__p); } 
    }; 

    // Explicit specializations for integer types. 
#define _Cxx_hashtable_define_trivial_hash(_Tp)  \ 
    template<>      \ 
    struct hash<_Tp> : public __hash_base<size_t, _Tp> \ 
    {             \ 
     size_t           \ 
     operator()(_Tp __val) const noexcept    \ 
     { return static_cast<size_t>(__val); }   \ 
    }; 

    /// Explicit specialization for bool. 
    _Cxx_hashtable_define_trivial_hash(bool) 

    /// Explicit specialization for char. 
    _Cxx_hashtable_define_trivial_hash(char) 

    /// ... 

---

La specializzazione per std::string è definito come:

#ifndef _GLIBCXX_COMPATIBILITY_CXX0X 
    /// std::hash specialization for string. 
    template<> 
    struct hash<string> 
    : public __hash_base<size_t, string> 
    { 
     size_t 
     operator()(const string& __s) const noexcept 
     { return std::_Hash_impl::hash(__s.data(), __s.length()); } 
    }; 

Alcuni ulteriore ricerca ci porta a:

struct _Hash_impl 
{ 
    static size_t 
    hash(const void* __ptr, size_t __clength, 
     size_t __seed = static_cast<size_t>(0xc70f6907UL)) 
    { return _Hash_bytes(__ptr, __clength, __seed); } 
    ... 
}; 
... 
// Hash function implementation for the nontrivial specialization. 
// All of them are based on a primitive that hashes a pointer to a 
// byte array. The actual hash algorithm is not guaranteed to stay 
// the same from release to release -- it may be updated or tuned to 
// improve hash quality or speed. 
size_t 
_Hash_bytes(const void* __ptr, size_t __len, size_t __seed); 

_Hash_bytes è un funzione esterna da libstdc++. Un po 'più alla ricerca mi ha portato a this file, in cui si afferma:

// This file defines Hash_bytes, a primitive used for defining hash 
// functions. Based on public domain MurmurHashUnaligned2, by Austin 
// Appleby. http://murmurhash.googlepages.com/ 

Così il GCC algoritmo predefinito hashing usa per le stringhe è MurmurHashUnaligned2.

Answer 2

Sebbene gli algoritmi di hashing siano dipendenti dal compilatore, lo presenterò per GCC C++ 11. @Avidan Borisov astutely discovered che l'algoritmo di hashing GCC utilizzato per le stringhe è "MurmurHashUnaligned2", di Austin Appleby. Ho fatto qualche ricerca e ho trovato una copia speculare di GCC su Github. Pertanto:

Il GCC C++ funzioni 11 hashing utilizzati per unordered_map (un modello di tabella hash) e unordered_set (un modello di set hash) sembrano essere la seguente.

• Thanks to Avidan Borisov per la sua ricerca di sfondo, che sulla questione delle quali sono i GCC C++ 11 funzioni di hash utilizzati, affermando che GCC utilizza un'implementazione di "MurmurHashUnaligned2", di Austin Appleby (http://murmurhash.googlepages.com/).
• Nel file "gcc/libstdC++ - v3/libsupC++/hash_bytes.cc", qui (https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/libsupc++/hash_bytes.cc), ho trovato le implementazioni. Ecco quello per il valore di ritorno "a 32 bit size_t", per esempio (tirato 11 ago 2017)

Codice:

// Implementation of Murmur hash for 32-bit size_t. 
size_t _Hash_bytes(const void* ptr, size_t len, size_t seed) 
{ 
    const size_t m = 0x5bd1e995; 
    size_t hash = seed^len; 
    const char* buf = static_cast<const char*>(ptr); 

    // Mix 4 bytes at a time into the hash. 
    while (len >= 4) 
    { 
    size_t k = unaligned_load(buf); 
    k *= m; 
    k ^= k >> 24; 
    k *= m; 
    hash *= m; 
    hash ^= k; 
    buf += 4; 
    len -= 4; 
    } 

    // Handle the last few bytes of the input array. 
    switch (len) 
    { 
    case 3: 
     hash ^= static_cast<unsigned char>(buf[2]) << 16; 
     [[gnu::fallthrough]]; 
    case 2: 
     hash ^= static_cast<unsigned char>(buf[1]) << 8; 
     [[gnu::fallthrough]]; 
    case 1: 
     hash ^= static_cast<unsigned char>(buf[0]); 
     hash *= m; 
    }; 

    // Do a few final mixes of the hash. 
    hash ^= hash >> 13; 
    hash *= m; 
    hash ^= hash >> 15; 
    return hash; 
} 

Per le funzioni di hashing aggiuntive, tra cui djb2, e le 2 versioni di K & Funzioni di hashing R (uno apparentemente terribile, uno piuttosto buono), vedere la mia altra risposta qui: https://stackoverflow.com/a/45641002/4561887.