Что такое hash-функция по умолчанию, используемая в C ++ std :: unordered_map?

Объект функции std::hash<> используется.

Стандартные специализации существуют для всех встроенных типов и некоторых других стандартных типов библиотек, таких как std::string и std::thread . См. Полный список ссылок.

Для других типов, которые будут использоваться в std::unordered_map , вам придется специализироваться на std::hash<> или создать свой собственный объект функции.

Вероятность столкновения полностью зависит от реализации, но учитывая тот факт, что целые числа ограничены между определенным диапазоном, а строки теоретически бесконечно длинны, я бы сказал, что вероятность столкновения со строками намного выше.

Что касается реализации в GCC, специализация для встроенных типов просто возвращает бит-шаблон. Вот как они определены в bits/functional_hash.h :

  /// Partial specializations for pointer types. template struct hash<_Tp*> : public __hash_base { size_t operator()(_Tp* __p) const noexcept { return reinterpret_cast(__p); } }; // Explicit specializations for integer types. #define _Cxx_hashtable_define_trivial_hash(_Tp) \ template<> \ struct hash<_tp> : public __hash_base \ { \ size_t \ operator()(_Tp __val) const noexcept \ { return static_cast(__val); } \ }; /// Explicit specialization for bool. _Cxx_hashtable_define_trivial_hash(bool) /// Explicit specialization for char. _Cxx_hashtable_define_trivial_hash(char) /// ... 

Специализация для std::string определяется как:

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

Дальнейший поиск ведет нас к:

 struct _Hash_impl { static size_t hash(const void* __ptr, size_t __clength, size_t __seed = static_cast(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 – это внешняя функция из libstdc++ . Еще немного поиска привело меня к этому файлу , в котором говорится:

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

Таким образом, алгоритм hashирования по умолчанию, используемый GCC для строк, – MurmurHashUnaligned2.

Хотя алгоритмы hashирования зависят от компилятора, я представлю его для GCC C ++ 11. @Avidan Borisov уверенно обнаружил, что алгоритм hashирования GCC, используемый для строк, – «MurmurHashUnaligned2», Остин Эпплби. Я сделал несколько поисков и нашел зеркальную копию GCC на Github. Следовательно:

Функции хеширования GCC C ++ 11, используемые для unordered_map (шаблон таблицы hashей) и unordered_set (шаблон набора hashей), выглядят следующим образом.

• Спасибо Авидану Борисову за его справочное исследование, которое касается вопроса о том, какие используются hash-функции GCC C ++ 11 , заявив, что GCC использует реализацию «MurmurHashUnaligned2», Остином Эпплби ( http://murmurhash.googlepages.com/) ).
• В файле «gcc / libstdc ++ – v3 / libsupc ++ / hash_bytes.cc», здесь ( https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/libsupc++/hash_bytes.cc ), я нашел реализации. Вот пример для возвращаемого значения «32-разрядный размер_t», например (вытащенный 11 августа 2017 года)

Код:

 // 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(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(buf[2]) << 16; [[gnu::fallthrough]]; case 2: hash ^= static_cast(buf[1]) << 8; [[gnu::fallthrough]]; case 1: hash ^= static_cast(buf[0]); hash *= m; }; // Do a few final mixes of the hash. hash ^= hash >> 13; hash *= m; hash ^= hash >> 15; return hash; } 

Для дополнительных функций hashирования, включая djb2 и 2 версии djb2 функций K & R (по-видимому, ужасно, один очень хорошо), см. Мой другой ответ здесь: https://stackoverflow.com/a/45641002/4561887 .