链地址法（哈希桶）详解与C++实现

创作时间:

作者:

@小白创作中心

链地址法（哈希桶）详解与C++实现

引用

CSDN

https://m.blog.csdn.net/2301_82135086/article/details/144973584

链地址法（哈希桶）

链地址法是一种解决哈希冲突的方法。与开放定址法不同，链地址法中所有的数据不再直接存储在哈希表中，而是通过指针将冲突的数据链接成一个链表，挂在哈希表的相应位置下。这种方法也被称为拉链法或哈希桶。

负载因子与扩容机制

链地址法的负载因子没有限制，可以大于1。负载因子越大，哈希冲突的概率越高，但空间利用率也越高；负载因子越小，哈希冲突的概率越低，但空间利用率也越低。在STL中，unordered_xxx容器的最大负载因子通常控制在1，当负载因子大于1时就会触发扩容操作。

示例演示

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

h(19) = 8
h(30) = 8
h(5) = 5
h(36) = 3
h(13) = 2
h(20) = 9
h(21) = 10
h(12) = 1
h(24) = 2
h(96) = 8

C++代码实现

链地址法的C++代码实现如下：

namespace hash_bucket
{
    // 仿函数
    template<class K>
    struct HashFunc
    {
        size_t operator()(const K& key)
        {
            return (size_t)key;
        }
    };

    // string类型的特化版本
    template<>
    struct HashFunc<string>
    {
        size_t operator()(const string& s)
        {
            size_t hash = 0;
            for (auto ch : s)
            {
                hash += ch;
            }
            return hash;
        }
    };

    // 哈希表节点结构
    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
    {
    public:
        HashTable()
            : _tables(__stl_next_prime(0))
            , _n(0)
        {}

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

        Hash hash;

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

        bool Erase(const K& key)
        {
            size_t hashi = hash(key) % _tables.size();
            Node* cur = _tables[hashi];
            Node* prev = nullptr;
            while (cur)
            {
                if (key == cur->_kv.first)
                {
                    if (prev == nullptr)
                    {
                        _tables[hashi] = cur->_next;
                    }
                    else
                    {
                        prev->_next = cur->_next;
                    }
                    delete cur;
                    --_n;
                    return true;
                }
                prev = cur;
                cur = cur->_next;
            }
            return false;
        }

        bool Insert(const pair<K, V>& kv)
        {
            if (_n == _tables.size())
            {
                vector<Node*> newtables(__stl_next_prime(_tables.size()) + 1);
                for (size_t i = 0; i < _tables.size(); i++)
                {
                    Node* cur = _tables[i];
                    while (cur)
                    {
                        Node* next = cur->_next;
                        size_t hashi = hash(cur->_kv.first) % newtables.size();
                        cur->_next = newtables[hashi];
                        newtables[hashi] = cur;
                        cur = next;
                    }
                    _tables[i] = nullptr;
                }
                _tables.swap(newtables);
            }

            size_t hashi = hash(kv.first) % _tables.size();
            Node* newnode = new Node(kv);
            newnode->_next = _tables[hashi];
            _tables[hashi] = newnode;
            ++_n;
            return true;
        }

    private:
        vector<Node*> _tables;
        size_t _n = 0;
    };
}