• 哈希表
    • 作用:将庞大的空间,映射到小的空间,集中数据,一般用取模,取模的数尽量取质数,最大程度减小冲突
    • 操作:一 般是添加和查找元素,删除元素通常有一个标记数组,对元素标记为已删除
    • 离散化相似,离散化是特殊的哈希方式,离散化处理的数据是单调的,相对位置不变
    • 映射会出现冲突,如将两个不同的数映射成同一个数
    • 存储结构:
      • 解决了冲突
      • 开放寻址法
        • 仅仅一个数组,数组长度通常为最大范围的2~3倍
        • 存储:当前位置有元素,就移到下一个位置,直到当前位置无元素为止
        • 查找:当前位置有元素且不为x,就移动到下一个位置,直到当前位置是x,后返回下标
        • 代码:
          const int N = 2e5 + 3;const int null = 0x3f3f3f3f;//表示无穷大int h[N];//查找 可以插入的/查找到的位置void find(int x){int k = (x % N + N) % N;//第一个哈希的位置while(h[k] != null && h[k] != x){//当前位置有元素且不为xk ++ ;//后移if(k == N) k = 0;//循环找位置}return k;//返回可以插入的位置,或者查找到x的位置}int k = find(x);//返回一个可以插入的或者查找到的位置//插入if(h[k] == null) h[k] = x;//当前位置为空可以插入//查询if(h[k] != null) return found//当前位置不空必为xelse return not found //当前位置为空,查找不到xmemset(h, 0x3f, sizeof h);
      • 拉链法
        • 冲突的元素存入当前位置的链表中,因此同一个下标就可以存下不同的元素解决冲突
        • 代码:
          const int N = 1e5 + 3; //质数int h[N], e[N], ne[N], idx = 1;//链表节点从1开始,0代表空节点//添加void insert(int x){int k = (x % N + N) % N;//x可能为负数,结果相当于|x| % Ne[idx] = x;ne[idx] = h[k];h[k] = idx;idx ++ ; }//查询void find(int x){int k = (x % N + N) % N;for(int i = h[k]; i; i = ne[i])if(e[i] == x) return true;else return false;}
    • 字符串哈希方式
      • 字符串前缀哈希法
      • 将字符串的每个字符映射为某个数(asic码),该数不能为0,并且将该数看作p进制下的一位,求出它的十进制的值,该值就代表字符串的映射值,然后将该值对q取模,成为字符串的哈希值
      • 一般取p = 131 或者 13331, 取q = 2^64, 可以大概率减少冲突,不考虑冲突
      • 用unsigned long long 存储每个字符串的映射值,自然溢出相当于对q取模
      • 求出某个字符串的前缀哈希值,则该字符串的任一子串的哈希值可以做差求出(类似前缀和)
      • 代码:
        typedef unsigned long long ULL;const int N = 1e5 + 10;const int P = 131; //P进制char str[N];ULL h[N], p[N];//h存储字符串前缀哈希值,p[i]存储P进制下的P^i的值//取字串的哈希值ULL gets(int l, int r){return h[r] - h[l - 1] * p[r - l + 1];}//递推预处理p^i, 字符串前缀哈希值p[0] = 1;for(int i = 1; i <= n; ++ i){p[i] = p[i - 1] * P;h[i] = h[i - 1] * P + str[i]; //求前i个字符组成的字符串的哈希值(字符串前缀哈希值)}