开放寻址法哈希表

1. 枚举状态

代码语言：javascript

AI代码解释

enum state
{
    EXIST,
    EMPTY,
    DELETE
};

为什么要有DELETE状态？ 原因：表大小为11，如果插入12（->1）,23(->1,冲突，->2) 我们删除12，如果直接将1的状态设置为empty，那我们查找23时，会找到1，发现为empty，就会返回找不到，但实际上时有23的

2. 成员，初始化

代码语言：javascript

AI代码解释

template<class K,class V>
struct hashdata
{
    std::pair<K, V> _kv;
    state _state=EMPTY;
};

template<class K, class V>
class hash
{
public:
    hash()
        :_tables(23)
        ,_n(0)
    { }
private:
    std::vector<hashdata<K, V>> _tables;
    size_t _n;
};

3. 插入

代码语言：javascript

AI代码解释

bool insert(const std::pair<K,V>& kv)
{
    size_t hash0 = kv.first % _tables.size();
    size_t hashi = hash0;
    size_t i = 1;
    int flag = 1;
    while (_tables[hashi]._state == EXIST)
    {
        hashi = (hash0 + i) % _tables.size();
        ++i;
    }
    _tables[hashi]._kv = kv;
    _tables[hashi]._state = EXIST;
    ++_n;
    return true;
}

当位置存在时，就一直找，找到不为存在时就插入

(1) 二次探测：由于直接这么探测，要是数据堆积那么效率较低 因此，可以将+i改成+-i方，让数据更加分散 其它都一样，将hash0 + i改为hash+i*i即可

(2) 双重散列法 由于二次探测在冲突时+-的值时一样的，依旧不能解决堆积问题 因此，可以再用一个独立的函数去计算+-的值 要求：函数值<M且与M互质（否则就是在原地几个数中踏步）

4. 扩容

将原来的vector拷贝到新的更大的vector 但是由于size不一样，开放寻址的_tables.size()爷不一样，因此需要重新建立关系 并且，不是满了扩容，而是当负载超过一定数时就扩容

代码语言：javascript

AI代码解释

if (_n * 100 / _tables.size() >= 70)
{
    hash<K, V> newhash;
    newhash._tables.resize(2 * _tables.size());
    for (auto& e : _tables)
    {
        if (e._state == EXIST)
        {
            newhash.insert(e._kv);
        }
    }
    _tables.swap(newhash._tables);
}

可以参考现代写法，建一个新的哈希表类，再复用插入逻辑，再交换两个vector

5. 质数处理

2 * _tables.size()由于新哈希表的大小为两倍以前的，因此一定不是质数 解决方案：弄一个质数数组，达到负载就取新的值

代码语言：javascript

AI代码解释

newhash._tables.resize(prim(_tables.size()+1));

写了个二分查找，找到最小的大于s的数

代码语言：javascript

AI代码解释

inline size_t prim(size_t s)
{
    static const size_t prime_list[] =
    {
        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
    };
    const size_t n = sizeof(prime_list) / sizeof(prime_list[0]);
    size_t left = 0, right = n;
    while (left < right)
    {
        size_t mid = left + (right - left) / 2;
        if (prime_list[mid] < s)
            left = mid + 1;
        else
            right = mid;
    }
    if (left < n)
        return prime_list[left];
    return prime_list[n - 1];
}

6. Find

代码语言：javascript

AI代码解释

hashdata<K, V>* Find(const K& key)
{
    size_t hash0 = 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();
        ++i;
    }
    return nullptr;
}

7. 转无符号整型

由于上面写的代码仅仅是针对于无符号整型的 但是其它的可以用仿函数的方式转

代码语言：javascript

AI代码解释

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

template<>
struct hashfunc<std::string>
{
    size_t operator()(const std::string& str)
    {
        size_t hash = 0;
        for (auto&e:str)
        {
            hash += e;
            hash *= 131;
        }
        return hash;
    }
};

在内置类型，如double等可以直接强转 但是，string也可能出现在哈希表中，因此对模板进行特化，优先走特化函数 因此，哈希表要转2次，传值->无符号整型->哈希函数映射哈希值BKDR哈希 String如何转无符号整型 如果将每一位简单相加，那么很容易冲突 因此，可以加一位再乘一个质数（选择131）以减少冲突