Kingsman C++ハッシュテーブル知識点

一般ハッシュ
(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つの値の衝突確率の低い小さい技巧を取ります:型を取る数は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];
}