Eq () and hash () in Python: Difference between revisions
| Line 19: | Line 19: | ||
3. If the bucket array needs resizing, '''re-use the previously computed hash value''' to re-insert all previously stored values. This is why is important that the key is immutable: if the key is mutable and it changes while the key/value pair is stored in the dictionary, lookup and resizing will not work. | 3. If the bucket array needs resizing, '''re-use the previously computed hash value''' to re-insert all previously stored values. This is why is important that the key is immutable: if the key is mutable and it changes while the key/value pair is stored in the dictionary, lookup and resizing will not work. | ||
To retrieve a key from the dictionary: | |||
1. Call <code>__hash__()</code> on the key and compute the hash of the key. If the key is not hashable, raise a <code>TypeError</code>. | |||
2. Locate the hash_value % len(buckets) bucket | |||
3. Iterate the bucket for an entry matching the hash value. <font color=darkkhaki>Why? Don't all keys stored in the bucket have the same hash value already?</font>. If an entry exists, <font color=darkkhaki>check for equality, first by identity then by calling <code>__eq__()</code>.</font> | |||
Revision as of 16:21, 11 September 2022
Internal
Overview
__eq__()
__hash__()
Dictionaries and the __hash__() Function
To store a key into a dictionary, Python performs the following sequence:
1. Call __hash__() on the key and compute the hash of the key. If the key is not hashable, raise a TypeError.
2. Store (hash_value, key, value) in the bucket at the location hash_value % len(buckets)
3. If the bucket array needs resizing, re-use the previously computed hash value to re-insert all previously stored values. This is why is important that the key is immutable: if the key is mutable and it changes while the key/value pair is stored in the dictionary, lookup and resizing will not work.
To retrieve a key from the dictionary:
1. Call __hash__() on the key and compute the hash of the key. If the key is not hashable, raise a TypeError.
2. Locate the hash_value % len(buckets) bucket
3. Iterate the bucket for an entry matching the hash value. Why? Don't all keys stored in the bucket have the same hash value already?. If an entry exists, check for equality, first by identity then by calling __eq__().