哈希表详解：从哈希函数到冲突解决的 C++ 实现

双重散列

• 第一个哈希函数计算出的值发生冲突，使用第二个哈希函数计算出一个跟 key 相关的偏移量值，不断往后探测，直到寻找到下一个没有存储数据的位置为止。
• h1(key) = hash0 = key % M , hash0 位置冲突了，则双重探测公式为：hc(key,i) = hashi = (hash0+ i∗h2(key)) % M，i = {1,2,3,…,M}

开放定址法哈希表结构

enum State { EXIST, //存在 EMPTY, //空 DELETE //被删除 };
template<class K, class V>
struct HashData {
    pair<K, V> _kv;
    State _state = EMPTY;
};

template<class K>
struct HashFunc {
    size_t operator()(const K& key) { return (size_t)key; }
};

template<>
struct HashFunc<string> {
    size_t operator()(const string& s) {
        size_t hash = 0;
        for (auto e : s) {
            hash = hash * 31 + e; //避免'abc'和'acb'这样的字符串冲突，所以*一个素数
        }
        return hash;
    }
};

template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
public:
    HashTable() :_tables(11),_n(0) { }

    bool Insert(const pair<K, V>& kv) {
        if (Find(kv.first)) { return false; }
        //负载因子>=0.7 就扩容
        if (_n * 10 / _tables.size() >= 7) {
            vector<HashData<K, V>> newtables(_tables.size() * 2);
            HashTable<K, V, Hash> newht;
            newht._tables.resize(_tables.size() * 2);
            for (auto data : _tables) {
                //旧表的顺序映射到新表
                if (data._state == EXIST) {
                    newht.Insert(data._kv); //调用 Insert，不用再自己找位置了
                }
            }
            _tables.swap(newht._tables);
        }
        Hash hash;
        //把要比较的值转为无符号整型
        size_t hash0 = hash(kv.first) % _tables.size();
        //第一次算出来的位置
        size_t hashi = hash0;
        size_t i = 1;
        while (_tables[hashi]._state == EXIST) {
            //线性探测
            hashi = (hash0 + i) % _tables.size(); //+1 +2 +3 ……
            ++i;
        }
        _tables[hashi]._kv = kv;
        _tables[hashi]._state = EXIST;
        ++_n;
        return true;
    }

    HashData<K, V>* Find(const K& key) {
        Hash hash;
        size_t hash0 = hash(key) % _tables.size();
        //第一次算出来的位置
        size_t hashi = hash0;
        size_t i = 1;
        while (_tables[hashi]._state != EMPTY) {
            if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key) {
                return &_tables[hashi]; //返回指针
            }
            //线性探测
            hashi = (hash0 + i) % _tables.size(); //+1 +2 +3 ……
            ++i;
        }
        return nullptr;
    }

    bool Erase(const K& key) {
        HashData<K, V>* ret = Find(key);
        if (ret) {
            ret->_state = DELETE;
            return true;
        } else {
            return false;
        }
    }
private:
    vector<HashData<K, V>> _tables;
    size_t _n = 0; //记录已经存放的数据个数
};

链地址法

解决冲突的思路

• 开放定址法中所有的元素都放到哈希表里，链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把 这些冲突的数据链接成一个链表，挂在哈希表这个位置下面，链地址法也叫做拉链法或者哈希桶。
• 链地址法的负载因子没有限制，可以大于 1。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低；stl 中 unordered_xxx 的最大负载因子基本控制在 1，大于 1 就扩容

示例演示

下面演示{19,30,5,36,13,20,21,12,24,96}这一组值映射到 M=11 的表中

代码实现

template<class K,class V>
struct HashNode {
    pair<K, V> _kv;
    HashNode<K, V>* _next;
    HashNode(const pair<K, V>& kv) :_kv(kv) , _next(nullptr) { }
};

template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
    typedef HashNode<K, V> Node;
public:
    HashTable() :_tables(11),_n(0) { }

    //拷贝构造
    HashTable(const HashTable& hashtable) {
        _tables.resize(hashtable._tables.size());
        _n = hashtable._n;
        for (size_t i = 0; i < hashtable._tables.size(); ++i) {
            Node* src_cur = hashtable._tables[i];
            Node* dst_tail = nullptr; //目标对象链表尾（尾插）
            while (src_cur) {
                Node* new_node = new Node(src_cur->_kv);
                if (_tables[i] == nullptr) {
                    _tables[i] = new_node;
                } else {
                    dst_tail->_next = new_node;
                }
                dst_tail = new_node; //指向尾结点
                src_cur = src_cur->_next;
            }
        }
    }

    ~HashTable() {
        for (size_t i = 0; i < _tables.size(); i++) {
            Node* cur = _tables[i];
            while (cur) {
                Node* next = cur->_next;
                delete cur;
                cur = next;
            }
            _tables[i] = nullptr;
        }
    }

    bool Insert(const pair<K, V>& kv) {
        if (Find(kv.first)) { return false; }
        //负载因子==1 时扩容
        if (_n == _tables.size()) {
            vector<Node*> newTable(_tables.size() * 2);
            for (size_t i = 0; i < _tables.size(); i++) {
                Node* cur = _tables[i];
                while (cur) {
                    Node* next = cur->_next;
                    //头插到新表
                    size_t hashi = cur->_kv.first % newTable.size();
                    cur->_next = newTable[hashi];
                    newTable[hashi] = cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
            _tables.swap(newTable);
        }
        size_t hashi = kv.first % _tables.size();
        //头插
        Node* newnode = new Node(kv);
        newnode->_next = _tables[hashi];
        _tables[hashi] = newnode;
        ++_n;
        return true;
    }

    Node* Find(const K& key) {
        size_t hashi = key % _tables.size();
        Node* cur = _tables[hashi];
        while (cur) {
            if (cur->_kv.first == key) {
                return cur;
            }
            cur = cur->_next;
        }
        return nullptr;
    }

    bool Erase(const K& key) {
        size_t hashi = key % _tables.size();
        Node* prev = nullptr;
        Node* cur = _tables[hashi];
        while (cur) {
            if (cur->_kv.first == key) {
                if (prev == nullptr) { //头节点
                    _tables[hashi] = cur->_next;
                } else { //中间节点
                    prev->_next = cur->_next;
                }
                delete cur;
                return true;
            } else {
                prev = cur;
                cur = cur->_next;
            }
        }
        return false;
    }
private:
    vector<Node*> _tables; //指针数组
    size_t _n = 0; //表中存的数据个数
};