Saltar a contenido

Última actualización：2026-10-12

STL implementación de una tabla hash escrita a mano

0. Introducción

Objetivo: implementar a mano una tabla hash, construida con el método de encadenamiento separado, donde cada hash(key) se corresponde con un árbol rojo-negro.

Parece sencillo, pero se puede aprender mucho. Lenguaje de implementación: C++.

Para afianzar las bases de los algoritmos, abrí un repositorio en github para completar más adelante la aplicación e implementación de esos fundamentos; la dirección es:

https://github.com/Light-City/algPratice

También puedes pulsar en leer el original.

1. Versión sencilla de una tabla hash

Encapsulamos la tabla hash en una clase y completamos la definición y declaración del recorrido, así como la implementación del constructor y el destructor: 

template<typename Key, typename Value>
class HashTable {
private:
    const static int upperTol = 3;
    const static int lowerTol = 1;
    const static int initCapacity = 1;
    map<Key, Value> **hashtable;
    int M;
    int size;
public:
    /**
     * 传参构造
     * @param M
     */
    HashTable(int M) : M(M), size(0) {
        // 这里的括号是为了初始化为0,这就可以不用写下面的代码,当然在后面add之类的操作,就不需要动态分配内存.
        // this->hashtable = new map<Key, Value> *[M]();
        this->hashtable = new map<Key, Value> *[M];
        for (int i = 0; i < M; i++) {
            this->hashtable[i] = new map<Key, Value>;
        }
    }

    /**
     * 默认构造
     */
    HashTable() {
        HashTable(initCapacity);
    }

    /**
     * 析构函数,释放内存
     */
    ~HashTable() {
        free(M);
    }
private:
    /**
     * 释放内存
     * @param M
     */
    void free(int M) {
        for (int i = 0; i < M; i++) {
            if (hashtable[i])
                delete hashtable[i];
        }
        delete[]hashtable;

};

Para la implementación de la tabla hash hay una función hash bastante importante; primero definimos una nosotros mismos: 

/**
* 哈希函数
* @param key
* @return
*/
int hashFunc(Key key) {
    std::hash<Key> h;
    return (h(key) & 0x7fffffff) % M;
}
Aquí, tras obtener el valor con el hash de std, se le aplica & con 0x7fffffff para eliminar el signo negativo del bit alto y convertirlo en positivo, y después se toma el módulo M.

Ahora, con todo esto, implementemos las operaciones de altas, bajas, modificaciones y consultas.

Operación de inserción

La capa inferior usa un árbol rojo-negro; la inserción se hace con el método insert, construyendo un pair para completarla. Cuando la key ya existe, basta con actualizar el valor; en cuanto a la actualización, usar insert directamente no surte efecto, como en la siguiente prueba: 

 map<string,int> m{{"a",1},{"b",2}};
for(auto i:m) cout<<i.first<<" "<<i.second<<" ";
cout<<endl;
m.insert({{"a",2}});
for(auto i:m) cout<<i.first<<" "<<i.second<<" ";
cout<<endl;
m["a"]=2;
for(auto i:m) cout<<i.first<<" "<<i.second<<" ";
cout<<endl;

Salida: 

a 1 b 2 
a 1 b 2 
a 2 b 2
Por tanto, para modificar el value asociado a una key se puede usar [], o bien eliminar primero y volver a insertar; aquí usaremos este método. 
/**
* 添加新元素
* @param key
* @param value
*/
void add(Key key, Value value) {
    // 拉链法出来的map如果为空,就动态分配一个map,然后进行插入
    // 如果key不存在就看内存是否存在,不存在,就分配,存在就插入
    if (hashtable[hashFunc(key)] == NULL || hashtable[hashFunc(key)]->count(key) == 0) {
        if (hashtable[hashFunc(key)] == NULL)
            hashtable[hashFunc(key)] = new map<Key, Value>;
        hashtable[hashFunc(key)]->insert(make_pair(key, value));
        size++;
        if (size >= maxCapacity())
            resize(2 * M);
    } else {
        // 否则,修改value.
        hashtable[hashFunc(key)]->erase(key);
        hashtable[hashFunc(key)]->insert(make_pair(key, value));
    }
}

Operación de eliminación

Si la key existe, se elimina y se hace size--; en caso contrario, se devuelve una marca de fallo. 

/**
* 移除Key
* @param key
* @return 0 success -1 fail
*/
Value remove(Key key) {
    Value ret = -1;
    // 是否包含key,若包含key,则直接删除
    if (contains(key)) {
        hashtable[hashFunc(key)]->erase(key);
        size--;
    //            if (size == 0) delete hashtable[hashFunc(key)];       // 可以添加这行来动态减少内存
        ret = 0;
        // initCapacity 保证不会越界
        if (size < minCapacity() && M / 2 >= initCapacity) resize(M / 2);
    }
    return ret;
}

Operación de modificación

Ya se mencionó antes; aquí va directamente el código. 

/**
* 重设value
* @param key
* @param value
*/
void set(Key key, Value value) {
    // key不存在
    if (!contains(key))
        hrow "key not exists!";
    // 修改value
    hashtable[hashFunc(key)]->erase(key);
    hashtable[hashFunc(key)]->insert(make_pair(key, value));
}

Operación de consulta

Obtiene el value correspondiente a la key. 

/**
* 获取key对应的value
* @param key
* @return
*/
Value get(Key key) {
    if (contains(key))
        return hashtable[hashFunc(key)]->at(key);
    return 0;
}

Por último, arriba han quedado sin mencionar funciones como contains y resize.

¿Existe la key?

Primero la implementación de la función contains, que simplemente comprueba si la key existe: 

/**
    * 是否包含key
    * @param key
    * @return
    */
bool contains(Key key) {
    return hashtable[hashFunc(key)] == NULL || this->hashtable[hashFunc(key)]->count(key) == 0 ? false : true;
}

Obtener el size 

/**
* 获取哈希表元素个数
* @return
*/
int getSize() {
    return size;
}

Capacidad máxima y capacidad mínima 

/**
    * 最大容量
    * @return
    */
Value maxCapacity() {
    return M * upperTol;
}

/**
    * 最小容量
    * @return
    */
Value minCapacity() {
    return M * lowerTol;
}

Función resize

Completa el ajuste dinámico de la memoria: copia el contenido de la memoria original al espacio recién asignado y libera el espacio original. 

/**
* 动态调整内存,保证时间复杂度O(1)查找
* 把扩容后的操作,平摊到前面每次操作,时间复杂度O(2),那就是O(1)了
* @param newM
*/
void resize(int newM) {
    cout << "resize " << newM << endl;
    map<Key, Value> **newHashTable = new map<Key, Value> *[newM];
    for (int i = 0; i < newM; i++) {
        newHashTable[i] = new map<Key, Value>;
    }
    int oldM = M;
    this->M = newM;
    for (int i = 0; i < oldM; i++) {
        map<Key, Value> m = *(hashtable[i]);
        for (auto p:m)
            newHashTable[hashFunc(p.first)]->insert(make_pair(p.first, p.second));
    }

    free(oldM);
    this->hashtable = newHashTable;
}

Sobrecarga del operador <<

Declaración: 

private:
    template<typename K, typename V>
    // 重载<<操作符
    friend ostream &operator<<(ostream &out, HashTable<K, V> &hashTable);
Definición: 
template<typename K, typename V>
ostream &operator<<(ostream &out, HashTable<K, V> &hashTable) {
    hashTable.print();
    return out;
}

Con esto la tabla hash descrita queda implementada; ahora vamos a probarla:

#include "hash.h"
#include <vector>
int main() {

    vector<string> words{"java", "c++", "c", "c++", "c#", "python", "ruby", "python",
                         "c", "c", "c++", "java", "c++", "rust", "python"};
    HashTable<string, int> ht(1);
    for (string word : words) {
        if (ht.contains(word)) {
            ht.set(word, ht.get(word) + 1);
        } else {
            ht.add(word, 1);
        }
    }
    cout<<ht;
    cout<<"size="<<ht.getSize()<<",maxCapacity="<<ht.maxCapacity()<<",minCapacity="<<ht.minCapacity()<<endl;
    string w="c++";
    ht.remove(w);
    if (ht.contains(w))
        cout << "" << w << ": " << ht.get(w) << endl;
    else
        cout << "No word " << w << " in words" << endl;
    cout<<ht;
    ht.remove("c#");
    ht.remove("java");
    ht.remove("c");
    cout<<"size="<<ht.getSize()<<",maxCapacity="<<ht.maxCapacity()<<",minCapacity="<<ht.minCapacity()<<endl;
    cout<<ht;

    return 0;
}

Resultado de la salida: 

resize 2
resize 4
{c#:1,java:2,ruby:1,c:3,rust:1,python:3,c++:4}
size=7,maxCapacity=12,minCapacity=4
No word c++ in words
{c#:1,java:2,ruby:1,c:3,rust:1,python:3}
resize 2
size=3,maxCapacity=6,minCapacity=2
{python:3,ruby:1,rust:1}
Con esto hemos completado una tabla hash sencilla.

1. Optimizar la tabla hash

En la versión gcc2.9, la tabla hash subyacente modificaba dinámicamente la capacidad usando números primos, así que la optimización parte de esta idea:

Añadir al principio de la clase el siguiente array: 

// 素数数组
const vector<int> capacity = {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317,
                                196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843,
                                50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};
Se elimina el constructor con parámetros y el constructor por defecto se modifica a: 
/**
* 默认构造
* @param M
*/
HashTable()  {
    M = capacity[capacityIndex], size = 0;
    // 这里的括号是为了初始化为0,这就可以不用写下面的代码,当然在后面add之类的操作,就不需要动态分配内存.
    // this->hashtable = new map<Key, Value> *[M]();
    this->hashtable = new map<Key, Value> *[M];
    for (int i = 0; i < M; i++) {
        this->hashtable[i] = new map<Key, Value>;
    }
}
Modificar la función add: tras el size++ se añade el siguiente código: 
if (size >= maxCapacity() && capacityIndex + 1 < capacity.size()) {
    capacityIndex++;
    resize(capacity[M]);
}
Cada resize toma el valor de capacity.

Modificación de la función remove

Tras el size-- se modifica a:

if (size < minCapacity() && capacityIndex - 1 >= 0) {
    capacityIndex--;
    resize(capacityIndex);
}

Con esto, ¡la tabla hash está completa! El código de prueba es el mismo que antes.

Temas relacionados

Comentarios