Last updated：2026-10-12

STL hashtable hash table

0.Introduction

The hash table serves as the underlying container of unordered_map and unordered_set and the like; since gcc2.9 its source code has grown massively!

The code we are reading this time is again gcc4.9.1. There is a lot of code, so we will not unfold all of it; we will focus on the art and technique of the underlying hashing — those two words do seem to rhyme, haha. Now to the main text~

1.First look at Hashtable

First, a glance at the Hashtable source code:

template<typename _Key, typename _Value, typename _Alloc,
    typename _ExtractKey, typename _Equal,
    typename _H1, typename _H2, typename _Hash,
    typename _RehashPolicy, typename _Traits>
class _Hashtable
: 　public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
    public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,  _H1, _H2, _Hash, _RehashPolicy, _Traits>,
    public __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>,
    public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,_H1, _H2, _Hash, _RehashPolicy, _Traits>,
    public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,_H1, _H2, _Hash, _RehashPolicy, _Traits>,
    private __detail::_Hashtable_alloc<typename __alloctr_rebind<_Alloc,__detail::_Hash_node<_Value,_Traits::__hash_cached::value> >::__type>
{
};

Those who have never studied class templates will be baffled — just counting the template parameters is dizzying...

And then its inheritance, suddenly producing this many fathers...

Below we analyze its fathers one by one, and then return to the hash table.

2._Hashtable_base

The comment in it reads:

Helper class adding management of _Equal functor to _Hash_code_base type.

A helper class that adds management of the _Equal functor to _Hash_code_base.

Comparing the code makes the meaning clear:

template<typename _Key, typename _Value,
    typename _ExtractKey, typename _Equal,
    typename _H1, typename _H2, typename _Hash, typename _Traits>
struct _Hashtable_base
: public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, _Traits::__hash_cached::value>,
private _Hashtable_ebo_helper<0, _Equal>
{

};

Comparing _Hash_code_base with _Hashtable_base, the two differ only in an _Equal, so that sentence is explained.

Its base classes, in turn, are two:

__detail::_Hash_code_base
__detail::_Hashtable_ebo_helper

Let's keep tracing these two classes!

2.1 _Hash_code_base

The last parameter of this class, __cache_hash_code, indicates whether to cache the hash code.

template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash,bool __cache_hash_code>
struct _Hash_code_base;

Depending on caching or not, we get its partially specialized versions:

• Uses range hashing (in effect what we usually call division with remainder), does not cache the hash code.

template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash>
struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
: private _Hashtable_ebo_helper<0, _ExtractKey>,
private _Hashtable_ebo_helper<1, _Hash>
}

- Uses range hashing (in effect what we usually call division with remainder), caches the hash code.

For this partial specialization, caching is unnecessary, so in the code it is only declared, never defined!

template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash>
struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;

- Has a hash function and a range hash function, does not cache the hash code.

template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2>
struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
_Default_ranged_hash, false>
: private _Hashtable_ebo_helper<0, _ExtractKey>,
private _Hashtable_ebo_helper<1, _H1>,
private _Hashtable_ebo_helper<2, _H2>
{
};

- The caching version of the above

template<typename _Key, typename _Value, typename _ExtractKey,
    typename _H1, typename _H2>
struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
            _Default_ranged_hash, true>
: private _Hashtable_ebo_helper<0, _ExtractKey>,
    private _Hashtable_ebo_helper<1, _H1>,
    private _Hashtable_ebo_helper<2, _H2>
{

The _H1 and _H2 above surely confuse everyone; let's take a look:

(1) Default range hashing function

h1=hash<key>

The following is exactly it:

h2(h1(key),N)=h1(key)%N

The details are explained later on.

struct _Mod_range_hashing
{
    typedef std::size_t first_argument_type;
    typedef std::size_t second_argument_type;
    typedef std::size_t result_type;

    result_type
    operator()(first_argument_type __num,
            second_argument_type __den) const noexcept
    { return __num % __den; }
};

Don't be misled by it being defined with a struct into thinking it is a class: it overloads the () operator, so it is a functor.

Mapped onto the hash table data structure, the above is the hash function everyone knows: division with remainder.

f(__num) = __num mod __den(__den<=__num)

Next comes _Default_ranged_hash:

struct _Default_ranged_hash { };

This serves only as a marker for the default already-computed range hash function (Default ranged hash function):

h(k, N) = h2(h1(k), N),

So at this point the hash function of the underlying hash table is clear: by default it is exactly this. And the marker just mentioned exists because composing an H from objects of types H1 and H2 would consume extra copy operations, hence this marker was introduced.

With that, the _H1 and _H2 mentioned above are fully explained: they correspond respectively to the two functions above.

(2) The rehash operation

Right after, there is another important one called rehash. You surely know rehash well: when collisions in the hash table reach a certain level, keys need to be placed back into appropriate positions, and that is exactly what the underlying hash table source code does; here it is encapsulated as a rehash policy:

struct _Prime_rehash_policy
{
   //...
};

On the rehash operation: the bucket size is by default usually the smallest prime, thereby keeping the load factor (the ratio of the container's current element count to the number of buckets) small enough. The load factor measures how full the hash table is; the default maximum load factor is 1.0.

_Prime_rehash_policy(float __z = 1.0)
: _M_max_load_factor(__z), _M_next_resize(0) { }


> rehash计算下一个素数桶

When a hash collision occurs, how is the rehash done?

 inline std::size_t
_Prime_rehash_policy::
_M_next_bkt(std::size_t __n) const
{
    const unsigned long* __p = std::lower_bound(__prime_list, __prime_list + _S_n_primes, __n);
    _M_next_resize = 
        static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
return *__p;
}

When a hash collision occurs, this function returns a prime not less than n to serve as the next bucket.

The prime table

How are primes looked up? Noticing the __prime_list above, we went searching and found the entire prime table in libstdc++v3/src/shared/hashtable-aux.cc. In total there are 256+1+49, or 256+49, of them. If sizeof(unsigned long)!=8 there are 256+1+49; otherwise 256+49.

extern const unsigned long __prime_list[] = // 256 + 1 or 256 + 48 + 1
  {
    2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,
    37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul,
    83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul，
    // 后面还有很多
  }

So everything becomes very clear: lower_bound is used to find, in the table above, the first prime greater than or equal to the given value n.

enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };

Computing the bucket for an element

From the maximum load factor the minimal number of buckets is derived, and then, based on the buckets, the minimal prime bucket for each element is computed.

inline std::size_t
_Prime_rehash_policy::
_M_bkt_for_elements(std::size_t __n) const
{
    // 获取最小的桶
    const float __min_bkts = __n / _M_max_load_factor;
    // 获取最小素数p
    const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
                        + _S_n_primes, __min_bkts);
    _M_next_resize =
        static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
    return *__p;
}

_Hashtable_ebo_helper is exactly the EBO empty base class learned earlier.

_Map_base mainly implements the overloaded operators [] and at via partial specialization.

_Insert mainly handles insertion-related work.

_Rehash_base mainly delivers the maximum load factor value used in the rehash above.

_Equality_base mainly provides the common types and functions for the class _Equality.

Up to now, every class inherited by the _Hashtable above has been explained.

2.Node structure of the linked list in the hashtable

The hash node base class, which contains only a pointer declaration.

struct _Hash_node_base
{
    _Hash_node_base* _M_nxt;

    _Hash_node_base() noexcept : _M_nxt() { }

    _Hash_node_base(_Hash_node_base* __next) noexcept : _M_nxt(__next) { }
};

The class carrying the node value inherits the base class above

template<typename _Value>
struct _Hash_node_value_base : _Hash_node_base
{
    typedef _Value value_type;

    __gnu_cxx::__aligned_buffer<_Value> _M_storage;

    _Value*
    _M_valptr() noexcept
    { return _M_storage._M_ptr(); }

    const _Value*
    _M_valptr() const noexcept
    { return _M_storage._M_ptr(); }

    _Value&
    _M_v() noexcept
    { return *_M_valptr(); }

    const _Value&
    _M_v() const noexcept
    { return *_M_valptr(); }
};

Earlier we mentioned whether a node carries a hash code, so the node ought to carry the hash code; that is implemented concretely below:

/**
*  Primary template struct _Hash_node.
*/
template<typename _Value, bool _Cache_hash_code>
struct _Hash_node;

/**
*  Specialization for nodes with caches, struct _Hash_node.
*
*  Base class is __detail::_Hash_node_value_base.
*/
template<typename _Value>
struct _Hash_node<_Value, true> : _Hash_node_value_base<_Value>
{
    std::size_t  _M_hash_code;

    _Hash_node*
    _M_next() const noexcept
    { return static_cast<_Hash_node*>(this->_M_nxt); }
};

/**
*  Specialization for nodes without caches, struct _Hash_node.
*
*  Base class is __detail::_Hash_node_value_base.
*/
template<typename _Value>
struct _Hash_node<_Value, false> : _Hash_node_value_base<_Value>
{
    _Hash_node*
    _M_next() const noexcept
    { return static_cast<_Hash_node*>(this->_M_nxt); }
};

At this point it is quite clear: nodes come in two kinds, with and without a hash code; which partially specialized version is invoked depends concretely on the passed template parameters.

3.Iterators

The iterator base class explicitly uses the using syntax, which is similar to typedef; afterwards __node_type can be used directly in definitions. The _M_incr function obtains the next node of the linked list.

/// Base class for node iterators.
template<typename _Value, bool _Cache_hash_code>
struct _Node_iterator_base
{
    using __node_type = _Hash_node<_Value, _Cache_hash_code>;

    __node_type*  _M_cur;

    _Node_iterator_base(__node_type* __p) noexcept
    : _M_cur(__p) { }

    void
    _M_incr() noexcept
    { _M_cur = _M_cur->_M_next(); }
};

The node iterator: studying the code below, we learn two things: - First: the use of using - hashtable's iterator is a forward_iterator - It overloads the four operators ++, --, *, ->

template<typename _Value, bool __constant_iterators, bool __cache>
struct _Node_iterator
: public _Node_iterator_base<_Value, __cache>
{
private:
    using __base_type = _Node_iterator_base<_Value, __cache>;
    using __node_type = typename __base_type::__node_type;

public:
    typedef _Value                  value_type;
    typedef std::ptrdiff_t              difference_type;
    typedef std::forward_iterator_tag           iterator_category;

    using pointer = typename std::conditional<__constant_iterators,
                    const _Value*, _Value*>::type;

    using reference = typename std::conditional<__constant_iterators,
                        const _Value&, _Value&>::type;

    _Node_iterator() noexcept
    : __base_type(0) { }

    explicit
    _Node_iterator(__node_type* __p) noexcept
    : __base_type(__p) { }

    reference
    operator*() const noexcept
    { return this->_M_cur->_M_v(); }

    pointer
    operator->() const noexcept
    { return this->_M_cur->_M_valptr(); }

    _Node_iterator&
    operator++() noexcept
    {
        this->_M_incr();
        return *this;
    }

    _Node_iterator
    operator++(int) noexcept
    {
        _Node_iterator __tmp(*this);
        this->_M_incr();
        return __tmp;
    }
};

4.A close study of the important internal structure of hashtable

The internal structure maintains a singly linked list in each element, and insertion, search, deletion and other operations on elements are performed on the singly linked list. Each element is called a bucket. At the bottom, H1 is first used to compute the hash code of the key, and then via division with remainder H2 the corresponding bucket is obtained.

template<typename _Key, typename _Value, typename _Alloc,
    typename _ExtractKey, typename _Equal,
    typename _H1, typename _H2, typename _Hash,
    typename _RehashPolicy, typename _Traits>
class _Hashtable
private:
    __bucket_type*      _M_buckets;  //_ Hash_node_base *
    size_type           _M_bucket_count;    // bucket 节点个数
    __node_base     _M_before_begin;    // _NodeAlloc::value_type
    size_type           _M_element_count;   // //hashtable中list节点个数
    _RehashPolicy       _M_rehash_policy;  // rehash策略
    __bucket_type       _M_single_bucket;  // 只需要一个桶用
};

Some important functions of the hashtable:

The begin function

iterator
begin() noexcept
{ return iterator(_M_begin()); }

Calling _M_begin:

Think of _M_before_begin as a head node; the first node is its next node.

__node_type*
_M_begin() const
{ return static_cast<__node_type*>(_M_before_begin._M_nxt); }

The end function

Since it is a singly linked list, returning the last one suffices.

iterator
end() noexcept
{ return iterator(nullptr); }

The size and empty functions

size_type
size() const noexcept
{ return _M_element_count; }

bool
empty() const noexcept
{ return size() == 0; }

Number of buckets

size_type
bucket_count() const noexcept
{ return _M_bucket_count; }

Computing the load factor

The current element count divided by the number of buckets

float
load_factor() const noexcept
{
    return static_cast<float>(size()) / static_cast<float>(bucket_count());
}

Computing a bucket's index

Obtain the bucket's index from the passed-in key.

size_type
bucket(const key_type& __k) const
{ return _M_bucket_index(__k, this->_M_hash_code(__k)); }

In _Hash_code_base there is the following implementation:

When we do not know what _M_h1 returning _H1 or _H1 is, we can look it up in unordered_map and find _Hash=hash<_Key>; therefore the function below is the mathematical expression: h1(k) to obtain the hash code.

Returns the hash code of the bucket.

__hash_code
_M_hash_code(const _Key& __k) const
{ return _M_h1()(__k); }

Returns the bucket's index.

The definition of _M_bucket_index is found later in the same file:

size_type
_M_bucket_index(const key_type& __k, __hash_code __c) const
{ return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); }

Continuing to __hash_code_base to look for _M_bucket_index, it can be found in bits/hashtable_policy.h:

std::size_t
_M_bucket_index(const _Key&, __hash_code __c,
        std::size_t __n) const
{ return _M_h2()(__c, __n); }

As with the lookup of h1 above, in unordered_map we can find that _H2 defaults to _Mod_range_hashing; now look at this source:

struct _Mod_range_hashing
{
    typedef std::size_t first_argument_type;
    typedef std::size_t second_argument_type;
    typedef std::size_t result_type;

    result_type
    operator()(first_argument_type __num,
            second_argument_type __den) const noexcept
    { return __num % __den; }
};

The corresponding mathematical expression is h2(c,n).

Therefore the mathematical expression for the bucket above obtaining a bucket's index is:

h(k,hash(k))=h(k,hash(k),n)=h(k,hash(k)%n)

which in effect finally is:

hash(k)%n

and that is the computation of a bucket's index.

Related Topics

• STL array source code analysis | C++那些事
• STL string deep dive | C++那些事
• STL string interview questions in depth | C++那些事
• STL deque source code analysis | C++那些事
• STL empty base optimization EBO | C++那些事
• STL hand-written hash table implementation | C++那些事
• STL iterator source code analysis | C++那些事
• STL list source code analysis | C++那些事
• STL map and multimap | C++那些事
• STL queue and stack source code analysis | C++那些事

Comments