哈希表
- 存储结构
- 开放寻址法
- 拉链法
- 字符串哈希方式
- 时间复杂度 O(1)
- mod 取模尽可能取质数并且远离2^n (第一个大于值域的质数)
- 离散化是特殊的哈希方式,需要保序
- h[k]里面存的是x的下标(0-N)
算法1
拉链法
开一个长度为hash值域的一维数组。数组值域作为链表的head。h[k]:储存链表的第一个下标
- step1 k = x % mod
- step2 头插法,将x查到单链表h[k]的头部
e[idx] = k
ne[idx] = h[k]
h[k] = idx
idx += 1
时间复杂度
O(1)
Python 代码
# Find the first prime number > 10^5 --> 100003
# for i in range(10**5, 10**5*2):
# flag = True
# for j in range(2, int(i ** 0.5)):
# if i%j == 0:
# flag = False
# break
# if flag == True:
# print(i)
# break
def insert(x):
# 头插法,将x对应的下标idx插到单链表h[k]的头部
global idx, mod
k = x%mod
e[idx] = x
ne[idx] = h[k]
h[k] = idx
idx += 1
def find(x):
global mod
k = x%mod
i = h[k]
while i != -1:
if e[i] == x:
return True
i = ne[i]
return False
if __name__ == '__main__':
n = int(input().strip())
# 初始化邻接表
N = 10**5 + 10 # 表示链表最多的节点数
h = [-1] * N
e = [-1] * N
ne = [-1] * N
idx = 0 # 下标
mod = 10**5 + 3
while n:
n -= 1
op,x = input().split()
x = int(x)
if op == 'I':
insert(x)
else:
if find(x): print('Yes')
else: print('No')
算法2
开放寻址法
- Pro: 只需要开一个一维数组中
- 数组长度:数据范围的2~3倍-> 降低冲突的概率
- h[k]里面存的是x本身(10^-9 ~ 10^9)
添加
- k = x%mod
- 从第k个槽开始,直到找到空的位置插入
查找
- k = x%mod
- 从第k个槽开始查找,直到碰到空的槽都没有找到x-> 则x不存在
时间复杂度
O(1)
Python 代码
# 找到放x的位置k
def find(x):
k = x%mod
while h[k] != None and h[k] != x:
k += 1
# 如果k走到了末尾,从头再开始走
if k == N:
k = 0
# k可能的值: 1.x要放的位置 2. x在数组中的位置
return k
if __name__ == "__main__":
N = 10**5 + 10
mod = 10**5 + 3
h = [None] * N
n = int(input())
while n:
n -= 1
op, x = input().split()
x = int(x)
k = find(x)
if op == 'I':
h[k] = x
else:
if h[k] == x: print('Yes')
else: print('No')