The core of the dictionary object is Hash table . The hash table is a sparse array ( An array that always has blank elements ), Each cell of the array is called bucket.
Every bucket There are two parts ： One is a reference to a key object , One is a reference to a value object
because , all bucket Consistent structure and size , We can read the specified by offset bucket
Putting a key value pair into the underlying process of the dictionary :
Suppose the dictionary a After object creation , The array length is 8
We are going to put ‘name’='cs’ This key value pair is placed in the dictionary object a in , The first step is to calculate the key “name” Hash value .Python Through hash（） To calculate
# The result of printing is ：0b10011001000000110000011001111011111011111100101100111111011001
print(bin(hash(“name”)))
Because the array length is 8, We can take the rightmost side of the calculated hash value 3 Bit number as offset , namely “001”, Decimal is a number 1, Let's look at the offset 1, Corresponding bucket Is it empty .
If it is empty , Then put the key value pair in . If it's not empty , Then take the right 3 Bit as offset , namely “011”, Decimal is a number 3, Check again that the offset is 3 Of bucket Is it empty .
Until you find an empty bucket Put it in , If they are not empty , Then the array will be expanded , Then the offset will change , Until the key value pairs are put in
Array capacity ： If the array has 2/3 Is already full , Then the array will be expanded , Bigger
Search by key “ Key value pair ” The underlying process ： It is similar to the process of putting key value pairs into a dictionary
Be careful ： Because the offset is 3 position 3 I started looking for , We're not sure if it's the same one “ Key value pair ”, So when we find it, we will find it “ key ” Take it out and calculate the hash value , If the hash values are the same , Then return to
If different , It means it's not the same “ Key value pair ”, Then keep looking , Until you find the same
Usage Summary ：
1. Keys must be hashable ：
（1） Numbers , character string , Tuples are hashable
（2） Custom objects need to support the following three points ：① Support hash（） function ② Supported by _eq_() Method to detect identity ③ if a == b It's true , be hash（a）== hash(b) It's true
2. Dictionaries are expensive in memory , Typical space for time
3. Key query speed is very fast
4. Adding a new item to the dictionary leads to capacity expansion , Causes the order of keys in the hash table to change . therefore , Don't modify the dictionary while traversing the dictionary
