哈希表

哈希表

• 作用：将庞大的空间，映射到小的空间，集中数据，一般用取模，取模的数尽量取质数，最大程度减小冲突
• 操作：一 般是添加和查找元素，删除元素通常有一个标记数组，对元素标记为已删除
• 离散化相似，离散化是特殊的哈希方式，离散化处理的数据是单调的，相对位置不变
• 映射会出现冲突，如将两个不同的数映射成同一个数

• 存储结构：

  • 解决了冲突

  • 开放寻址法

    • 仅仅一个数组，数组长度通常为最大范围的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){//当前位置有元素且不为x
      		k ++ ;//后移
      		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//当前位置不空必为x
      else return not found //当前位置为空，查找不到x
      memset(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| % N
      	e[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个字符组成的字符串的哈希值（字符串前缀哈希值）
    }