Última actualización：2026-10-12

STL hashtable tabla hash¶

0. Introducción¶

La tabla hash es el contenedor subyacente de unordered_map, unordered_set y similares; ¡a partir de gcc2.9 la cantidad de código fuente se disparó!

El código leído esta vez sigue siendo el de gcc4.9.1; hay muchísimo código, así que no lo desplegaremos todo: nos centraremos en el arte y la técnica de la tabla hash subyacente. Estas dos palabras suenan bien juntas, jeje. ¡Vamos al grano!

1. Primer contacto con Hashtable¶

Echemos primero un vistazo al código fuente de Hashtable:

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

Quien no haya estudiado plantillas de clase se queda totalmente perdido: solo de contar los parámetros de plantilla ya mareas...

Y luego su herencia: de golpe saca tantos padres...

A continuación analizaremos uno a uno sus padres y luego volveremos a la tabla hash.

2._Hashtable_base¶

En los comentarios dice lo siguiente:

Helper class adding management of _Equal functor to _Hash_code_base type.

Clase auxiliar que añade la gestión del functor _Equal al tipo _Hash_code_base.

Comparando el código se ve enseguida qué significa:

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>
{

};

Comparando _Hash_code_base con _Hashtable_base, la única diferencia es un _Equal; con esto queda explicada la frase.

Sus clases base son dos:

__detail::_Hash_code_base
__detail::_Hashtable_ebo_helper

¡Sigamos rastreando estas dos clases!

2.1 _Hash_code_base¶

El último parámetro de esta clase, __cache_hash_code, indica si se cachea el hash code.

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

Según se cachee o no, se obtienen sus versiones especializadas parcialmente:

Usa hash por rangos (en realidad, lo que normalmente llamamos método de la división), sin cachear el 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>
}

Usa hash por rangos (en realidad, lo que normalmente llamamos método de la división), cacheando el hash code.

Para esta especialización parcial, la caché no es necesaria, ¡así que en el código solo está la declaración y no la definición!

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

- Con función hash y función hash por rangos, sin cachear el 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>
{
};

- La versión anterior con caché del 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, true>
: private _Hashtable_ebo_helper<0, _ExtractKey>,
    private _Hashtable_ebo_helper<1, _H1>,
    private _Hashtable_ebo_helper<2, _H2>
{

Seguro que _H1 y _H2 anteriores resultan confusos; veámoslos:

（1） Default range hashing function (función hash por rangos por defecto)

h1=hash<key>

La siguiente es justo esto:

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

Más adelante se puede ver la explicación concreta.

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

Aunque esté definido con un struct y pueda parecer una clase, en realidad sobrecarga el operador (): es un functor.

Lo anterior, llevado a la estructura de datos de la tabla hash, es la función de dispersión que todos conocéis: el método de la división.

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

A continuación, _Default_ranged_hash:

struct _Default_ranged_hash { };

Esto solo sirve como marcador: la función hash por rangos ya calculada por defecto (Default ranged hash function):

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

Así que hasta aquí la función de dispersión de la tabla hash subyacente queda clara: por defecto es exactamente esta. Y el marcador mencionado hace un momento existe porque componer objetos de los tipos H1 y H2 en H consumiría operaciones de copia adicionales; de ahí la introducción de este marcador.

Con esto termina la explicación de _H1 y _H2 mencionados arriba: se corresponden, respectivamente, con las dos funciones anteriores.

（2） Operación rehash

Acto seguido hay otra pieza importante llamada rehash. Seguro que conocéis bien rehash: cuando los conflictos de la tabla de dispersión alcanzan cierto nivel, hay que recolocar las keys en posiciones adecuadas, y eso es precisamente lo que hace el código fuente de la tabla hash; aquí se encapsula en una rehash policy:

struct _Prime_rehash_policy
{
   //...
};

Sobre la operación rehash se comenta: el tamaño de cubo (bucket size) por defecto suele ser el primo más pequeño, para garantizar que el factor de carga (load factor, el cociente entre el número actual de elementos del contenedor y el número de cubos) sea suficientemente pequeño. El factor de carga mide el grado de llenado de la tabla hash; el factor de carga máximo por defecto es 1.0.

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


> rehash计算下一个素数桶

Cuando hay conflicto de hash, ¿cómo se hace el rehash?

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

Cuando se produce un conflicto de hash, esta función devuelve un primo no menor que n para usarlo como siguiente cubo.

Tabla de primos

¿Cómo se buscan los primos? Arriba aparece un __prime_list, así que fuimos a buscarlo y en libstdc++v3/src/shared/hashtable-aux.cc encontramos la tabla completa de primos. Dentro hay 256+1+49 o 256+49 en total. Si sizeof(unsigned long)!=8 son 256+1+49; en caso contrario, 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，
    // 后面还有很多
  }

Así que todo queda clarísimo: se usa lower_bound sobre la tabla anterior para encontrar el primer primo mayor o igual que el valor n dado.

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

Cálculo del cubo correspondiente a un elemento

A partir del factor de carga máximo se calcula el número mínimo de cubos y, a partir de este, el primo mínimo de cubos correspondiente a cada elemento.

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 es el EBO (clase base vacía) que ya estudiamos antes.

_Map_base implementa, mediante especialización parcial, la sobrecarga de los operadores [] y at.

｀_Insert｀ se encarga principalmente de todo lo relacionado con la inserción.

｀_Rehash_base｀ se encarga principalmente de transmitir el valor del factor de carga máximo del rehash descrito arriba.

｀_Equality_base｀ proporciona principalmente tipos y funciones comunes para la clase _Equality.

Hasta aquí quedan explicadas todas las clases de las que hereda el _Hashtable anterior.

2. Estructura de los nodos de la lista enlazada en hashtable¶

Clase base del hash node: contiene únicamente la declaración del puntero.

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) { }
};

La clase con valor de nodo hereda de la clase base anterior

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

Antes se mencionó si el nodo lleva o no hash code; el nodo debe incluir el hash code, y esto se concreta en la implementación siguiente:

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

Aquí queda claro: los nodos se dividen en los que incluyen hash code y los que no; en concreto, según el parámetro de plantilla que se pase, se invoca la versión especializada correspondiente.

3. Iteradores¶

La clase base del iterador muestra el uso de la sintaxis using, similar a typedef, de modo que después se puede definir directamente con la sintaxis __node_type; la función _M_incr obtiene el siguiente nodo de la lista enlazada.

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

Iterador de nodo: estudiando el código siguiente se aprenden dos cosas: - Primero: el uso de using - el iterador de hashtable es un forward_iterator - sobrecarga los cuatro operadores ++, --, * y ->

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. Estudio en profundidad de la importante estructura interna de hashtable¶

La estructura interna mantiene una lista enlazada simple en cada elemento y, sobre esa lista, ejecuta las operaciones de inserción, búsqueda y borrado de elementos; cada elemento se denomina cubo (bucket). La construcción subyacente primero usa H1 para calcular el hash code de la key y después obtiene el cubo correspondiente mediante el método de la división H2.

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;  // 只需要一个桶用
};

Algunas funciones importantes de hashtable:

Función begin

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

Invoca _M_begin:

Puedes imaginar _M_before_begin como un nodo head: el primer nodo es el siguiente nodo.

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

Función end

Al ser una lista simplemente enlazada, basta con devolver el último.

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

Funciones size y empty

size_type
size() const noexcept
{ return _M_element_count; }

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

Número de cubos

size_type
bucket_count() const noexcept
{ return _M_bucket_count; }

Cálculo del factor de carga

El número actual de elementos dividido por el número de cubos

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

Cálculo del índice del cubo

Obtiene el índice del cubo a partir de la key que se le pasa.

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

En _Hash_code_base hay la implementación siguiente:

_M_h1 devuelve _H1; cuando no sepamos qué es _H1, podemos buscarlo en unordered_map, donde encontramos _Hash=hash<_Key>, por lo que la función siguiente es la expresión matemática: h1(k) para obtener el hash code.

Devuelve el hash code del cubo.

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

Devuelve el índice del cubo.

La definición de _M_bucket_index se encuentra más adelante en el mismo archivo:

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

Seguimos buscando _M_bucket_index en __hash_code_base y lo encontramos en 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); }

Igual que en la búsqueda de h1 anterior, en unordered_map se encuentra que _H2 usa por defecto _Mod_range_hashing; veamos este código fuente:

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

La expresión matemática correspondiente es h2(c,n).

Por tanto, la expresión matemática correspondiente a la obtención del índice del cubo con bucket anterior es:

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

En realidad, la forma final es:

hash(k)%n

Este es el cálculo del índice del cubo.