散列函数与查询

image.png

mod一般取一个素数

---

解决冲突的方法：

1. 线性探查法

hash=H(key)+i
如果找不到空位就再循环下去。

2. 平方探查法

hash=H(key)+i*i

for(i=0;i<table_length;i++){
  hash=(H(key)+i*i)%prime;
}

3. 二次探测再散列

H0,H0+i*i,H0-i*i......

image.png

4. 链地址法

如果冲突就挂在这个链节点上。

---

一般用STL的map就行了。

---

字符串hash怎么办？

a[0]-'A' 记作ascii码