常用代码模板2（3）——数据结构

小灰灰 2024-03-26 16:08 50阅读 0赞

## 常用代码模板2（3）——数据结构 ##

原文：[常用代码模板2——数据结构][2]

### 一般哈希 ###

(1) 拉链法
        int h[N], e[N], ne[N], idx;
    
        // 向哈希表中插入一个数
        void insert(int x)
        {
            int k = (x % N + N) % N;
            e[idx] = x;
            ne[idx] = h[k];
            h[k] = idx ++ ;
        }
    
        // 在哈希表中查询某个数是否存在
        bool find(int x)
        {
            int k = (x % N + N) % N;
            for (int i = h[k]; i != -1; i = ne[i])
                if (e[i] == x)
                    return true;
    
            return false;
        }
    
    (2) 开放寻址法
        int h[N];
    
        // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
        int find(int x)
        {
            int t = (x % N + N) % N;
            while (h[t] != null && h[t] != x)
            {
                t ++ ;
                if (t == N) t = 0;
            }
            return t;
        }

### 字符串哈希 ###

核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
    小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
    
    typedef unsigned long long ULL;
    ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
    
    // 初始化
    p[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        h[i] = h[i - 1] * P + str[i];
        p[i] = p[i - 1] * P;
    }
    
    // 计算子串 str[l ~ r] 的哈希值
    ULL get(int l, int r)
    {
        return h[r] - h[l - 1] * p[r - l + 1];
    }

[2]: https://www.acwing.com/blog/content/404/