Swift：我的散列 table 适用于幻数，但不适用于动态数

Question

我正在学习如何根据自己的知识创建自己的哈希 table（以及面试准备，让我们面对现实吧）。

我在 swift 工作，我运行陷入了一个我似乎无法很好解决的问题。

我们的目标是创建一个简单但有效的散列，在调整大小后仍然 returns 在输入键作为下标时的适当值。如果我在散列 table 中使用相同的值，无论其大小如何，它都会起作用。

例如，如果我将 %（模）除数设置为 3，那么一切都很好。散列 table 按预期工作。

但是……

如果我将 %（模）除数设置为 'buckets'.count Int 值，则在调整大小时，我的键不再映射到任何相关内容，我的 return 值为 'nil' 这是正确的，因为密钥映射到新调整大小的 'buckets' 中不存在的原始哈希值。

（我想我说的很对，如有不妥请见谅）

这是我对哈希函数的尝试：

// function to find a safe prime number -> a nice implementation i found here on stack overflow
func isPrime(_ n: Int) -> Bool {
    guard n >= 2     else { return false }
    guard n != 2     else { return true  }
    guard n % 2 != 0 else { return false }
    return !stride(from: 3, through: Int(sqrt(Double(n))), by: 2).contains { n % [=12=] == 0 }
}

private func index(forKey key: Key) -> Int {

    // set primeNumber to a value that is the largest Int value in range of buckets.count...0

    var primeNumber: Int = 3

    for n in 0...buckets.count {

        let validPrime = isPrime(n)

        if validPrime {

            primeNumber = n
        }
    }

    return abs(key.hashValue % primeNumber)
}

这是我对调整大小功能的尝试：

mutating func resize(newCapacity: Int) -> [Bucket] {

    var temporaryBuckets: [Bucket] = []

    for bucket in buckets {

        temporaryBuckets.append(bucket)
    }

    self.capacity = newCapacity

    assert(capacity > 0)

    // need to find another way to re-insert the elements

    buckets = Array<Bucket>(repeatElement([], count: capacity))

    var index = 0
    for bucket in temporaryBuckets {

        buckets[index] = bucket

        index += 1
    }

    return buckets
}

非常感谢任何帮助。如果有更有效的方法又不会太疯狂，那我洗耳恭听！

如果好奇，我正在尝试完成 Ray Wenderlich 的 Swift 算法俱乐部条目中的散列 table 教程：

Swift 算法俱乐部：Kelvin Lau 的哈希表。 https://www.raywenderlich.com/206-swift-algorithm-club-hash-tables

提前致谢！

Answer 1

您需要为新哈希重新计算索引table。现在，您正在将存储桶分配给索引 0、1、2 等等。相反，您应该为每个元素再次调用 index(forKey:) 并将其插入到新索引处。请注意，您现在不能使用相同的 Bucket 对象。你能想到这是为什么吗？

Swift：我的散列 table 适用于幻数，但不适用于动态数

Swift: my hash table works with a magic number, but not with a dynamic number

arrays

hash

hashtable

hashmap

swift