image.png

mod一般取一個素數(shù)

解決沖突的方法：

1. 線性探查法

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

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. 鏈地址法

如果沖突就掛在這個鏈節(jié)點上。

一般用STL的map就行了。

字符串hash怎么辦？

a[0]-'A' 記作ascii碼