一、func hashStr(sep string) (uint32, uint32)
先分析下golang用得hash算法
32 bit FNV_prime = 2^24 + 2^8 + 0x93 = 16777619（详见FNV hash算法）
// primeRK is the prime base used in Rabin-Karp algorithm.
const primeRK = 16777619
// hashStr returns the hash and the appropriate multiplicative
// factor for use in Rabin-Karp algorithm.
func hashStr(sep string) (uint32, uint32) {
hash := uint32(0)
for i := 0; i < len(sep); i++ {
//hash = 0 * 16777619 + sep[i]
hash = hash*primeRK + uint32(sep[i])
}
var pow, sq uint32 = 1, primeRK
for i := len(sep); i > 0; i >>= 1 {
if i&1 != 0 {
pow *= sq
}
sq *= sq
}
return hash, pow
}
核心算法是这一句(FNV Hash算法)
hash = hash*primeRK + uint32(sep[i])
后面一段, 计算出pow（后面Index函数使用）,如下公式
var pow, sq uint32 = 1, primeRK
for i := len(sep); i > 0; i >>= 1 {
if i&1 != 0 {
pow *= sq
}
sq *= sq
}
二、func Index(s, sep string) int
这是golang strings包中的Index函数函数, 查找sep字符串在s中的位置并返回（RK算法，Rabin-Karp算法）
// Index returns the index of the first instance of sep in s, or -1 if sep is not present in s.
func Index(s, sep string) int {
//查找字符串的长度
n := len(sep)
switch {
//长度 == 0， return 0
case n == 0:
return 0
//长度 == 1，调用另外一个函数
case n == 1:
return IndexByte(s, sep[0])
//长度 == s字符串的长度相等，比较两个字符串是否相等
case n == len(s):
if sep == s {
return 0
}
return -1
case n > len(s):
return -1
}
// Rabin-Karp search
hashsep, pow := hashStr(sep)
var h uint32
for i := 0; i < n; i++ {
h = h*primeRK + uint32(s[i])
}
if h == hashsep && s[:n] == sep {
return 0
}
for i := n; i < len(s); {
h *= primeRK
h += uint32(s[i])
h -= pow * uint32(s[i-n])
i++
if h == hashsep && s[i-n:i] == sep {
return i - n
}
}
return -1
}
常规思路（sep是关键词，s是源字符串）
- 对要查找的字符串sep进行hash，此处hash值是uint32类型
- 在源字符串s中，从头取len(sep)长度，也进行hash
- 比较两次hash值是否一致，一致，返回index
例如在“abcdefgh”中查找“fg”的位置
- 对“fg” hash，得到hashsep
- for循环，依次取2位（len("fg")），比如第一次取，“ab”， 第二次取“bc”， 第三次取“cd”..., 进行hash，得到hashsep1
- 比较hashsep和hashsep1是否相等
golang源码中，使用的算法如下
- 对要查找的字符串sep进行hash，得到hashsep， 此处hashsep值是uint32类型
- 在s头部取len(sep)的字符串，进行hash，直接与上步产生的hashsep比较，相等则已经找到
- 根据上步的hashsep计算出下次需要的hashsep
例如：
在“abcdefgh”中查找“fg”的位置
- 对“fg” hash，得到hashsep
hashsep, pow := hashStr(sep)
- 取出“ab”进行hash，得到hash值，与hashsep比较
var h uint32
for i := 0; i < n; i++ {
h = h*primeRK + uint32(s[i])
}
if h == hashsep && s[:n] == sep {
return 0
}
- 根据“ab”的hash值，计算出“bc”的hash值（这一步很巧妙）
for i := n; i < len(s); {
h *= primeRK
h += uint32(s[i])
h -= pow * uint32(s[i-n])
i++
if h == hashsep && s[i-n:i] == sep {
return i - n
}
}
分析一下怎么根据“ab”的hash值，计算出“bc”的hash值
还以“abcdefg”中查找“ef”为例
- 计算hash["ab"] (表示“ab”的hash值)
-
计算hash["bc"]
- 从hash["ab"]计算出hash["bc"]
可以用多位字符串试一试，我这里只用两位
对比一下刚才这段代码
for i := n; i < len(s); {
h *= primeRK
h += uint32(s[i])
h -= pow * uint32(s[i-n])
i++
if h == hashsep && s[i-n:i] == sep {
return i - n
}
}
func hashStr(sep string) (uint32, uint32)函数返回的pow就是用来计算下一个组合的hash值的h -= pow * uint32(s[i-n])
