字符串哈希 - 元素码农

发布时间: 2025-03-21 20:03

↑

# 字符串哈希

字符串哈希（String Hashing）是一种将字符串映射为整数的方法，通过巧妙的设计可以快速判断两个字符串是否相等，是处理字符串问题的重要算法。

## 基本概念

### 哈希函数

字符串哈希的核心是设计一个好的哈希函数，它需要满足：
- 计算速度快
- 冲突概率小
- 支持子串哈希值的快速计算

### 多项式哈希

最常用的字符串哈希方法是多项式哈希，基本思想是：
- 将字符串看作一个P进制数
- 选择一个大质数M作为模数
- 计算这个P进制数对M取模的结果

## 实现原理

### 基本实现

```go
// 字符串哈希结构
type StringHash struct {
    str    string   // 原始字符串
    hash   []int64  // 前缀哈希值
    power  []int64  // P的幂
    P      int64    // 进制数
    M      int64    // 模数
}

// 创建字符串哈希
func NewStringHash(s string) *StringHash {
    n := len(s)
    sh := &StringHash{
        str:   s,
        hash:  make([]int64, n+1),
        power: make([]int64, n+1),
        P:     131,        // 经验值，可以是131或13331
        M:     1e9 + 7,   // 大质数
    }
    sh.init()
    return sh
}

// 初始化哈希值和幂
func (sh *StringHash) init() {
    // 初始化P的幂
    sh.power[0] = 1
    for i := 1; i <= len(sh.str); i++ {
        sh.power[i] = (sh.power[i-1] * sh.P) % sh.M
    }
    
    // 计算前缀哈希值
    for i := 0; i < len(sh.str); i++ {
        sh.hash[i+1] = (sh.hash[i]*sh.P + int64(sh.str[i])) % sh.M
    }
}

// 获取子串哈希值
func (sh *StringHash) getSubstringHash(left, right int) int64 {
    return ((sh.hash[right+1] - sh.hash[left]*sh.power[right-left+1])%sh.M + sh.M) % sh.M
}
```

### 双哈希

为了进一步降低哈希冲突的概率，可以使用双哈希：

```go
// 双哈希结构
type DoubleHash struct {
    hash1 *StringHash
    hash2 *StringHash
}

// 创建双哈希
func NewDoubleHash(s string) *DoubleHash {
    dh := &DoubleHash{
        hash1: NewStringHash(s),
    }
    // 使用不同的P和M
    dh.hash2 = &StringHash{
        str:   s,
        hash:  make([]int64, len(s)+1),
        power: make([]int64, len(s)+1),
        P:     13331,
        M:     1e9 + 9,
    }
    dh.hash2.init()
    return dh
}

// 比较两个子串是否相等
func (dh *DoubleHash) compareSubstrings(s1Left, s1Right, s2Left, s2Right int) bool {
    hash1Equal := dh.hash1.getSubstringHash(s1Left, s1Right) == 
                 dh.hash1.getSubstringHash(s2Left, s2Right)
    hash2Equal := dh.hash2.getSubstringHash(s1Left, s1Right) == 
                 dh.hash2.getSubstringHash(s2Left, s2Right)
    return hash1Equal && hash2Equal
}
```

## 应用场景

### 字符串匹配

```go
// 查找模式串在文本中的所有出现位置
func FindPattern(text, pattern string) []int {
    result := make([]int, 0)
    n, m := len(text), len(pattern)
    if m > n {
        return result
    }
    
    // 创建文本和模式串的哈希
    textHash := NewStringHash(text)
    patternHash := NewStringHash(pattern)
    targetHash := patternHash.hash[m]
    
    // 滑动窗口查找
    for i := 0; i <= n-m; i++ {
        if textHash.getSubstringHash(i, i+m-1) == targetHash {
            result = append(result, i)
        }
    }
    return result
}
```

### 重复子串检测

```go
// 查找最长重复子串
func LongestRepeatedSubstring(s string) string {
    n := len(s)
    sh := NewStringHash(s)
    maxLen := 0
    start := 0
    
    // 二分查找最长长度
    left, right := 1, n
    for left <= right {
        mid := (left + right) / 2
        found := false
        
        // 检查是否存在长度为mid的重复子串
        seen := make(map[int64]int)
        for i := 0; i <= n-mid; i++ {
            hash := sh.getSubstringHash(i, i+mid-1)
            if pos, ok := seen[hash]; ok {
                // 找到重复子串
                found = true
                if mid > maxLen {
                    maxLen = mid
                    start = pos
                }
                break
            }
            seen[hash] = i
        }
        
        if found {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    if maxLen == 0 {
        return ""
    }
    return s[start:start+maxLen]
}
```

## 性能分析

### 时间复杂度

1. 预处理
   - 哈希值计算：O(n)
   - 幂值计算：O(n)

2. 查询操作
   - 子串哈希值获取：O(1)
   - 字符串匹配：O(n)
   - 重复子串检测：O(nlogn)

### 空间复杂度

- 基本实现：O(n)
- 双哈希：O(n)

### 哈希冲突

1. 冲突概率
   - 单哈希：约1/M
   - 双哈希：约1/(M1*M2)

2. 减少冲突的方法
   - 选择合适的P和M
   - 使用双哈希
   - 增大模数

## 实践建议

### 参数选择

1. 进制数P
   - 常用值：131, 13331
   - 要大于字符集大小
   - 最好是质数

2. 模数M
   - 常用值：1e9+7, 1e9+9
   - 要足够大
   - 最好是质数

### 优化技巧

1. 溢出处理
   - 使用unsigned long long
   - 自然溢出
   - 模数分解

2. 效率提升
   - 预计算幂值
   - 使用位运算
   - 避免取模运算

## 总结

1. 优点
   - 计算速度快
   - 空间占用小
   - 实现简单

2. 缺点
   - 存在哈希冲突
   - 需要预处理
   - 模数限制

3. 适用场景
   - 字符串匹配
   - 重复性检测
   - 子串比较