在Swift中实现哈希表？

Question

在Swift中实现哈希表？

6

我正在尝试在Swift中实现HashTable。基于我的理解，哈希值被用作要在数组中使用的索引。问题是，例如哈希值非常大。

"1" => 4,799,450,059,485,597,623
"2" => 4,799,450,059,485,597,624
"3" => 4,799,450,059,485,597,629

这些哈希值生成数组索引的正确方式是什么？

class HashTable <K: Hashable, V> {

    private var values : [V?]

    init(size: Int) {
        values = [V?](count: size, repeatedValue: nil)
    }

    func push(key: K, value: V?) {
        values[key.hashValue] = value
    }

    subscript (key: K) -> V? {
        get {
            return values[key.hashValue]
        }
        set {
            push(key, value: newValue)
        }
    }
}

- aryaxt

2

Swift字典是哈希表，那么重新实现为数组的优势在哪里呢？（特别是考虑到Swift没有稀疏数组的事实...） - matt

1

@matt 我知道，自己实现的好处在于学习它们的工作原理。我的代码难道不是创建了一个稀疏数组吗？[V?](count: size, repeatedValue: nil) 是一个特定大小且默认值为 nil 的数组。 - aryaxt

这篇文章似乎解决了这个问题 http://waynewbishop.com/swift/hashtables - aryaxt

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- aryaxt · Accepted Answer

我最终在数组中存储了LinkedNodes而不是值。

hashIndex = hashValue % values.count

当搜索或删除链表中超过一个节点时，我直接比较哈希值而不是哈希索引。（处理冲突）

想知道是否有更好的解决方案。