Swift中如何对大数进行模运算？（滚动哈希场景）

在滚动哈希场景下，无需生成并处理超大数，直接利用模运算的分配律分步计算，就能避免Double精度丢失、Decimal无模运算支持、Int64范围不足的问题，全程使用Swift原生类型实现。

核心原理 #

模运算满足以下性质，可将超大数运算拆解为小范围分步运算：

• ((a + b) \mod m = [(a \mod m) + (b \mod m)] \mod m)
• ((a - b) \mod m = [(a \mod m) - (b \mod m) + m] \mod m)（加m确保结果非负）
• ((a \times b) \mod m = [(a \mod m) \times (b \mod m)] \mod m)

基于这些性质，我们可以在每一步哈希更新时就对结果取模，让所有中间值始终保持在mod（如(10^9+7)）范围内，完全不需要存储超出Int/Int64范围的大数。

原生实现示例 #

以固定窗口的滚动哈希为例：

let mod = 1_000_000_007
let base = 256 // 根据字符集选择，比如小写字母用26
let windowSize = 5
let text = "abcdefghij"

// 预计算 base^windowSize mod mod，避免重复计算
var basePower = 1
for _ in 0..<windowSize {
    basePower = (basePower * base) % mod
}

// 计算初始窗口的哈希值
var currentHash = 0
let initialWindow = text.prefix(windowSize)
for char in initialWindow {
    guard let asciiValue = char.asciiValue else { continue }
    let charValue = Int(asciiValue)
    currentHash = (currentHash * base + charValue) % mod
}
print("初始窗口哈希：\(currentHash)")

// 滚动更新哈希
for i in windowSize..<text.count {
    let oldCharIndex = text.index(text.startIndex, offsetBy: i - windowSize)
    let newCharIndex = text.index(text.startIndex, offsetBy: i)
    guard let oldAscii = text[oldCharIndex].asciiValue,
          let newAscii = text[newCharIndex].asciiValue else { continue }
    
    let oldCharValue = Int(oldAscii)
    let newCharValue = Int(newAscii)
    
    // 分步计算并取模，处理减法可能产生的负数
    currentHash = (currentHash * base - oldCharValue * basePower + newCharValue) % mod
    if currentHash < 0 {
        currentHash += mod
    }
    print("滚动后哈希：\(currentHash)")
}

优势说明 #

• 全程使用Swift原生Int类型（64位系统下等价于Int64），无需任何第三方库或自定义扩展
• 中间结果始终控制在mod范围内，不会出现溢出或精度丢失
• 计算效率高于先生成大数再取模的方式，减少内存占用

内容的提问来源于stack exchange，提问作者Dracula