作用

• 把一个庞大的空间映射到小的空间，小的空间一般是0~N（N一般取10^5）
• 一般哈希操作只有添加和查找
  • 如果非要实现删除，一般是重开一个数组作为标记，标记某个数被删除了
• 通过一个哈希函数$h(x) \in (0,10^5)$
• 哈希函数写法
  • x mod y
    • y取比映射范围大的第一个质数
      • 100000 —> 100003
  • 冲突处理（两个不一样的数映射到同一个数）
    • 开放寻址法
    • 拉链法

存储

两大类：开放寻址法、拉链法

开放寻址法

• 思想
  • 只开了一个一维数组，长度一般是最大长度的2~3倍，且为质数
  • 如果求出哈希值有人，就求出下一个位置（k++），知道没有人
• 代码实现

N = 200003
null = 0x3f3f3f3f
h = [0x3f3f3f3f] * N
def find(x): # 返回的是哈希值，如果x已存在，则返回存在的位置，如果x不存在，则返回应该插入的位置
    k = x % N
    while h[k] != null and h[k] != x:
        k += 1
        if k == N:
            k = 0
    return k

拉链法

• 思想

  • 每一个位当作一个槽

  • 如果几个数是冲突的，那么就会在该位置同时存几个数

    

• 代码实现

N =1000003
h = [-1] * N # 槽清空，空指针用-1表示
e= [0] * N
ne = [0] * N
idx = 0
def insert(x):
    k = x % N # k为哈希值
#头插入节点
    e[idx] = x
    ne[idx] = h[k]
    h[k] = idx
    idx += 1

def find(x):
    k = (x % N + N) % N
    i = h[k]
    while i != -1:
        if e[i] == x:
            return True
        i = ne[i]
    return False

• 如果是c++，k = (x % N + N) % N 。+N%N是因为如果x为负数得到的余数是负数，因此+N%N可以保证余数是正数

字符串前缀哈希法

1. 思想