Whether the dictionary is ordered
Prior to Python 3.6, dictionaries were unordered, but with Python 3.7+, they are ordered.
Dictionary ordering was an implementation detail in 3.6, and only became a formal language feature in 3.7, so 100% ordering could not be ensured in 3.6.
Time complexity of dictionary lookups, additions, and deletions
The average time complexity of querying, adding, and deleting of dictionaries is O(1), which gives better performance compared to lists vs. metazoans.
Dictionary Implementation Principles
Unordered dictionaries before Python 3.6
The bottom of the dictionary is to maintain a hash table, you can think of the hash table as a list, each element in the hash table and store the hash value (hash), the key (key), the value (value) of the three elements.
enteies = [
['--', '--', '--'],
[hash, key, value],
['--', '--', '--'],
['--', '--', '--'],
[hash, key, value],
]
Bring in specific values to introduce
# Add a value to the dictionary with key hello and value word
# my_dict['hello'] = 'word'
# The initial hash table is as follows
enteies = [
['--', '--', '--'],
['--', '--', '--'],
['--', '--', '--'],
['--', '--', '--'],
['--', '--', '--'],
]
hash_value = hash('hello') # Assuming a value of 12343543
index = hash_value & ( len(enteies) - 1) # Assuming the index value is calculated to be equal to 3
# The following will store the value in enteies
enteies = [
['--', '--', '--'],
['--', '--', '--'],
['--', '--', '--'],
[12343543, 'hello', 'word'], # index=3
['--', '--', '--'],
]
# Continue to add values to the dictionary
# my_dict['color'] = 'green'
hash_value = hash('color') # Assuming a value of Also 12343543
index = hash_value & ( len(enteies) - 1) # Assuming that the index value is also calculated to be equal to 3
# The following will store the value in enteies
enteies = [
['--', '--', '--'],
['--', '--', '--'],
['--', '--', '--'],
[12343543, 'hello', 'word'], # Since the index=3 position is already occupied and the key is not the same, it is determined to be a hash conflict, continue to search downward
[12343543, 'color', 'green'], # If you find a free position, save it
]
The enteies table is sparse, and as we insert different values, the enteies table gets sparser and sparser (enteies is also one that dynamically expands in length, and for each such expansion, the hash values of all the keys are recalculated), so new dictionary implementations follow.
New implementations after Python 3.7+
Python 3.7 + bring in data demo
# Add a value to the dictionary with the key hello and the value word
# my_dict['hello'] = 'word'
# Assuming an empty list, the hash table is initially as follows
indices = [None, None, None, None, None, None]
enteies = []
hash_value = hash('hello') # Assuming a value of 12343543
index = hash_value & ( len(indices) - 1) # Assuming the index value is calculated to be equal to 3
# It will find the index of the indices at 3 #
indices = [None, None, None, 0, None, None]
# At this point enteies will be inserted into the first element #
enteies = [
[12343543, 'hello', 'word']
]
# We continue to add values to the dictionary
my_dict['haimeimei'] = 'lihua'
hash_value = hash('haimeimei') # Assumes a value of 34323545
index = hash_value & ( len(indices) - 1) # Assume that the index value is calculated to be equal to 0
# It will find the location where index of indices is 0 #
indices = [1, None, None, 0, None, None]
# At this point enteies will be inserted into the first element #
enteies = [
[12343543, 'hello', 'word'],
[34323545, 'haimeimei', 'lihua']
]
Search Dictionary
# Here's a dictionary with a dictionary store #
more_dict = {'name': 'Zhang San', 'sex': 'Male', 'age': 10, 'birth': '2019-01-01'}
# Physical storage of data
indices = [None, 2, None, 0, None, None, 1, None, 3]
enteies = [
[34353243, 'name', 'Zhang San'],
[34354545, 'sex', 'Male'],
[23343199, 'age', 10],
[00956542, 'birth', '2019-01-01'],
]
print(more_dict['age']) # When we execute this sentence
hash_value = hash('age') # Assumed value 23343199
index = hash_value & ( len(indices) - 1) # index = 1
entey_index = indices[1] # The data in the enteies is in position 2
value = enteies[entey_index] # So find the value enteies[2] #
time complexity
The average time complexity of a dictionary is O(1) because dictionaries are implemented by hashing algorithms, and an unavoidable problem with hash algorithms is hash conflicts, and Python dictionaries that have hash conflicts will look down for a free position until a position is found.
If the time complexity of the dictionary becomes O(n) if no free position is ever found when computing the hash value of the key.
Common Hash Conflict Resolution
1 Open addressing method (open addressing)
In the open addressing method, all the elements are stored in the hash table, when a hash conflict arises, the next candidate location is calculated by a probe function, if the next selected location is still a conflict, then the probe function is constantly looking down until an empty slot is found to store the element to be inserted.
2 Re-hashing
This method is in order to specify a number of hash functions, each time the query in order to call the hash function, call to the first null when the return does not exist, call to this key to return its value.
3 Chain address method
All the records with the same keyword hash value are stored in the same linear chain table, so as not to take up other hash addresses, the same hash value in a chain table, traversed in order to find.
4 Public overflow areas
The basic idea is that all keywords and the basic table keywords for the same hash value of the record, regardless of their hash address obtained by the hash function, once the conflict occurs, are filled into the overflow table.
summarize
The above is a personal experience, I hope it can give you a reference, and I hope you can support me more.