哈希和哈希表

哈希 Hash

应用：将一串字符串转变为数字

字符串哈希核心代码：

typedef unsigned long long ULL;
const int b=26;//进制 
ULL hash()
{
    ULL sum=0;
    for(int i=1;i<=m;++i)
        sum=sum*b+(ULL)(s[i]-'a'+1);//b进制 
    return sum;
}

哈希表 Hash Table

例题：Code

核心代码

//x、y为一个元素的两个哈希值，使用双哈希思想处理哈希冲突
void insert(int x,int y)                        //将元素插入哈希表
{
    //所有 x 值相同的字符串会储存在一条链表上，用 y 值区分
    nxt[++tot]=poi[x];
    poi[x]=tot;
    end[tot]=y;
}

int query(int x,int y)
{
    for(int i=poi[x];i;i=nxt[i])                //找到则表示存在
    {
        if(end[i]==y)
        {
            return 1;
        }
    }
    return 0;                                   //不存在返回 0
}

---

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.