A brief discussion on dictionaries and hash tables in Python and the resolution of hash conflicts

The content of this article is about a brief discussion of dictionaries and hash tables in Python and the resolution of hash conflicts. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Python uses hash tables to implement dict.

A hash table is actually a sparse array (an array that always has blank elements is called a sparse array). In general books, the units in a hash table are usually called buckets. exist dict In the hash table, each key-value pair occupies a table element, and each table element has two parts, one is a reference to the key, and the other is a reference to the value. Because each table cell is the same size, you can read a table cell by offset.

Python will try to ensure that about one-third of the table elements are empty. When this threshold is almost reached, it will expand and copy the original hash table to a larger hash table. .

If you want to put an object into a hash table, you must first calculate the hash value of the element key. This requires that the key must be hashable.

A hashable object must meet the following conditions:

Support the hash() function, and the hash value obtained through the __hash__() method is unchanged.

Supports equality detection through the __eq__() method.

If a == b is true, then hash(a) == hash(b) is also true.

The following mainly explains the hash table algorithm.

To get the key The value search_value corresponding to search_key, Python will first call hash(search_key) to calculate search_key The hash value of the value, the lowest few digits of this value are used as offsets, and the table element is searched in the hash table (the specific number depends on the size of the current hash table). If the found table element is empty, KeyError is thrown Exception; if it is not empty, there will be a pair of found_key:found_value in the table element, check search_key and found_key Whether they are equal, if so, return found_value. If they are not equal, this situation is called a hash collision.

In order to solve the hash conflict, the algorithm will take a few more bits in the hash value, then process it with a special method, and use the new value obtained as an offset to search in the hash table table element, if the found table element is empty, a KeyError exception will also be thrown; if it is not empty, compare the keys to see if they are consistent, and return the corresponding value if they are consistent; if a hash conflict is found, repeat the above steps.

Adding a new element is almost the same as the above process, except that when an empty table element is found, the new element will be put in. If it is not empty, the hash will be repeated and the search will continue.

When to go When a new element is added to the dict and a hash conflict occurs, the new element may be arranged to be stored in another location. So the following situation will happen: dict([key1, value1], [key2, value2]) and dict([key2, value2], [key1, value1]) Two dictionaries are equal when compared, but if the hashes of key1 and key2 conflict, the order of the two keys in the dictionary is different.

Whenever, go Add new keys to dict, python The parser may decide to expand the dictionary. The result of expansion is to create a larger hash table and add existing elements in the dictionary to the new hash table. New hash conflicts may occur during this process, causing the order of keys in the new hash table to change. What happens if you iterate over a dictionary while adding new keys to it? Unfortunately, the capacity was expanded. Unfortunately, the order of the keys changed, and then orz.

Since the hash table must be sparse, its space consumption must be much larger. This is a typical space-for-time trade-off.

The above is the detailed content of A brief discussion on dictionaries and hash tables in Python and the resolution of hash conflicts. For more information, please follow other related articles on the PHP Chinese website!