从0到1打牢算法基础之手写一个哈希表

0.导语

目的：手写实现一个哈希表，采用拉链法构建，每个hash(key)对应的是一个红黑树。

看起来很简单，但可以学到很多东西。实现语言：C++。

为了打牢算法基础，github开了个仓库，来完成后面算法基础的应用与实现，地址：

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

也可以点击原文阅读。

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，可以通过来修改，还可以先删除，再插入，这里就用这个方法。