SE-0514: `Hashable` Conformance for `Dictionary.Keys`, `CollectionOfOne` and `EmptyCollection`

Introduction

This proposal adds Hashable conformance to three standard library collection types: Dictionary.Keys, CollectionOfOne and EmptyCollection.

Motivation

Dictionary.Keys

Dictionary.Keys is simply a view of the dictionary's keys, and every key in a dictionary conforms to Hashable. Hence, Dictionary.Keys should automatically and unconditionally conform to Hashable.

CollectionOfOne and EmptyCollection

CollectionOfOne and EmptyCollection are some of the more rarely used types and the addition of their Hashable conformance is more for completeness and consistency with other standard library collection types.

CollectionOfOne does not conform to Equatable so this proposal also adds that conformance.

Proposed solution

The standard library should add unconditional Hashable conformance to Dictionary.Keys and EmptyCollection, and conditional Equatable and Hashable conformances to CollectionOfOne.

Detailed design

Dictionary.Keys

Dictionary.Keys gains unconditional Hashable conformance. Since dictionary keys are always Hashable (as required by Dictionary's type constraints), the keys view is always hashable. The hash implementation uses a commutative hashing algorithm (XOR of individual element hashes) to ensure that two Dictionary.Keys collections hash to the same value if they contain the same elements regardless of iteration order.

extension Dictionary.Keys {
  @_alwaysEmitIntoClient
  public func hash(into hasher: inout Hasher) {
    var commutativeHash = 0
    for element in self {
      // Note that, similar to `Set`'s and `Dictionary`'s hashing algorithms, we use a copy of our own hasher here.
      // This makes hash values dependent on its state, eliminating static collision patterns.
      var elementHasher = hasher
      elementHasher.combine(element)
      commutativeHash ^= elementHasher._finalize()
    }
    hasher.combine(commutativeHash)
  }

  @_alwaysEmitIntoClient
  public var hashValue: Int { // Prevent compiler from synthesizing hashValue.
    var hasher = Hasher()
    self.hash(into: &hasher)
    return hasher.finalize()
  }
}

@available(SwiftStdlib 6.4, *)
extension Dictionary.Keys: Hashable {}

For example:

let batch1 = ["apple": 1, "banana": 2, "cherry": 3, "date": 4]
let batch2 = ["date": 10, "banana": 20, "apple": 30, "cherry": 40]
let batch3 = ["mango": 5, "orange": 6, "papaya": 7]

let uniqueBatches = Set([batch1.keys, batch2.keys, batch3.keys])

print(uniqueBatches)
// [Dictionary.Keys(["orange", "mango", "papaya"]), Dictionary.Keys(["banana", "apple", "date", "cherry"])]

CollectionOfOne

CollectionOfOne gains conditional Equatable conformance when Element conforms to Equatable, and Hashable when Element conforms to Hashable. The hash value is derived from the single element it contains.

extension CollectionOfOne where Element: Equatable {
  @_alwaysEmitIntoClient
  public static func ==(lhs: CollectionOfOne<Element>, rhs: CollectionOfOne<Element>) -> Bool {
    return lhs._element == rhs._element
  }
}

extension CollectionOfOne where Element: Hashable {
  @_alwaysEmitIntoClient
  public func hash(into hasher: inout Hasher) {
    hasher.combine(self._element)
  }

  @_alwaysEmitIntoClient
  public var hashValue: Int { // Prevent compiler from synthesizing hashValue.
    var hasher = Hasher()
    self.hash(into: &hasher)
    return hasher.finalize()
  }
}

@available(SwiftStdlib 6.4, *)
extension CollectionOfOne: Equatable where Element: Equatable {}

@available(SwiftStdlib 6.4, *)
extension CollectionOfOne: Hashable where Element: Hashable {}

EmptyCollection

EmptyCollection gains unconditional Hashable conformance. Since all empty collections are equal regardless of their element type, they all hash to the same value. The hash function simply combines the value 0, consistent with the hashing convension for empty sets, dictionaries and arrays.

extension EmptyCollection {
  @_alwaysEmitIntoClient
  public func hash(into hasher: inout Hasher) {
    hasher.combine(0)
  }

  @_alwaysEmitIntoClient
  public var hashValue: Int { // Prevent compiler from synthesizing hashValue.
    var hasher = Hasher()
    self.hash(into: &hasher)
    return hasher.finalize()
  }
}

@available(SwiftStdlib 6.4, *)
extension EmptyCollection: Hashable {}

Source compatibility

This is a purely additive change, but any code that provides its own redundant conformance will now generate a warning (see "Implications on Adoption" for discussion of how to handle this).

ABI compatibility

This proposal is purely an extension of the ABI of the standard library and does not change any existing features.

Implications on adoption

The new conformances require Swift 6.4 or later. Adopters may simply declare the conformances when deploying to earlier Swift versions. For example:

#if swift(<6.4)
  extension Dictionary.Keys: @retroactive Hashable {}
#endif

Note: if existing code on an earlier Swift version also implements these functions, there is a low, theoretical risk of binary compatibility issues at runtime if those implementations are fundamentally incompatible or conflict with the standard library implementations.

Alternatives considered

Don't include the Hashable conformance for EmptyCollection

Asides the reasons of completeness and consistency with other standard library collection types, use cases for working with EmptyCollections in a hash-based context can be avoided (e.g. by working with result ?? EmptyCollection<T> instead). However, such workarounds may not be idiomatic for that use case.

Add Hashable conformance to Dictionary.Values

Unlike Dictionary.Keys, which represents a set-like collection of unique elements, Dictionary.Values can contain duplicates. A proper multiset comparison would require sorting or counting, adding non-trivial cost. As the goal of this proposal is to add trivial missing conformances rather than design new data structures or algorithms, Hashable conformance for Dictionary.Values has been excluded.