Hàm băm mặc định được sử dụng trong C++ std :: unordered_map là gì?

Question

Tôi đang sử dụng

unordered_map<string, int> 

và

unordered_map<int, int> 

hàm băm nào được sử dụng trong từng trường hợp và cơ hội va chạm trong mỗi trường hợp là bao nhiêu? Tôi sẽ chèn chuỗi duy nhất và int duy nhất làm khóa trong mỗi trường hợp tương ứng.

Tôi quan tâm đến việc biết thuật toán hàm băm trong trường hợp chuỗi ký tự và khóa int và số liệu thống kê va chạm của chúng.

Answer 1

Đối tượng hàm std::hash<> được sử dụng.

Chuyên môn tiêu chuẩn tồn tại cho tất cả các loại được tích hợp và một số loại thư viện chuẩn khác chẳng hạn như std::string và std::thread. Xem liên kết để xem danh sách đầy đủ.

Đối với các loại khác được sử dụng trong std::unordered_map, bạn sẽ phải chuyên std::hash<> hoặc tạo đối tượng hàm của riêng bạn.

Nguy cơ va chạm hoàn toàn phụ thuộc vào thực thi, nhưng xem xét thực tế là số nguyên bị giới hạn giữa phạm vi được xác định, trong khi chuỗi dài về mặt lý thuyết, tôi cho rằng có cơ hội tốt hơn để va chạm với chuỗi.

Đối với việc thực hiện trong GCC, việc chuyên môn hóa cho kiểu dựng sẵn chỉ trả về mẫu bit. Dưới đây là cách thức chúng được quy định tại 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) 

    /// ... 

---

Sự chuyên môn cho std::string được định nghĩa là:

#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()); } 
    }; 

Một số tìm kiếm hơn nữa đưa chúng ta đến:

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 là một chức năng bên ngoài từ libstdc++. Một chút: tìm kiếm này dẫn tôi đến this file, trong đó nêu:

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

Vì vậy, các thuật toán mặc định băm GCC sử dụng cho các chuỗi là MurmurHashUnaligned2.

Answer 2

Mặc dù thuật toán băm phụ thuộc vào trình biên dịch, tôi sẽ trình bày nó cho GCC C++ 11. @Avidan Borisov astutely discovered rằng thuật toán băm GCC được sử dụng cho chuỗi là "MurmurHashUnaligned2" của Austin Appleby. Tôi đã làm một số tìm kiếm và tìm thấy một bản sao nhân đôi của GCC trên Github. Do đó:

Hàm băm GCC C++ 11 được sử dụng cho unordered_map (mẫu bảng băm) và unordered_set (mẫu băm) xuất hiện như sau.

• Thanks to Avidan Borisov cho nghiên cứu nền của mình mà về vấn đề GCC C++ 11 hàm băm sử dụng, nói rằng GCC sử dụng một thực hiện "MurmurHashUnaligned2", bởi Austin Appleby (http://murmurhash.googlepages.com/) là gì.
• Trong tệp "gcc/libstdC++ - v3/libsupC++/hash_bytes.cc", tại đây (https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/libsupc++/hash_bytes.cc), tôi đã tìm thấy các triển khai. Dưới đây là một cho "32-bit size_t" giá trị trả về, ví dụ (kéo 11 Aug 2017)

Code:

// 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; 
} 

Đối với chức năng băm bổ sung, bao gồm djb2, và 2 phiên bản chức năng b & R băm (có vẻ như khủng khiếp, một cái khá đẹp), xem câu trả lời khác của tôi ở đây: https://stackoverflow.com/a/45641002/4561887.