[Pitch] Hashable Conformance for Dictionary.Keys, CollectionOfOne and EmptyCollection

Evolution Pitches
1

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.3, *)
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.3, *)
extension CollectionOfOne: Equatable where Element: Equatable {}

@available(SwiftStdlib 6.3, *)
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.3, *)
extension EmptyCollection: Hashable {}

Source compatibility

This is a purely additive change, and the hash and == functions use @_alwaysEmitIntoClient to back-deploy.

ABI compatibility

This proposal is purely an extension of the ABI of the standard library and does not change any existing features. The new conformances are guarded with @available(SwiftStdlib 6.3, *).

Implications on adoption

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

#if swift(<6.3)
  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.

12 Likes
2

I agree you can, and I agree that there's no particular harm in doing so. But why do you care? Under what circumstance do you want any of these to be, eg. a dictionary key?

I generally advise that Hashable is something you shouldn't do "because you can", but only where it actually makes logical sense. Maybe "it's in the stdlib, and someone might care" is good enough reason. But how did you come to care?

3

Well, for Dictionary.Keys it goes without saying that it should be Hashable. Reasons for the usefulness of Dictionary.Keys being Hashable are exactly the same as for Set being Hashable. Also, the implementation of the hash function for a fundamental type as Dictionary.Keys can easily be incorrect or inefficient. So it can be helpful to have the implementation of such functions included in the standard library.

For CollectionOfOne and EmptyCollection, as mentioned in the pitch, the addition is mostly for completeness and consistency, more so for EmptyCollection. Abstract use cases exist, such as EmptyCollection providing the guard rails for being a member of say, a power set. But even such cases can easily be avoided. However, there may be one or two other reasonable use cases that I am not aware of.

2 Likes