[数据结构与算法]模拟实现Hash-Table线性探测/开散列

这篇文章都是以如何模拟实现hash(线性探测)，关于Hash-Table介绍这里只说大概，方便了解。

概念

Hash-Table也叫散列表，哈希表，是根据关键字（key）来直接访问对应存储值的的数据结构。 虽然说是根据关键字，但其本质还是通过 vector 的下标来找到对应值。

构建

当我们决定构建一个哈希表的时候，就需要用到一个 vector ，vector 里面存储的值为了方便我们之后使用，会有两个参数： 1、pair ，为了我们之后放数据使用 2、state ，这个值的作用就是为了插入数据的时候判断，这个位置能否插入，因为我们插入数据再删除，我们如何把这个位置变为一个不可使用的值？state 就是为了解决这个问题的。

先将要放的数据类型和一些其他配置写好：

enum State
{
    EMPTY,
    EXITS,
    DELETE
};
?
template <class K,class V>
struct HashData
{
?
    pair<K, V> _kv;
    State _state;
};

vector 里面要放的数据就是这个 HashData。

然后我们正式就可以开始写 HashTable 了。

template <class K,class V>
class HashTable
{
    typedef HashData<K,V> Data;
?
?
?
    vector<Data> _table;
    size_t _size = 0;
};

在插入之前，我们要了解的几点：

1、如何插入

通过将传过来的 K （可能是整数，或者是字符串）来进行处理，得到对应的下标，这个下标有一个特点，不同的值要对应不同的下标，然后在下标对应的值放上要存储的数据。

2、如果插入的位置已经有值了怎么办

那就有两种办法：

线性探测和二次探测，这里分别说一下是什么意思。

线性探测：如果当前位置有值了，就往后面找空位置，然后放上数据，隐患是很容易出现需要找一整个 vector 的情况，但是能用。

二次探测：如果当前位置有值，就通过平方的办法来找下标，如果平方大了，就取余

3、空间不够了怎么办

扩容，然后将原本的数据值交给扩容的空间。

插入

思路：

插入之前，先判断这个数据在表内是否存在，如果存在，就不用放进去（不是mul版本），然后判断一下空间大小，如果空间不是很足，就先扩容，之后再通过传进来的第一个值来找到对应下标。

这里有一个问题就是，如何确保传进来的第一个数据是 string 类型还能找到其下标，这里就要通过仿函数了。

就跟之前模拟实现的那些比较大小的值一样，这里我们可以重载 string ，然后找到其对应的值。

template <class K>
struct DefaultHash
{
    size_t operator()(const K& key)
    {
        return (size_t)key;
    }
};
?
template<>
struct DefaultHash < string >
{
    size_t operator()(const string& key)
    {
        size_t hash = 0;
        for (auto ch : key)
        {
            hash += hash * 13 + ch;
        }
    }
};

通过重载来完成找到下标的办法，这里字符串的计算方法来自《The C Programming Language》，这书很长，但是这个网址找到了常用的几种算法：各种字符串Hash函数 - clq - 博客园 (cnblogs.com)

这里选取的是第一种。

如何判断要不要孔扩容，这里就用存储大小来判断，如果一开始空表肯定是要扩容的，当存储的数据大于 7/10 也可以扩容。

扩容就是新开一个table，然后往里面插入当前数组的有效值（不为空或者删除的值），然后交换啷个vector 即可。

    bool Insert(const pair<K, V>& kv)
    {
        if (Find(kv.first)){
            return false;
        }
        
        //空vector 或者是存储数据超过七成
        if (_table.size() == 0 || _size * 10 / _table.size() >= 7)
        {
            //判断新开空间大小
            size_t newsize = _size == 0 ? 10 : _size * 2;
            HashTable<K, V> newtable;
            newtable._table.resize(newsize);
            //遍历插入
            for (auto& e : _table)
            {
                if (e._state == EXITS)
                    newtable.Insert(e._kv);
            }
            newtable._table.swap(_table);
        }
?
        //通过创建对象来使用仿函数
        Func f;
        size_t pos = f(kv.first);
        pos %= _table.size();
        
        //如果当前位置是已经有值的，就继续往后找，直到为空或者已经删除的位置
        while (_table[pos]._state == EXITS)
        {
            pos++;
            pos %= _table.size();
        }
        
        //将这里的值覆盖即可
        _table[pos]._kv = kv;
        //别忘了打上标记表示这里已经有值
        _table[pos]._state = EXITS;
        _size++;
        return true;
    }

查找

查找的思路跟插入差不多，找到下标然后判断，如果这个位置不是就往后找，直到为空

    Data* Find(const K& key) 
    {
        //为空就不用找了
        if (_table.size() == 0)
            return false;
        //找下标
        Func func;
        size_t pos = func(key);
        pos %= _table.size();
        //一直找到为空的位置
        while (_table[pos]._state != EMPTY)
            {
                if (_table[pos]._state != DELETE && _table[pos]._kv.first == key){
                return &_table[pos];
            }
            pos++;
            pos %= _table.size();
        }
        return nullptr;
    }

删除

这...，直接用Find找，找到了就直接将那个位置的 state 置为删除状态即可。

    bool Earse(const K& key)
    {
        auto tmp = Find(key);
        if (tmp){
            tmp._state = DELETE;
            return true;
        }
        return false;
    }

哈希桶

之前所使用的 vctor 里面放数据，如果有位置上有数据就往后移，这种办法称之为：闭散列，因为所有的数组都会在 vector 里面不停增长，为了解决这种闭散列可能出现的拥挤问题，这里引出了下面要说的：开散列。

开散列跟闭散列最大的不同在于，闭散列存放的是值，而开散列存放的是指针，这里说一下，指针也分单向双向之类，这里使用的是单向不循环链表。

当我们要存放值的位置上有数据了，我们就不需要再往后找空位置了，只需要用指针将它们连接起来即可。

所以也不需要什么 state 来看当前节点状态，下面就正式来实现一下：

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)
    {}
};

插入

思路其实跟之前那个差不多，都是找下标然后插入，空间不够扩容，这里要说一下的是扩容，当我们把原先位置的 vector 交换给新的 vector 之后，原本的 vector 被释放，但是里面存放的值，也就是我们之前节点的数据可不会被释放，就会出现内存泄漏的情况，为了解决这种问题，我们可以直接在新 vector 里面插入旧 vector 的节点，这样即避免了新开辟节点，也避免了上面的内存泄露。

这里放上代码：

    bool Insert(const pair<K, V>& kv)
    {
        Func Hf;
        if (Find(kv.first))
            return false;
            
        //跟之前的 0.7 不同，这里满了就扩容
        if (_table.size() == _size)
        {
            //算新开的空间大小
            size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
            //新开空间
            vector<Node*> newtable;
            newtable.resize(newsize, nullptr);
?
            //遍历之前 vector 里面的所有节点   bool Insert(const pair<K, V>& kv)
    {
        if (Find(kv.first))
            return false;
?
        //跟之前的 0.7 不同，这里满了就扩容
        if (_table.size() == _size)
        {
            //算新开的空间大小
            size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
            //新开空间
            vector<Node*> newtable;
            newtable.resize(newsize, nullptr);
?
            //遍历之前 vector 里面的所有节点
            for (int i = 0; i < _table.size(); i++)
            {
                Node* cur = _table[i];
                while (cur)
                {
                    //当我们插入节点之后，这个节点的 next 就指向了空，为了避免出现这个节点下面还有数据的情况，所以要先保留一下
                    Node* next = cur->_next;
?
                    size_t pos = (Hf(cur->_kv.first)) %= newsize;
                    cur->_next = newtable[pos];
                    newtable[pos] = cur;
?
                    cur = next;
                }
                //将原本位置职位空
                _table[i] = nullptr;
            }
            //交换空间
            newtable.swap(_table);
        }
?
        //如果无需扩容/扩容结束，就让新节点的 next 直接指向下标所处的空间，然后让下标所处的空间指向这个即可，相当于链表的头插
        size_t pos = Hf(kv.first);
        pos %= _table.size();
        Node* newnode = new Node(kv);
        newnode->_next = _table[pos];
        _table[pos] = newnode;
        ++_size;
        return true;
    }
            for (int i = 0; i < _table.size(); i++)
            {
                Node* cur = _table[i];
                while (cur)
                {
                 ?  //当我们插入节点之后，这个节点的 next 就指向了空，为了避免出现这个节点下面还有数据的情况，所以要先保留一下
                    Node* next = cur->_next;
?
                    size_t pos = (Func(cur->_kv.first)) %= newsize;
                    cur->_next = newtable[pos];
                    newtable[pos] = cur;
?
                    cur = next;
                }
                //将原本位置职位空
                _table[i] = nullptr;
            }
            //交换空间
            newtable.swap(_table);
        }
?
        //如果无需扩容/扩容结束，就让新节点的 next 直接指向下标所处的空间，然后让下标所处的空间指向这个即可，相当于链表的头插
        size_t pos = Func(kv.first);
        pos %= _table.size();
        Node* newnode = new Node(kv);
        newnode->_next = _table[pos];
        _table[pos] = newnode;
        ++_size;
        return true;
    }

查找

bool Find(const K& key)
{
    if (_size == 0)
        return false;
?
    Func Hf;
    size_t pos = (Hf(key)) %= _table.size();
    Node* cur = _table[pos];
    while (cur)
    {
        if (cur->_kv.first == key)
            return true;
?
        cur = cur->_next;
    }
    return false;
}

查找就比较简单，所以这里就不打注释了。

删除

bool Erase(const K& key)
{
    if (_size == 0)
        return false;
?
    Func Hf;
    size_t pos = (Hf(key)) %= _table.size();
    Node* cur = _table[pos];
    Node* prev = nullptr;
    while (cur)
    {
        if (cur->_kv.first == key)
        {
            prev == nullptr ? : _table[pos] = nullptr :  _table[pos] = cur->_next;
            delete cur;
            return true;
        }
            prev = cur;
            cur = cur->_next;
    }
?
    return false;
}

单链表的知识，这里要用一个 prev 来保存 cur 上一个节点的位置，之后我们要跳过 cur 将链表链接起来。

如果 prev 等于空，就说明这个位置就是我们要找的，所以直接将这个位置置为 cur 的下一个即可。

析构

虽然在扩容的时候说不需要写析构，但是我们最后一次使用，它不扩容的时候，那些节点还是需要我们自己释放的，所以析构函数还是有必要的。

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