[编程笔记]-Hash_Table哈希表

概念

通过哈希函数（自定义，一般是取模），把数据映射到哈希表上。

听不懂就对了，听得懂也没必要看原理了(～￣▽￣)～

当然，如果已经学过离散化的，理解起来可能方便些。

为了方便学习，这里挂一个离散化链接：
“[编程笔记]-Discretization离散化”

顺便也挂一个字符串哈希吧，毕竟同根同源~
“[编程笔记]-String_Hash字符串哈希”

实现

映射

这点就讲讲哈希函数，为了减少哈希冲突，我们一般都会选择模一个质数。

处理冲突

有两种方式：拉链法（或者挂链法之类的）和开放寻址法。

拉链法

就是在哈希表上每一个节点后都拉一条链表，遇到冲突的直接插到链表后面，或者用类似链式前向星的方法插到表头。

开放寻址法

遇到冲突想办法找别的空位子坐下。经验表明，一般要开题目要求范围内的两到三倍。

需要注意的是，开放寻址法中，因为查询也是照着插入的方式一个一个找的，所以如果真的删除了元素的话，那么就会使查找过程异常，所以一般都是打个标记。（删除过程和查询过程一模一样hh）

y总の奇妙比喻belike: 就像澈硕找坑位一样，这个有人，欸下一个，找到空的，欸就你了！

寻找

靠哈希函数找出当前值应该在的位置，然后挂链法就顺着链表找一遍，开放寻址法麻烦一点，一般暴力做法就是绕着找一圈。

代码

拉链法

鉴于尾插法过于简单，这里使用头插法。

class Hash{
    public:
        int hd[N],ne[N],vl[N],idk;
        void init(){
            for(int i=0;i<N;i++){
                hd[i]=-1;
            }
        }
        int hash(int x){
            return (x%N+N)%N;//防负数
        }
        void insert(int x){
            vl[++idk]=x;
            int key=hash(x);
            ne[idk]=hd[key];
            hd[key]=idk;
        }
        bool query(int x){
            int key=hash(x);
            for(int i=hd[key];i!=-1;i=ne[i]){
                if(vl[i]==x)return true;
            }
            return false;
        }
}hs;

开放寻址法

本模板中无删除功能，如有需要请自行添加，因为和查找功能基本上没有区别，只需要再单开一个判断是否删除的数组就行了。

class Hash{
    public:
        int h[N];
        void init(){
            memset(h,0x3f,sizeof(h));
        }
        int hash(int x){
            return (x%N+N)%N;
        }
        int find(int x){
            int k=hash(x);
            while(h[k]!=nb&&h[k]!=x){
                if(++k==N)k=0;
            }
            return k;
        }
        void insert(int x){
            int k=find(x);
            h[k]=x;
        }
        bool query(int x){
            int k=find(x);
            return h[k]==x;
        }
}hs;

完结撒花o(￣︶￣)o