algorithm - 快速实现 FNV 哈希

Question

我正在尝试快速实现 FNV 散列的一个版本。这是在 Objective-C 中:

+ (uint32_t)hash:(uint8_t *)a length:(uint32_t)length
{
    uint8_t *p;
    uint32_t x;

    p = a;
    x = *p << 7;
    for (int i=0; i<length; i++) {
        x = (1000003 * x) ^ *p++;
        x ^= length;
    }
    if (x == -1) {
        x = -2;
    }
    return x;
}

这是我将它移植到 swift 的尝试:

func hashFNV(data: UInt8[]) -> UInt32 {
    var x = data[0] << 7

    for byte in data {
        x *= 1000003
        x ^= byte
        x ^= data.count
    }
    if x == -1 {
        x = -2
    }
    return x
}

它编译但在运行时导致错误:

EXC_BAD_INSTRUCTION (code=EXC_I386_INVOP,subcode=0x0)

当我在 Playground 上尝试时出现同样的错误:

Playground execution failed: error: Execution was interrupted, reason: EXC_BAD_INSTRUCTION (code=EXC_I386_INVOP, subcode=0x0).
The process has been left at the point where it was interrupted, use "thread return -x" to return to the state before expression evaluation.
* thread #1: tid = 0x619fa, 0x000000010d119aad, queue = 'com.apple.main-thread', stop reason = EXC_BAD_INSTRUCTION (code=EXC_I386_INVOP, subcode=0x0)
  * frame #0: 0x000000010d119aad
    frame #1: 0x0000000100204880 libswift_stdlib_core.dylib`value witness table for Swift.Int + 160

我以为可能与溢出有关，但下面的代码也失败并出现同样的错误:

func hashFNV(data: UInt8[]) -> UInt32 {
    var x = UInt32(data[0]) << 7

    for byte in data {
        x = 1000003 &* x
        x ^= byte
        x ^= data.count
    }
    if x == -1 {
        x = -2
    }
    return x
}

编辑:

实际上，我试图将 -2 赋给 x 的事实不应该导致编译错误吗？我认为 swift 不会隐式地从 Int (-2) 转换为 UInt32 (x)。

与 x ^= byte 行相同。 byte 应该是 UInt8，x 是 UInt32。

编辑 2:

这是一个编译错误(见下面的评论)。

修复了编译错误，运行时仍然失败:

func hashFNV(data: UInt8[]) -> UInt32 {
    var x = Int(data[0]) << 7

    for byte in data {
        x = 1000003 &* x
        x ^= Int(byte)
        x ^= data.count
    }
    if x == -1 {
        x = -2
    }
    return UInt32(x)
}

Answer 1

如果您仍在寻找实现，这是我的。它的构建非常类似于标准库中的常规默认 Hasher。

struct HasherFNV1a {

    private var hash: UInt = 14_695_981_039_346_656_037
    private let prime: UInt = 1_099_511_628_211

    mutating func combine<S: Sequence>(_ sequence: S) where S.Element == UInt8 {
        for byte in sequence {
            hash ^= UInt(byte)
            hash = hash &* prime
        }
    }

    func finalize() -> Int {
        Int(truncatingIfNeeded: hash)
    }
}

extension HasherFNV1a {

    mutating func combine(_ string: String) {
        combine(string.utf8)
    }

    mutating func combine(_ bool: Bool) {
        combine(CollectionOfOne(bool ? 1 : 0))
    }
}

请记住，这是 FNV1a，如果您确实需要 FNV1，您只需切换循环中的 2 行即可。