最終更新：2026-10-12

STL 手書きハッシュテーブル実装

0.はじめに

目的：ハッシュテーブルを手書きで実装すること。チェイン法で構築し、各hash(key)には赤黒木が対応します。

簡単に見えますが、多くのことが学べます。実装言語：C++。

アルゴリズムの基礎を固めるため、githubにリポジトリを作り、今後のアルゴリズム基礎の応用と実装をそこで行います。アドレス：

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

「原文を読む」をクリックしてもアクセスできます。

1.簡易版ハッシュテーブル

ハッシュテーブルを1つのクラスにカプセル化し、走査の定義と宣言、そしてコンストラクタ、デストラクタの実装を完了します：

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;

};

ハッシュテーブルの実装には、比較的重要なハッシュ関数があります。ここではまず自分で定義します：

/**
* 哈希函数
* @param key
* @return
*/
int hashFunc(Key key) {
    std::hash<Key> h;
    return (h(key) & 0x7fffffff) % M;
}

ここではstdのhashで値を得た後、それを0x7fffffffと&することで高位の負号を取り除いて正数に変え、その後Mで余りを取ります。

これができたので、追加・削除・変更・検索を実装しましょう。

追加操作

基盤には赤黒木を使っており、挿入にはinsertメソッドを使い、pairを構築して完了します。 keyがすでに存在する場合は値を更新するだけです。この更新について、insertを直接使っても効果がありません。例えば下のテストのように：

 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;

出力：

a 1 b 2 
a 1 b 2 
a 2 b 2 

したがって、keyに対応するvalueを変更したい場合は、[]で変更するか、先に削除してから挿入する方法があります。ここではこの方法を使います。

/**
* 添加新元素
* @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));
    }
}

削除操作

keyが存在すれば削除し、size--します。存在しなければ失敗を示す値を返します。

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

変更操作

前述の通りなので、ここではコードを直接示します。

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

検索操作

keyに対応するvalueを取得します。

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

最後に、上にはcontainsやresizeなどの関数がまだ説明されていません。

keyが存在するかどうか

まずcontains関数の実装です。keyが存在するかどうかを判断します：

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

sizeの取得

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

最大容量と最小容量

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

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

resize関数

動的なメモリ調整を行い、元のメモリ内の内容を新しく割り当てた空間にコピーし、元の空間を解放します！

/**
* 动态调整内存,保证时间复杂度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;
}

<<演算子のオーバーロード

宣言：

private:
    template<typename K, typename V>
    // 重载<<操作符
    friend ostream &operator<<(ostream &out, HashTable<K, V> &hashTable);

定義：

template<typename K, typename V>
ostream &operator<<(ostream &out, HashTable<K, V> &hashTable) {
    hashTable.print();
    return out;
}

以上で、上のハッシュテーブルの実装は完了です。今からテストしましょう：

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

出力結果：

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}

以上で、簡単なハッシュテーブルが完成しました。

1.ハッシュテーブルの最適化

gcc2.9バージョンでは、基盤のハッシュテーブルは素数を容量として動的に変更していました。そこで、ここでの最適化はここから出発します：

クラス内部の先頭に次の配列を追加します：

// 素数数组
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};

パラメータ付きコンストラクタを削除し、デフォルトコンストラクタを次のように変更します：

/**
* 默认构造
* @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>;
    }
}

add関数を修正します： size++の後に次のコードを追加します：

if (size >= maxCapacity() && capacityIndex + 1 < capacity.size()) {
    capacityIndex++;
    resize(capacity[M]);
}

毎回のresizeではcapacityから値を取ります。

remove関数の修正

size--の後に修正します：

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

以上で、ハッシュテーブルは完成です！テストコードは上と同じです。

関連トピック

• STL array ソースコード解析 | C++那些事
• STL string 深入解析 | C++那些事
• STL string 面接問題解説 | C++那些事
• STL deque ソースコード解析 | C++那些事
• STL 空基底クラス最適化 EBO | C++那些事
• STL hashtable ハッシュテーブル | C++那些事
• STL イテレータソースコード解析 | C++那些事
• STL list ソースコード解析 | C++那些事
• STL map と multimap | C++那些事
• STL queue と stack ソースコード解析 | C++那些事

コメント