只考虑id，符合Hashable的实现方式正确吗？

Question

我遇到的很多在线示例，当它们尝试符合Hashable时，仅考虑了id。例如https://www.raywenderlich.com/8241072-ios-tutorial-collection-view-and-diffable-data-source，https://medium.com/@JoyceMatos/hashable-protocols-in-swift-baf0cabeaebd，...

/// Copyright (c) 2020 Razeware LLC
/// 
/// Permission is hereby granted, free of charge, to any person obtaining a copy
/// of this software and associated documentation files (the "Software"), to deal
/// in the Software without restriction, including without limitation the rights
/// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
/// copies of the Software, and to permit persons to whom the Software is
/// furnished to do so, subject to the following conditions:
/// 
/// The above copyright notice and this permission notice shall be included in
/// all copies or substantial portions of the Software.
/// 
/// Notwithstanding the foregoing, you may not use, copy, modify, merge, publish,
/// distribute, sublicense, create a derivative work, and/or sell copies of the
/// Software in any work that is designed, intended, or marketed for pedagogical or
/// instructional purposes related to programming, coding, application development,
/// or information technology.  Permission for such use, copying, modification,
/// merger, publication, distribution, sublicensing, creation of derivative works,
/// or sale is expressly withheld.
/// 
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
/// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
/// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
/// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
/// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
/// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
/// THE SOFTWARE.

import UIKit

class Video: Hashable {
  var id = UUID()
  var title: String
  var thumbnail: UIImage?
  var lessonCount: Int
  var link: URL?
  
  init(title: String, thumbnail: UIImage? = nil, lessonCount: Int, link: URL?) {
    self.title = title
    self.thumbnail = thumbnail
    self.lessonCount = lessonCount
    self.link = link
  }
  // 1
  func hash(into hasher: inout Hasher) {
    // 2
    hasher.combine(id)
  }
  // 3
  static func == (lhs: Video, rhs: Video) -> Bool {
    lhs.id == rhs.id
  }
}

---

我在想，是否有一种正确的方法来符合Hashable协议？我认为我们应该考虑所有类成员变量吧？

例如，仅使用id在func hash/func ==中，将导致以下不良行为。

我们会遇到两个内容不同的对象，但比较这两个对象时func ==将返回true。

struct Dog: Hashable {
    let id = UUID()
    var name: String
    var age: Int
    
    init(name: String, age: Int) {
        self.name = name
        self.age = age
    }

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

    static func == (lhs: Dog, rhs: Dog) -> Bool {
        lhs.id == rhs.id
    }
}


var dog0 = Dog(name: "dog", age: 1)
var dog1 = dog0

/*
 dog0 is -5743610764084706839, dog, 1
 dog1 is -5743610764084706839, dog, 1
 compare dog0 with dog1 is true
 */
print("dog0 is \(dog0.hashValue), \(dog0.name), \(dog0.age)")
print("dog1 is \(dog1.hashValue), \(dog1.name), \(dog1.age)")
print("compare dog0 with dog1 is \(dog0 == dog1)")


dog1.name = "another name"
dog1.age = 9

// Same id, but different content!

/*
 dog0 is -5743610764084706839, dog, 1
 dog1 is -5743610764084706839, another name, 9
 compare dog0 with dog1 is true
 */
print("dog0 is \(dog0.hashValue), \(dog0.name), \(dog0.age)")
print("dog1 is \(dog1.hashValue), \(dog1.name), \(dog1.age)")
print("compare dog0 with dog1 is \(dog0 == dog1)")

我想知道，仅考虑 id 是否符合符合 Hashable 的要求？

---

p/s

我尝试从其他语言（例如Java）中了解有关哈希码生成的一般建议。在他们流行的 Effective Java 书中写下了以下内容。

不要因为性能而诱惑自己从哈希码计算中排除重要字段。虽然生成的哈希函数可能运行得更快，但其质量差劲可能会降低哈希表的性能，甚至使其变得无法使用。特别是，哈希函数可能面临大量只在你选择忽略的区域中有所不同的实例集合。如果发生这种情况，则哈希函数将所有这些实例映射到少量哈希码，并且应该以线性时间运行的程序将代替以二次时间运行。这不仅仅是一个理论问题。在 Java 2 之前，String 哈希函数最多使用字符串中间均匀分布的十六个字符，从第一个字符开始。对于包含大量层次结构名称（例如 URL）的集合，此函数完全显示了早期描述的病态行为。

- Cheok Yan Cheng

---

这要看情况。从可区分数据源的角度来看，如果内容是可变的，则在hash(into:)方法中将所有相关结构成员组合起来。 - vadian

Answer 1

TL;DR：这个哈希函数是不必要的，但合法且可以说是理想的。等于号 == 是不正确的，尽管在教程中很常见，因为它违反了可替换性，而 Equatable 需要可替换性，正如你所建议的一样。

然而，正如 Matt 注意到的，可区分数据源可能仍需要这个哈希函数。这并不好，但可能是必要的。（务必阅读下面所有的 matt 评论。他们提供了许多重要的背景信息。具体关于可区分数据源，请参见他的答案；我对可区分数据源并不特别熟悉。）

---

我建议查阅文档，其中有详细说明。

首先，Hashable:

哈希一个值意味着将其基本组件输入哈希函数中，由哈希器类型表示。基本组件是对类型实现Equatable的贡献。两个相等的实例必须以相同的顺序在hash(into:)中向哈希器提供相同的值。

最重要的是Hashable与Equatable一致。两个不相等的事物绝不能相等，但具有不同的哈希值。

反之则不成立。两个不相等的事物具有相同的哈希值是完全有效的。事实上，这是哈希的基本原理之一，称为pigeonhole principle。通过避免不必要的相等性检查，良好的哈希可以提高性能。但以下hash(into:)函数始终有效：

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

这意味着每个值都有相同的哈希值，因此系统将始终调用==。 这对性能不利（在服务器应用程序中，这可能会导致一种称为哈希洪泛的拒绝服务攻击）。 但是它是合法的。

如果这是合法的，那么只对id进行哈希处理也是合法的。

但是...

这就引出了Equatable及其文档，以及最重要的段落（已加重强调）：

平等意味着可替换性 - 任何比较相等的两个实例都可以在依赖于其值的任何代码中互换使用。 为了保持可替换性，==运算符应考虑到Equatable类型的所有可见方面。 不鼓励公开Equatable类型的非值方面，除了类标识之外，任何公开的非值方面都应在文档中明确指出。

只有当两个值可以在任何环境下相互替代，并且不会影响程序的正确性时，才应将其视为相等。显然，在您的示例中，这并不成立。实际上，对于具有可变公共属性的类型（尽管许多教程都搞错了），永远不会成立。因此，您的“==”是不正确的。但是，您的哈希函数是好的，甚至可以说是理想的。其目标是快速检查非平等，并最小化冲突。如果ID相同，则仍然必须检查其他值，但如果它们不同，则知道它们不会相等。

如果你的Dog类型是不可变的（name和age是let而不是var），那么这种实现==的方式可能是可以接受的。手动设置id是不可能的，因此不可能获得具有相同id但不同值的两个值。但我不会这样做，除非你能展示出显著的性能提升。它将正确性挂在了太微妙的要求上。例如，如果一个扩展添加了一个允许直接设置id的init，那么你的==就无效了。在我看来，这太脆弱了。

私有可变状态怎么样？只要这仅仅是为了性能目的（记忆化/缓存），那么将其留在==（和哈希）之外就可以了。但是，如果这个内部状态可以影响到外部可见的行为，那么它需要成为==的一部分。

好消息是，大多数情况下你不需要担心。Swift的自动实现会在开箱即用时正确地处理此问题，并比较所有属性。因此，在您的Dog示例中，最好的解决方案是只需删除方法（我相信您已经意识到这一点；只是为了让读者跟着理解）。尽可能地，我强烈建议使用默认的Hashable符合协议并避免编写自己的。

但在必须实现自己的情况下，规则很简单：

• 两个相等的值必须在所有情况下完全可替换，而不影响正确性（尽管替换可能会影响性能）
• 两个相等的值必须始终具有相同的哈希值

指南也相当简单：哈希应该快速，同时最小化冲突。

---

我曾经看到这些错误实现“==”的唯一论据是为了让Set正常工作。在我看来，这是对Set和Equatable的误用，并且不能保证按预期方式工作（如果您插入具有相同标识符但不同属性的重复值，则未定义将哪个值放入集合中）。您不应该扭曲Equatable想使用特定的数据结构。您应该使用与您的含义匹配的数据结构。

在常见情况下，正确的工具是字典，如[ID: Value]。它表达了您真正意思：ID和该ID的单个值之间的映射，而不是无序的唯一值的包。

使用字典而不是Set可能会有一些内存成本（因为您必须复制ID）。但是，在证明存在问题需要解决之后，您只应尝试解决此问题。

---

此外，请查看下面的Matt评论。我没有花太多时间使用新的可差异数据源。我记得当我第一次看到它们时，我担心它们可能会错误地使用Equatable。如果是这样，那么您可能不得不误用Equatable来使用它们，这就解释了一些这样做的教程。这并不意味着这是良好的Swift，但可能是Apple框架所要求的。

---

随着我对苹果公司代码的研究越来越深入（请参见Matt的答案），我注意到它们都遵循我上面讨论的规则：它们是不可变的，你不能在初始化时设置UUID。这种构造方式使得两个值具有相同的ID但其他值不同变得不可能，因此检查ID总是足够的。但是如果你使值可变，或者允许ID不是let id = UUID()，那么这种构造方式就变得危险起来了。

- Rob Napier

---

嗯，说实话，OP指向的第一个教程中几乎所有的东西都是错误的，你可能会晕倒。 - matt

然而，正是苹果公司宣传了这种做法。请查看 https://developer.apple.com/videos/play/wwdc2019/220/?time=832（时间很重要，所以您在正确的位置），并尽可能地查看代码。您会发现苹果公司正在 完全 做着您说不要做的事情。他们已经定义了 hash(into:) 和 == 仅依赖于 UUID 标识符。请记住，这是原始示例，公众看到如何创建可差异化数据源的第一个示例。因此，人们都在按照苹果公司的指示去做。 - matt

是的，这一直是我对可区分数据源的担忧。它们似乎没有遵循Swift标准库的明确要求。自从在WWDC期间看到它们以来，我就没有再多想过它们，所以我不知道是否有一个好的模式来解决这个问题，或者苹果是否只是让我们走了一条错误的路。我在ObjC中经常看到这种错误，人们一直逃脱着，直到他们突然遇到奇怪的集合相关的错误。 - Rob Napier

请参阅苹果的相同代码，网址为https://docs-assets.developer.apple.com/published/6840986f9a/ImplementingModernCollectionViews.zip。他们进行了四次相同的操作（在“static func ==”上搜索）。 - matt

抱歉一直在唠叨，但我想到您关于可变性的问题可能可以在我的示例中得到回答：https://dev59.com/A1IG5IYBdhLWcg3wkR1z#64164508 - matt

Answer 2

完全没有问题。 Hashable 只有一个要求：如果 a == b，则 a.hashValue == b.hashValue 也必须为真。这里已经满足了，因此您的结构体将作为字典键或集合成员工作。

请注意，如果您的 hash(into:) 没有将任何数据（或仅将常量数据）组合到哈希器中，则也会满足此要求。这将使哈希表查找变慢，但它们仍将正常工作。

另一种选择是在您的 == 实现中比较所有字段，但仅在 hash(into:) 中使用其中的一部分进行哈希。这仍然遵循规则（反过来不允许）。 这可能是性能优化的一种选择，但也可能会降低性能。这取决于您正在哈希的数据分布情况。

- Sven

Answer 3

无论是否仅使用属性的子集来符合哈希要求，完全取决于您的需求。

如果对于某个对象，相等性确实只由单个变量（或变量的子集）定义，则使用该变量的子集进行哈希（和相等）是正确的。

然而，如果需要所有类型的属性才能确定两个实例是否相等，则应使用所有属性。

- Dávid Pásztor

Answer 4

拥有一个具有多个属性（包括UUID）的类型，其中对于Hashable和Equatable的一致性仅取决于UUID而不是任何其他属性，是可以的。苹果在他们自己的代码中使用了这种模式。从这里下载苹果的示例代码：

https://docs-assets.developer.apple.com/published/6840986f9a/ImplementingModernCollectionViews.zip

看一下 WiFiController.Network 结构体、MountainsController.Mountain 结构体、OutlineViewController.OutlineItem 类以及 InsertionSortArray.SortNode 结构体。它们都做同样的事情。因此，所有这些代码都是由苹果公司编写的。

---

struct Network: Hashable {
    let name: String
    let identifier = UUID()

    func hash(into hasher: inout Hasher) {
        hasher.combine(identifier)
    }
    static func == (lhs: Network, rhs: Network) -> Bool {
        return lhs.identifier == rhs.identifier
    }
}

---

struct Mountain: Hashable {
    let name: String
    let height: Int
    let identifier = UUID()
    func hash(into hasher: inout Hasher) {
        hasher.combine(identifier)
    }
    static func == (lhs: Mountain, rhs: Mountain) -> Bool {
        return lhs.identifier == rhs.identifier
    }
    func contains(_ filter: String?) -> Bool {
        guard let filterText = filter else { return true }
        if filterText.isEmpty { return true }
        let lowercasedFilter = filterText.lowercased()
        return name.lowercased().contains(lowercasedFilter)
    }
}

---

class OutlineItem: Hashable {
    let title: String
    let subitems: [OutlineItem]
    let outlineViewController: UIViewController.Type?

    init(title: String,
         viewController: UIViewController.Type? = nil,
         subitems: [OutlineItem] = []) {
        self.title = title
        self.subitems = subitems
        self.outlineViewController = viewController
    }
    func hash(into hasher: inout Hasher) {
        hasher.combine(identifier)
    }
    static func == (lhs: OutlineItem, rhs: OutlineItem) -> Bool {
        return lhs.identifier == rhs.identifier
    }
    private let identifier = UUID()
}

---

struct SortNode: Hashable {
    let value: Int
    let color: UIColor

    init(value: Int, maxValue: Int) {
        self.value = value
        let hue = CGFloat(value) / CGFloat(maxValue)
        self.color = UIColor(hue: hue, saturation: 1.0, brightness: 1.0, alpha: 1.0)
    }
    private let identifier = UUID()
    func hash(into hasher: inout Hasher) {
        hasher.combine(identifier)
    }
    static func == (lhs: SortNode, rhs: SortNode) -> Bool {
        return lhs.identifier == rhs.identifier
    }
}

- matt

Answer 5

你的怀疑是正确的。关于是否“正确”（正如你所说）的问题取决于领域。已经对哈希和相等性的技术细节给出了很好的解释。

由于你的问题多次涉及到DiffableDataSource，因此在设计领域逻辑以满足UI框架的需求时，应非常谨慎。这样做违反了依赖反转和开闭原则。

创建一个本地数据结构作为数据源的项目标识符，并仅复制你有意决定触发重新加载的属性。

typealias DataSource = UICollectionViewDiffableDataSource<Int, DogItem>

struct DogItem: Hashable {
    var name: String // the cell will reload whenever the name changes
}

对比

struct DogItem: Hashable {
    var id: Dog.ID // the cell will never change until explicitly told
}

正如所提到的，一个常见的解决方案是使用将ID映射到值的字典： var items = [UUID:Item]() 然而，这可能会导致您映射错误的值：

var item1 = Item(id: UUID())
var item2 = Item(id: UUID())
items[item1.id] = item2

相反地，创建一个可重复使用的哈希包装数据结构来明确使用标识符。

struct IDMap<T: Identifiable & Hashable> {

    private var _items = [T.ID : T]()

    init() { }

    subscript(index: T.ID) -> T? {
        get { return _items[index] }
    }
    
    mutating func insert(_ item: T) {
        _items[item.id] = item
    }
    
    mutating func remove(_ item: T) {
        _items.removeValue(forKey: item.id)
    }
    
    var items: Set<T> {
        return Set(_items.values)
    }


}

- MH175

Answer 6

没错，你的代码对可哈希对象有一个要求，它只比较 dog.id == dog1.id 当你使用 dog == dog1 时。

如果你想检查结构体的所有字段，那么在 == 方法中比较那些字段。

static func == (lhs: Dog, rhs: Dog) -> Bool {
    lhs.id == rhs.id && lhs.name == rhs.name && lhs.age == rhs.age
}

- Dhawal