arrays - Swift：我的哈希表适用于幻数，但不适用于动态数字

问题描述

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

我正在快速工作，我遇到了一个我似乎无法特别好解决的挂断。

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

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

但...

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

（我想我说得对。如果它倒退了，请原谅我。）

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

// 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.com/206-swift-algorithm-club-hash-tables

提前致谢！

标签： arraysswifthashhashmaphashtable

arrays - Swift：我的哈希表适用于幻数，但不适用于动态数字

问题描述

解决方案

推荐阅读