Swift：字典的Key类型为何必须遵循Hashable协议？

Great question! It's totally reasonable to wonder why Equatable isn't enough—let's unpack this with how dictionaries actually operate under the hood.

First: Why Equatable alone isn't sufficient #

If a dictionary only relied on Equatable, every time you tried to look up a value, the program would have to compare your key to every single key in the dictionary to find a match. That's an O(n) operation—slow and inefficient, especially as the number of key-value pairs grows. For dictionaries, we need lookups, inserts, and deletes to be fast (ideally O(1) average time), and Equatable alone can't deliver that.

What Hashable adds (and why it's critical) #

Hashable inherits from Equatable, so it includes all the equality-checking functionality you need—plus it adds a way to generate a hash value (via hash(into:) in modern Swift, or the old hashValue property). This hash value is a numerical representation of the key, and it's used to map the key to a specific "bucket" in a hash table (the underlying data structure of a dictionary).

Here's how this makes operations fast:

• When inserting a key-value pair: Calculate the key's hash, map it to a bucket, and store the pair there.
• When looking up a value: Calculate the key's hash to jump straight to the relevant bucket, then only use Equatable to compare keys within that bucket (to handle rare hash collisions, where two different keys produce the same hash value).

This cuts the average time complexity for core operations to O(1)—a massive performance improvement over O(n).

How dictionaries are implemented (simplified) #

At their core, Swift dictionaries are hash tables. Here's a simplified breakdown of their workflow:

• Hash Calculation: For any key, compute its hash value using the type's Hashable implementation.
• Bucket Mapping: Use a hash function to convert the hash value into an index for one of the buckets in the hash table array.
• Collision Handling: If two keys map to the same bucket (a collision), the dictionary stores them in a linked list (or similar structure) within that bucket. When accessing, it uses Equatable to check each entry in the bucket until it finds a matching key.
• Resizing: As the dictionary fills up, it will periodically resize the underlying array of buckets to keep collisions rare and maintain performance.

Key rules for Hashable compliance #

To ensure dictionaries work correctly, types conforming to Hashable must follow two rules:

• If two keys are equal (per Equatable's ==), they must produce the same hash value.
• While not required, it's ideal for different keys to produce different hash values (to minimize collisions and keep operations fast).

内容的提问来源于stack exchange，提问作者rahulg