快速设置类型的哈希值是什么? [英] What does Hash Values for Set Types in swift?

问题描述

当我阅读快速文档时，我不明白那是什么意思吗?. 类型必须是可哈希的才能存储在集合中，也就是说，该类型必须提供一种为其自身计算哈希值的方法.哈希值是一个Int值，对于所有相等比较的对象都是相同的，因此，如果a == b，则它遵循a.hashValue == b.hashValue.

when i read swift documentation i can not understand what that mean?. A type must be hashable in order to be stored in a set—that is, the type must provide a way to compute a hash value for itself. A hash value is an Int value that is the same for all objects that compare equally, such that if a == b, it follows that a.hashValue == b.hashValue.

推荐答案

Set是为提高性能而设计的. Set上的contains(_:)方法的复杂度为O(1)，这意味着无论集合的大小如何，都需要花费恒定的时间来执行. Array上的contains(_:)为O(n)，这意味着确定数组是否包含元素的时间会随着数组大小的增加而增加.

Sets are designed for performance. The contains(_:) method on Set is O(1) complexity meaning it takes a constant amount of time to perform no matter the size of the set. contains(_:) on an Array is O(n) meaning the time to determine if the array contains an element increases as the size of the array increases.

Set如何做到这一点?它对Set的项目使用hashValue，并包含类似于内部字典的结构，该结构将hashValue映射到具有hashValue的项目列表.这使得测试复杂结构(例如String)的相等性非常快，因为Set首先测试两个值是否具有相同的hashValue.如果hashValue不同，则不需要检查struct本身的内容.

How does a Set do that? It uses a hashValue for the items of the Set and contains an internal dictionary like structure that maps the hashValue to the list of items with that hashValue. This makes testing equality of complex structures (like String) very quick because Set first tests if two values have the same hashValue. If the hashValues are different, it doesn't need to check the contents of the structs themselves.

要测试Set contains是否为值，仅需要在字典中查找hashValue，然后将该项与匹配的值进行比较.

To test if the Set contains a value, it is necessary to only look up the hashValue in the dictionary and then compare the item to the values that match.

因此，对于要包含在Set中的项目，重要的是提供一种散列函数，该散列函数应:

So, for items to be contained in a Set, it is important to provide a hashing function that:

1. 如果两个结构/对象相等，则相同. (绝对要求)
2. 计算范围广泛的hashValues，因此项目分布广泛，不需要回落到较慢的相等检查中. (为了获得良好的性能)

1. Is the same if two structs/objects are equal. (absolute requirement)
2. Computes a wide range of hashValues so that the items are widely distributed and don't require falling back to the slower check for equality. (for good performance)

---

以下是Hashable struct的示例，适合存储在Set中:

---

Here is an example of a Hashable struct that is appropriate for storage in a Set:

struct Option: Hashable, CustomStringConvertible {
    var title: String
    var key: String
    var value: Int
    var description: String { return "{title: \"\(title)\", key: \"\(key)\", value: \(value)}" }

    func hash(into hasher: inout Hasher) {
        hasher.combine(title)
        hasher.combine(key)
    }

    static func ==(lhs: Option, rhs: Option) -> Bool {
        return lhs.title == rhs.title && lhs.key == rhs.key
    }
}

注意::在此示例中，仅考虑title和key属性是否相等.即使两个结构具有不同的value属性，它们也可以相等. hash(into:)函数同样仅考虑title和key属性.

Note: In this example, only the title and key properties are considered for equality. Two structs can be equal even if they have different value properties. The hash(into:) function likewise only considers the title and key properties.

这篇关于快速设置类型的哈希值是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！