闭散列哈希表

一、什么是 哈希 ？

1.1 哈希概念 与 哈希冲突

在正式介绍闭散列哈希之前，我们需要明确 哈希 的概念。

哈希 ：构造一种数据存储结构，通过 仿函数 hashfunc() ，使 元素的存储位置 与 其对应的键值 建立一一映射关系，在此基础上，可以只凭借 o(1) 的时间复杂度查找到目标元素。

通过以上举例可见，我们对 哈希 其实并不陌生，但是由此衍生出两个问题：

1. 在数据范围集中时，我们可以通过开一定大小的空间实现下标与元素的一一映射；但如果出现这样一组分散的数据 1, 2, 12, 99, 10000, 6 呢？

2. 提前把第一个问题的答案告诉各位： 除留余数法 可以解决问题 —— 开一个大小为 10 的数组，每个数据 % 10 后再存进数组中。

   但，如何避免 “哈希冲突” —— 不同的键值计算出相同的哈希地址 呢？比如：2 % 10 == 12 % 10 == 2，如何规避二者冲突的问题？

1.2 哈希函数

引起哈希冲突的原因很可能是：哈希函数设计的不够合理 —— 哈希函数最好能保证所有元素均匀地分布在整个哈希空间中。

常见的哈希函数：

1. 直接定址法。比如：小写字母次数映射。

2. 除留余数法。

二、闭散列

闭散列：开放定址法 —— 如果发生了 “哈希冲突” 且当前的哈希空间并未被“填满”，此时，把新插入的冲突元素存到 “下一个”空位置 去。

2.1 线性探测

通过上面的解释，相信大家已经明了 线性探测 的基本要义，下面再给出它的定义。

线性探测：从发生冲突的位置开始，依次向后寻找，直到找到下一个空位置为止。

2.2 引入状态量

因此，我们需要在每个哈希地址增加一个状态量 —— empty（空），exist（存在），delete（删除），默认构造把所有位置初始化为 empty ，插入元素的同时将 empty 改为 exist ，删除元素再将 exist 改为 delete 。

通过每个哈希位置的状态量，判断此处是否为空，是否可以插入元素等等。

2.3 闭散列的框架搭建

• 枚举状态量

    enum state
    {
        empty,
        exist,
        delete
    };

• hashdata

    template<class k, class v>
    struct hashdata
    {
        pair<k, v> _kv;
        state _state = empty; // 默认初始化为空
    };    

• hashtable

    template<class k, class v>
    class hashtable
    {
    public:
        hashtable(size_t n = 10)
        {
            _tables.resize(n);// resize() 可以保证 size == capacity
        }
        
    private:
        vector<hashdata<k, v>> _tables;
        size_t _n = 0;// 当前哈希表中的元素个数
    };

2.4 insert() 及引入 hashfunc()

    // 先给出一个基本的 insert 函数
    bool insert(const pair<k, v>& kv)
    {
        if (find(kv.first)) // 未实现的 find()，找到了返回映射的哈希位置指针，没找到返回空
        {
            return false; // 已经存在，插入失败
        }
        
        // 扩容逻辑
        if ((double)_n / _tables.size() >= 0.7) // 将 负载因子 控制在 0.7
        {
            // 创建一个空间为 原表两倍大小 的表
            hashtable<k, v> newtable(2 * _tables.size()); 
            for (size_t i = 0; i < _tables.size(); i++)
            {
                if (_tables[i]._state == exist)
                    newtable.insert(_tables[i]._kv); 
            }
            _tables.swap(newtable._tables);
        }
        
        // 插入逻辑
        size_t hashi = kv.first % _tables.size(); // 计算相应的 哈希地址
        while (_tables[hashi]._state == exist)// 线性探测
        {
            hashi++;
            hashi %= _tables.size();
        }
        // 代码运行到这里则必然找到了一个可以插入的位置
        _tables[hashi]._kv = kv;
        _tables[hashi]._state = exist; // 修改对应状态
        _n++;
        return true;
    }
​
    void test_insert1()
    {
        int arr[] = { 1, 4, 24, 34, 7, 44, 17, 20 };
        hashtable<int, int> ht;
        
        for (auto e : arr)
        {
            ht.insert(make_pair(e, e));
        }
    }

扩容逻辑中复用 insert() 的部分确实精妙绝伦，newtable 的 size 是原表的 2 倍，因此在插入过程中，不会出现重复扩容进而死循环的状态。

以上的 insert() 看上去似乎没什么问题，可是，一旦我们把传入两个 string —— hashtable<string, string> ，再 insert(make_pair<"sort", "排序">) 就出问题了 —— string 类型不支持 size_t hashi = kv.first % _tables.size(); 的方式计算哈希地址!

所以我们需要一个哈希函数 —— hashfunc()（仿函数） ，用于将任意长度的输入数据映射到固定长度输出值（哈希值或散列值）。

    template<class k>
    struct hashfunc
    {
        size_t operator()(const k& key)
        {
            size_t ret = key;
            return ret;
        }
    };
​
    // 为 string 写一个特化版本
    template<>
    struct hashfunc<string>
    {
        size_t operator()(const string& s)
        {
            size_t hash = 0;
            for (auto& e : s)
            {
                hash = hash * 131 + e; // 131 是前辈用大量数据测试得到的值，可以尽大程度避免哈希冲突
            }
            return hash;
        }
    };

有了 hashfunc，我们再对以上的内容做一下改造：

    template<class k, class v, class hash = hashfunc<k>>
    class hashtable
    {
    public:
        hashtable(size_t n = 10)
        {
            _tables.resize(n);
        }
        
        bool insert(const pair<k, v>& kv)
        {
            hash hs;
            if (find(kv.first)) 
            {
                return false;
            }
​
            // 扩容逻辑
            if ((double)_n / _tables.size() >= 0.7) 
            {
                hashtable<k, v> newtable(2 * _tables.size()); 
                for (size_t i = 0; i < _tables.size(); i++)
                {
                    if (_tables[i]._state == exist)
                        newtable.insert(_tables[i]._kv); 
                }
                _tables.swap(newtable._tables);
            }
​
            // 插入逻辑
            size_t hashi = hs(kv.first) % _tables.size(); // hs(kv.first) 利用哈希函数计算 映射的哈希地址
            while (_tables[hashi]._state == exist)
            {
                hashi++;
                hashi %= _tables.size();
            }
            
            _tables[hashi]._kv = kv;
            _tables[hashi]._state = exist; 
            _n++;
            return true;
        }
        
    private:
        vector<hashdata<k, v>> _tables;
        size_t _n = 0;
    };

hash 是一个模板接口，当自定义类型不支持仿函数模板推演的时候，你可以传入自己的 hashfunc 完成对应功能！

2.5 find() 和 erase()

    hashdata<k, v>* find(const k& key)
    {
        hash hs;
        size_t hashi = hs(key) % _tables.size();
        
        while (_tables[hashi]._state != empty) 
        {
            if (_tables[hashi]._kv.first == key && _tables[hashi]._state == exist)
                return &_tables[hashi];
            
            hashi++;
            hashi %= _tables.size();
        }
        
        return nullptr;
    }

中间过程，有些值可能被删除 —— 状态为 delete。

    bool erase(const k& key)
    {
        hashdata<k, v>* ret = find(key);
        if (ret)
        {
            ret->_state = delete;
            --_n;
            return true;
        }
        else
            return false;
    }