$\Large\color{black}{（填坑）链地址法原理及实现}$

原帖位置

基于链地址法的哈希表类定义：

//哈希表类，模板参数有两个：元素类型，哈希函数（STL中用的是结构体）
template<class Elem, class HashFcn>
class UnorderedSet {
private:
    vector<HashNode<Elem>> base;//存放各链表的头部
    HashFcn hasher;//结构体的哈希仿函数，返回值类型size_t，可供自由选择
    size_t size = 0;

    //扩容
    void rehash();
public:
    //构造函数
    UnorderedSet();

    //插入
    void insert(Elem e);

    //查找
    bool find(Elem e);
};

此时哈希函数不再写在类内，而是利用仿函数结构体，作为模板参数传入该类，和STL一样，此时使用的哈希函数如下（仍然是除留余数法，只不过primeList和idx提到了全局区）：

//整数型数据元素专用哈希函数
template<class Elem>
struct HashIntFcn {
    size_t operator()(Elem e) {
        //std::hash有类似的方法，都是预先判断类型可不可用，报生成错误
        static_assert(is_integral<Elem>(), "Cannot convert to integral type");
        return (size_t)e % primeList[idx];//除留余数法照样可用
    }
};

链地址法处理冲突的时候，所有的同义词都被串成一条链表，此后还有同义词插入时，就往对应的链表中插入就行。此方法下，底层的数组存放的元素不再是元素自身，而是各地址对应链表的头部自身，就像下图一样：

template<class Elem, class HashFcn>
UnorderedSet<Elem, HashFcn>::UnorderedSet()
{
    base.resize(primeList[idx]);
}

此处的base数组中，元素是一般对象类型而不是对象指针类型，原因就是如果使用指针类型，此处会全部初始化为空指针，至于resize的第二个参数设置为new HashNode那更不行，因为resize函数中new只会调用一次，剩余的都是复制，如果这样做，base中任意一个元素指向的都是同一个地址，插入元素时插入的是同一个位置

接下来介绍插入和查找。每个元素在其中都存放在了一个链表节点中，此时如果插入67，需要经历以下几个步骤（不考虑扩容和已经存在的情况）：
1. 计算哈希值，得到哈希地址：$H(67)=67~MOD~13=2$
2. 调用$\text{new}$，构造一个值为67的节点（指针）
3. 找到地址2对应链表的头部，向该链表的头部插入
4. 哈希表大小+1

template<class Elem, class HashFcn>
void UnorderedSet<Elem, HashFcn>::insert(Elem e)
{
    if (find(e)) {
        return;
    }
    if (size == primeList[idx]) {
        rehash();
    }
    //找到哈希地址和对应的链表头部，构造元素的节点
    size_t addr = hasher(e);
    HashNode<Elem>* node = new HashNode<Elem>, * pAddr = &base[addr];
    //执行头部的插入操作
    node->val = e;
    node->nxt = pAddr->nxt;
    pAddr->nxt = node;
    //大小+1
    size++;
}

查找某一元素时，也分以下几步：
1. 计算哈希值，得到哈希地址
2. 找到该地址对应链表的头部
3. 遍历该链表，找到相同元素则查找成功，否则查找失败

template<class Elem, class HashFcn>
bool UnorderedSet<Elem, HashFcn>::find(Elem e)
{
    //找到对应的链表头部
    size_t addr = hasher(e);
    HashNode<Elem>* pAddr = base[addr].nxt;
    //遍历链表寻找元素
    while (pAddr) {
        if (pAddr->val == e) {
            return true;
        }
        pAddr = pAddr->nxt;
    }
    return false;
}

同样，链地址法哈希表也需要定期扩容，以避免链表过长影响效率。扩容的条件和步骤与开放定址法相似，之前的链表节点可以复用

template<class Elem, class HashFcn>
void UnorderedSet<Elem, HashFcn>::rehash()
{
    vector<HashNode<Elem>> newBase(primeList[++idx]);
    for (auto& head : base) {
        while (head.nxt) {
            //把它从原来的链表中取出
            HashNode<Elem>* node = head.nxt;
            head.nxt = node->nxt;
            node->nxt = nullptr;

            //加入到新的链表中
            size_t addr = hasher(node->val);
            HashNode<Elem>* pAddr = &newBase[addr];
            node->nxt = pAddr->nxt;
            pAddr->nxt = node;
        }
    }
    //用新表替换原表
    base.swap(newBase);
}

就目前实现的几个成员函数的平均时复来说，插入和查询都是$O(1)$，扩容是$O(n)$，毫无疑问扩容是很费时间的。此处实现的开放定址法和链地址法都重在基本原理，对于海量数据元素装载的情况尚未考虑完整。STL中考虑到了这样的需求，提供了以下两个成员函数：

void rehash(size_type _count);//为至少为指定数量的桶（链表头部）预留空间
void reserve(size_type _count);//为至少为指定数量的元素预留空间

如果在一开始就调用了这些函数，并且传入了一个较大的参数，就可以事先减少大量冲突处理和扩容重哈希的过程