python The underlying implementation of the dictionary is a hash table . call python Built in hash function , Will key （key） Convert as a parameter （ Hash operation + Take over operations ）, Get a unique address （ Index of address ）, Then set the value （value） Store in the corresponding address （ Assigning values to the same keys directly overwrites the original values , Because the address after the same key conversion is the same ）
Hashtable （Hash Table, Also known as hash table ） Is a linear table storage structure . By a direct addressing table T ( Assume the size is m) And a hash function h(k) form . For any hashable object , By hash function （ Generally, hash calculation is performed first , Then the result is remainder ）, Map this object to the index of the addressing table [0,1,2,…m-1], Then in the space corresponding to the index T[0,1,2,…,m-1] Storage of variables / Read and so on . As shown in the figure below .
Store data in a sequence table
Store key value timing , Calculate the index corresponding to the key through the hash function , Store the value in the data area corresponding to the index
When getting data , Calculate the index corresponding to the key through the hash function , Get the data corresponding to the index 
notes ： key （Key） Must be hashable , namely , The unique address of this key can be calculated by hash function .
about Python Come on , Variable , list 、 Dictionaries 、 These sets are variable , So it can't be used as a key （Key） To use . Because variable elements such as lists can be stored in tuples , So if you really want to use tuples as dictionary keys （Key）, That must be restricted to tuples ： When tuples contain only immutable elements such as numbers and strings , Can be used as a valid key in the dictionary （Key）. Another thing to note is ,Python The hash algorithm calculates the same result for the same value , in other words 12315 and 12315.0 The value of is the same , They are considered to be the same key （Key）.
Insert ： Hash and remainder keys , Get the index of a hash table , If the table address space corresponding to the index is empty , Store the key value pair in the address space ;
Inquire about / to update ： Hash and remainder keys , Get the index of a hash table , If the address space corresponding to the index contains the key to be queried / The updated keys are consistent , Then take out the key value pair / Update the value corresponding to the key ;
Capacity expansion ： When the dictionary is initialized , Will initialize a corresponding one with k A spatial table , When there's not enough space , The system will automatically expand , At this time, the existing key value pairs Redo hash remainder operation （ Re insert ） Save to another location ;
For any hash function , There will be two different elements mapped to the same location , This is called a hash conflict
Each position of the hash table is connected to a linked list , When there is a conflict , Conflicting elements will be added to the end of the linked list at that location 
If the hash function gets the position i There's already data , Then probe back to a new location to store this value
Linear detection ： If i Have the data , Detection i+1,i+2… And so on , Until we find an empty place
a、key=apple,cat,dog,hello, The values obtained from the hash function mapping are 2
b、 There is an existing dictionary dic={‘apple’:1,‘cat’:2,‘dog’:3}, Store the data ,
c、 Original lead 2 The location of does not store data , At this time will be apple Value 1 Store in this
d、 next cat Addressing to index is 2 The location of , It is found that this position has value , Will continue to probe backwards , By analogy
a、 obtain dic[‘dog’] When , First come index is 2 Where to get
b、 Failed to get continue backward probe
dic.remove(‘cat’)
a、 Define a state for each node
not used
Already used
deleted
Open chain method ：
advantage ： Deleting a node is easier , The data volume is relatively large, and the open chain method is used
shortcoming ： The use space is relatively large
Open addressing ：
Deleting a node cannot really delete a node , Define a state for each node , The data volume is relatively small. Use the open addressing method
shortcoming ：
a、 Use open addressing , Then the sequence table will fill up one day
b、 Generally, to ensure the efficiency of insertion and search , The hash table is generally in the range of the number of elements in the capacity 2/3 when , It's going to expand
c、 After the expansion , The computed hash function also changes , The order in which the data is stored will also change
