哈希表核心原理与 C++ 实现详解

保证负载因子 < 1，一定有位置存储。

b. 查找：从哈希值的位置开始查找，一直向后查找，遇到查找值或遇到 EMPTY 则查找结束。

对于此类哈希表的存储，需要为表中数据设置状态（EXIST，EMPTY，DELETE），否则如果将 30 删除将无法查找到 20。

c. 公式： h(key) = hash0 = key % M, 哈希值冲突 h(key, i) = hashi = (hash0 + i) % M , i = {1, 2, 3, ..., M-1 }

2. 二次探测

依次左右按二次方跳跃探测，遇到哈希表的头尾则回绕。

公式： h(key) = hash0 = key % M, 哈希值冲突 h(key, i) = hashi = (hash +- i^2) % M , i = {1, 2, 3, ..., M/2 }

3. 双重散列探测

较为复杂，这里不做介绍。

以下为哈希表实现代码：

#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;

enum STATE {
    EXIST, // 存在
    EMPTY, // 空
    DELETE // 删除
};

// stl_hashtable.h C++库中选择哈希表大小的方法
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] = { 
    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, 3221225473, 4294967291 
};

inline unsigned long __stl_next_prime(unsigned long n) {
    const unsigned long* first = __stl_prime_list;
    const unsigned long* last = __stl_prime_list + __stl_num_primes;
    const unsigned long* pos = lower_bound(first, last, n);
    return pos == last ? *(last - 1) : *pos;
}

// JAVA template<class K, class Hash = hash_func<K>>
size_t table_size(const K& key) {
    size_t x = 16;
    size_t num = (1 << (x - 1)); // 初始值设为 2^16
    size_t hash0 = (Hash()(key) & (num - 1)) ^ (Hash()(key) >> x); // 后 x-1 位与前 32-x 位异或
    return hash0;
}

// 整型转换仿函数
template<class K>
struct hash_func {
    size_t operator()(const K& key) {
        return (size_t)key;
    }
};

template<>
struct hash_func<string> // string 常用，对其特化
{
    // BKDR
    size_t operator()(const string& s) {
        size_t ret = 0;
        for (auto e : s) {
            ret += e * 131;
        }
        return ret;
    }
};

namespace hash_tables {
    template<class K, class V>
    struct hash_data {
        pair<K, V> _data;
        STATE _state = EMPTY;
    };

    template<class K, class V, class Hash = hash_func<K>>
    class hash_table {
    public:
        using data_type = pair<K, V>;
        using hash_type = hash_data<K, V>;
        using key_type = K;

    public:
        hash_table() : _tables(__stl_prime_list[0]), _size(0) {
            size_t start_num = 0;
            _tables.resize(__stl_prime_list[start_num]);
        }

        pair<hash_type*, bool> insert(data_type data) // 采用除法散列法
        {
            // 冗余值不插入
            if (find(data.first).second == true) return { nullptr, false };

            // 更新哈希表大小 负载因子大于 0.7 则扩容
            if ((_size * 10 / _tables.size()) > 7) {
                hash_table<K, V> tmphash;
                tmphash._tables.resize(__stl_next_prime(_tables.size() + 1));
                for (auto& e : _tables) {
                    tmphash.insert(e._data); // 需要重新插入，哈希表大小不同，映射的值也不同
                }
                _tables.swap(tmphash._tables);
            }

            // 哈希表的映射
            size_t flag = -1;
            size_t i = 0;
            size_t hash0 = _hash(data.first) % _tables.size(); // _tables.size() 的值为 M
            size_t hashi = hash0;
            while (_tables[hashi]._state == EXIST) {
                hashi = linear_search(hash0, i); // 以线性探测为例
            }
            _tables[hashi]._data = data;
            _tables[hashi]._state = EXIST;
            ++_size;
            return { &( _tables[hashi]), true };
        }

        pair<hash_type*, bool> find(key_type key) // 线性探索的查找
        {
            size_t i = 0;
            size_t flag = -1;
            size_t hash0 = _hash(key) % _tables.size(); // key 需要支持整型的转换
            size_t hashi = hash0;
            while (_tables[hashi]._state != EMPTY && _tables[hashi]._data.first != key) // key 的类型需要支持等于的比较
            {
                hashi = linear_search(hash0, i);
            }
            if (_tables[hashi]._state == EMPTY) return { nullptr, false };
            else return { &( _tables[hashi]), true };
        }

        bool erase(key_type key) {
            if (find(key).second == false) return false;
            (*(find(key).first))._state = DELETE;
            --_size;
            return true;
        }

    private:
        vector<hash_type> _tables;
        size_t _size = 0;
        Hash _hash;

    private:
        // 线性探索
        size_t linear_search(size_t hash0, size_t& i) // 返回 hashi 的值
        {
            ++i;
            hash0 = (hash0 + i) % _tables.size();
            return hash0;
        }

        // 二次探测
        size_t bidirectional_search(size_t hash0, size_t& i, size_t& flag) {
            // 先加后减
            if (flag == -1) {
                flag = 1;
                if(i <= _tables.size() / 2) ++i;
            }
            if (flag == 1) flag = -1;
            hash0 = (hash0 + i * i * flag) % _tables.size();
            return hash0;
        }
    };
}

五、链地址法

最常用的方法之一，用指针数组（即数组中存放节点的指针）的方式处理哈希冲突。

对于极端情况下，某个桶长度特别长，可以将其转换为红黑树（JAVA 采用的方法）。

以下为哈希桶的实现代码：

// 哈希桶
namespace hash_buckets {
    template<class K, class V>
    struct hash_node // 采用单链表的形式
    {
        pair<K, V> _data;
        hash_node* _next = nullptr;
    };

    template<class K, class V, class Hash = hash_func<K>>
    class hash_table {
    public:
        using key_type = K;
        using data_type = pair<K, V>;
        using node_type = hash_node<K, V>;
        using link_type = node_type*;
        using self = hash_table<K, V, Hash>;

    public:
        hash_table() : _tables(__stl_prime_list[0]), _size(0) {}

        ~hash_table() {
            for (auto& head : _tables) {
                link_type cur = head;
                while (cur) {
                    head = cur->_next;
                    delete cur;
                    cur = head;
                }
            }
            _tables.~vector();
        }

        hash_table(const hash_table& ht) {
            self _tmpht;
            _tmpht._tables.resize(ht._tables.size());
            for (const auto& head : ht._tables) {
                link_type cur = head;
                while (cur) {
                    link_type next = cur->_next;
                    _tmpht.insert(cur->_data);
                    cur = next;
                }
            }
            _tables.swap(_tmpht._tables);
            _size = ht._size;
        }

        hash_table& operator=(hash_table ht) {
            _tables.swap(ht._tables);
            _size = ht._size;
            return *this;
        }

    public:
        pair<link_type, bool> insert(data_type data) {
            if (find(data.first).second == true) return { nullptr, false };

            // 负载因子大于等于 1 时扩容
            if ((_size / _tables.size()) >= 1) // 均为 size_t,最后结果会保留整数
            {
                // 采用直接移动节点的方法，否则需要再创造新节点删除旧节点
                vector<link_type> newtables(__stl_prime_list[_tables.size() + 1]);
                //vector<link_type> newtables((_tables.size()) * 2);
                for (auto& head : _tables) {
                    link_type cur = head;
                    while (cur) {
                        link_type next = cur->_next;
                        size_t hash0 = _hash(cur->_data.first) % newtables.size();
                        if (newtables[hash0] != nullptr) cur->_next = newtables[hash0];
                        newtables[hash0] = cur;
                        cur = next;
                    }
                }
                _tables.swap(newtables);
            }

            size_t hash0 = _hash(data.first) % _tables.size();
            link_type newnode = new node_type;
            newnode->_data = data;
            if(_tables[hash0] != nullptr) newnode->_next = _tables[hash0];
            _tables[hash0] = newnode;
            ++_size;
            return { _tables[hash0], true };
        }

        pair<link_type, bool> find(key_type key) {
            size_t hash0 = _hash(key) % _tables.size();
            link_type cur = _tables[hash0];
            while (cur) {
                if (cur->_data.first == key) return { cur, true };
                cur = cur->_next;
            }
            return { nullptr, false };
        }

        bool erase(key_type key) {
            pair<link_type, bool> ret = find(key);
            if (ret.second == false) return false;
            else {
                size_t hash0 = _hash(key) % _tables.size();
                link_type cur = _tables[hash0];
                link_type prev = _tables[hash0];
                while (cur) {
                    if (cur->_data.first == key) {
                        if (cur == _tables[hash0]) _tables[hash0] = cur->_next;
                        else prev->_next = cur->_next;
                        delete cur;
                        --_size;
                        return true;
                    }
                    prev = cur;
                    cur = cur->_next;
                }
                return false;
            }
        }

    private:
        vector<link_type> _tables; // 便于实现 iterator
        size_t _size = 0;
        Hash _hash;
    };
}

六、整型转换

1. 一般采用仿函数的方式转换

// 整型转换仿函数
template<class K>
struct hash_func {
    size_t operator()(const K& key) {
        return (size_t)key;
    }
};

2. 对于 string 类型的整型转换

可以参考 BKDR 哈希 string 算法：每次字母 ASCII 值相加前先*131(13331) 后再相加，能有效减少哈希冲突。

template<>
struct hash_func<string> // string 常用，对其特化
{
    // BKDR
    size_t operator()(const string& s) {
        size_t ret = 0;
        for (auto e : s) {
            ret += e * 131;
        }
        return ret;
    }
};

3. hash 表对于 key 类型的要求

a. 能转换为 size_t 类型（映射） b. 支持等于的比较（查找中的要求）