一南蓬、func hashStr(sep string) (uint32, uint32)
先分析下golang用得hash算法
32 bit FNV_prime = 2^24 + 2^8 + 0x93 = 16777619（詳見(jiàn)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])
后面一段, 計(jì)算出pow（后面Index函數(shù)使用）,如下公式
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函數(shù)函數(shù), 查找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 {
//查找字符串的長(zhǎng)度
n := len(sep)
switch {
//長(zhǎng)度 == 0留拾， return 0
case n == 0:
return 0
//長(zhǎng)度 == 1敌呈，調(diào)用另外一個(gè)函數(shù)
case n == 1:
return IndexByte(s, sep[0])
//長(zhǎng)度 == s字符串的長(zhǎng)度相等诬辈，比較兩個(gè)字符串是否相等
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
}
常規(guī)思路（sep是關(guān)鍵詞拳昌，s是源字符串）
- 對(duì)要查找的字符串sep進(jìn)行hash雨饺，此處hash值是uint32類型
- 在源字符串s中钳垮，從頭取len(sep)長(zhǎng)度，也進(jìn)行hash
- 比較兩次hash值是否一致额港，一致饺窿，返回index
例如在“abcdefgh”中查找“fg”的位置
- 對(duì)“fg” hash，得到hashsep
- for循環(huán)移斩，依次取2位（len("fg")）肚医，比如第一次取，“ab”向瓷， 第二次取“bc”肠套， 第三次取“cd”..., 進(jìn)行hash，得到hashsep1
- 比較hashsep和hashsep1是否相等
golang源碼中猖任，使用的算法如下
- 對(duì)要查找的字符串sep進(jìn)行hash你稚，得到hashsep， 此處hashsep值是uint32類型
- 在s頭部取len(sep)的字符串朱躺，進(jìn)行hash刁赖，直接與上步產(chǎn)生的hashsep比較，相等則已經(jīng)找到
- 根據(jù)上步的hashsep計(jì)算出下次需要的hashsep
例如：
在“abcdefgh”中查找“fg”的位置
- 對(duì)“fg” hash室琢，得到hashsep
hashsep, pow := hashStr(sep)
- 取出“ab”進(jìn)行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
}
- 根據(jù)“ab”的hash值盈滴，計(jì)算出“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
}
}
分析一下怎么根據(jù)“ab”的hash值涯肩，計(jì)算出“bc”的hash值
還以“abcdefg”中查找“ef”為例
- 計(jì)算hash["ab"] (表示“ab”的hash值)
-
計(jì)算hash["bc"]
- 從hash["ab"]計(jì)算出hash["bc"]
可以用多位字符串試一試轿钠，我這里只用兩位
對(duì)比一下剛才這段代碼
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)函數(shù)返回的pow就是用來(lái)計(jì)算下一個(gè)組合的hash值的h -= pow * uint32(s[i-n])
