Swift：我的哈希表可以用魔数，但不能用动态数。

Question

我正在学习如何为自己的知识（和面试准备，让我们面对它）创建自己的哈希表。

我在swift中工作，我遇到了一个我似乎不能很好解决的问题。

我们的目标是创建一个简单而有效的哈希值，当输入一个键作为下标时，该哈希值在调整大小后仍能返回适当的值。

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

但是...

但是......如果我把%(modulo)除数设置为'buckets'.count Int值，在调整大小后，我的键不再映射到任何相关的东西，我的返回值是'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 % $0 == 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 Algorithm Club作品中的哈希表教程。

Swift算法俱乐部：哈希表 作者：Kelvin Lau.https:/www.raywenderlich.com206-swift-algorithm-club-hash-tables

先谢谢你!

Answer 1

你需要再次计算新哈希表的索引。现在你正在将桶分配到索引0，1，2，以此类推。相反，你应该调用 index(forKey:) 并将其插入到新的索引中。请注意，你不能使用相同的 Bucket 对象了。你能想到这其中的原因吗？