哈希表的底层实现(2)---C++版

目录

链地址法Separate Chaining——哈希桶的模拟实现

超大重点分析：

两种方法对比

---

由于在上次的哈希表的底层实现(1)---C++版已经详细的阐述了相关的结构和原理，哈希表的实现方法主要分为链地址法和开放定址法。开放定址法上次已经实现过了，这次我们实现一下链地址法。

链地址法Separate Chaining——哈希桶的模拟实现

哈希桶的结构和链表是完全一样的，我们这边选择在每个vector里面装入单链表就可以了，比较简单嘛，所以每个结点和成员都是指针。

#include<iostream>
#include<vector>
using namespace std;

template<class K>
struct Hashfunc//仿函数
{
    int operator()(const K& key)
    {
        return (int)key;
    }
};

struct Hashfunc<string>//结构体名字必须一致才省略模板
{
    int operator()(const string& key)
    {
        int hashi = 0;
        for (auto e : key)
        {
            hashi = hashi * 31;
            hashi = hashi + e;
        }
        return hashi;
    }
};
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
{
    typedef Hashnode<K, V> node;
public:
    Hashtable()
    {
        _tables.resize(10, nullptr);//先初始化存有10个空指针的数组
    }
    ~Hashtable()//需要自己写析构函数的
    {
        for (int i = 0; i < _tables.size(); i++)
        {
            node* cur = _tables[i];
            while (cur)
            {
                node* next = cur->_next;
                delete cur;
                cur = next;
            }
            _tables[i] = nullptr;

        }
    }

    bool Insert(const pair<K, V>& kv)
    {
        hash ha;
        // 负载因子==1扩容
        if (n == _tables[size])
        {
            /*Hashtable<K, V> newHT;
            newHT._tables.resize(_tables.size() * 2);
            for (size_t i = 0; i < _tables.size(); i++)
            {
                node* cur = _tables[i];
                while(cur)
                {
                    newHT.Insert(cur->_kv);//用以前复用的逻辑有点浪费空间了
                    cur = cur->_next;
                }
            }*/
            vector<node*>newht.resize(_tables.size() * 2, nullptr);
            for (int i = 0; i < _tables.size(); i++)
            {
                node* cur = _tables[i];
                while (cur)
                {
                    node* next = cur->_next;
                    // 旧表中节点，挪动新表重新映射的位置
                    size_t hashi = ha(cur->_kv.first) % newht.size();
                    // 头插到新表，当然使用尾插也可以
                    cur->_next = newht[hashi];//头插的逻辑
                    newht[hashi] = cur;
                    cur = next;
                }
                _tables[i] = nullptr;//置空了头结点后面的结点也就找不到了，其实感觉不置空也没什么问题
            }
            _tables.swap(newht);//再交换一下
        }
        size_t hashi = ha(kv.first) % _tables.size();
        //头插
        node* newnode = new(kv);//通过kv构造一个新结点，需要合适的构造函数
        newnode->_next = _tables[hashi];
        _tables[hashi] = newnode;
        n++;
    }

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

    bool Erase(const K& key)
    {
        hash ha;
        if (Find(key) == nullptr)
        {
            return false;
        }
        else
        {
            size_t hashi =ha(K) % _tables.size();
            node* cur = _table[hashi];
            node* prev = nullptr;
            while (cur)
            {
                if (cur->_kv.first == key)
                {
                    if (prev == nullptr)
                    {
                        _tables[hashi] = cur->_next;
                    }
                    else
                    {
                        prev->_next = cur->_next;
                    }
                    delete cur;
                    cur = nullptr;
                    --n;
                    return true;
                }
                prev = cur;
                cur = cur->_next
            }
        }
    }
private:
    vector<node*> _tables;// 使用指针数组
    size_t n = 0;//负载因子
};

超大重点分析：

为什么需要自己写析构函数呢？因为如果让系统调用默认构造的话，成员中负载因子属于内置类型编译器不处理，然后vector属于自定义类型，编译器会调用vector的默认构造，这样vector里面的单链表就没有办法析构了，就会照成内存泄漏。

为什么扩容不复用insert了呢，先说一下为什么会需要扩容，随着数据的不断大量的插入单链表，肯定在某种情况下会使得某个链表过于长，这样在查找哈希表的时候会使得时间复杂度过于大了，所以引入负载因子n进行控制，当n == size时就扩容，为什么在扩容时不建议复用呢，因为这样不断的创造新的结点而放着旧结点不直接拿来用的话会比较浪费空间，创造一个结点的消耗还是比较大的。

为什么这边需要写构造函数，因为insert传的是pair，那根据这个pair构造新结点的话需要自己写一个构造，默认构造用不上。

为什么这边哈希桶状的结构是单链表而不是直接使用list或者C++11新加入的forward_list呢，首先没说不可以，但是用单链表不是更简单吗，forward_list尽量少用。

vector<list<pair<K, V>>> _tables;  // 指针数组

像上面这种就是使用list的写法，但是到时候封装的iterator实现起来会比较困难

struct Bucket//联合体
{
       list<pair<K, V>> _lt;
       map<K, V> _m;
       size_t _bucketsize;   // >8 map  <=8 list

};
vector<Bucket> _tables;

但是呢就算是有扩容操作还是会有人故意使用一些很极端的数据使得即使多次扩容还是显得某个链表的插入数据很多，导致每个链表插入数据的数目不平衡。所以为了解决这种情况，有些人会选择当负载因子过大时转而使用搜索树map来代替list实现存储，如上：

最后一个问题，为什么使用头插呢，因为其实无论是头插还是尾插在Find还是erase都没什么显著差别的，但是在扩容时头插会比尾插更有优势，因为每个结点刚开始初始化时的_next结点都是空

这样当头插到开头时每次指向的都是空，这样就不会把多余的结点带出来了，如果是尾插就需要最后再手动将_next置空。

两种方法对比

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上： 由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a ，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。