Python dictionary is the most flexible built-in data structure type in Python besides list. A list is an ordered combination of objects, and a dictionary is an unordered collection of objects. The difference between the two is that the elements in the dictionary are accessed by keys, not by offsets.
Using subscript index in the list can quickly get the corresponding value, so we need to do two things:
- How to calculate a unique value for a key
- How to distribute this unique value uniformly and uniquely in a fixed length list
How to calculate a unique value for a key
Because the key of the dictionary is immutable and can be hashed, we can use the hash function to calculate the unique hash value corresponding to the key.
How to distribute this unique value uniformly and uniquely in a fixed length list
Hash hash is an algorithm that can map large data sets to fixed length data sets, so we can hash the hash values calculated above. Obviously, there will be hash conflicts after hashing. Therefore, we need to deal with this conflict, and the unique value can be uniformly and uniquely distributed. At this time, there are two methods to deal with hash conflict: zipper method and open address method
<!--more-->
Zipper method
Put K and V pairs with the same hash address in the same single linked list. The following two functions are implemented
- Put function: put(slots, key, value), which is used to insert data into the dictionary
- Get function: get(slots, key), which is used to read data from the dictionary.
You can also implement more functions, such as dict.keys()
#!/usr/bin/env python # coding=utf-8 slots = [] slotsNum = 32 for _ in range(32): slots.append([]) def put(slots, key, value): i = hash(key) % slotsNum pos = -1 for pos, (k, v) in enumerate(slots[i]): if key == k: break else: slots[i].append((key, value)) if pos >= 0 and pos < len(slots[i]): slots[i][pos] = (key, value) def get(slots, key): i = hash(key) % slotsNum for k, v in slots[i]: if key == k: return v else: raise KeyError(key) # Throw an exception when it does not exist put(slots, 'a', 1) print(get(slots, 'a')) put(slots, 'b' ,2) print(get(slots, 'b')) put(slots, 'a', 3) print(get(slots, 'a'))
These two functions are encapsulated into classes
class Dict: def __init__(self, num): self.__solts__ = [] self.num = num for _ in range(num): self.__solts__.append([]) def put(self, key, value): i = hash(key) % self.num for p, (k, v) in enumerate(self.__solts__[i]): if k == key: break else: self.__solts__[i].append((key, value)) return self.__solts__[i][p] = (key, value) def get(self, key): i = hash(key) % self.num for k, v in self.__solts__[i]: if k == key: return v raise KeyError(key) # keys function def keys(self): ret = [] for solt in self.__solts__: for k, _ in solt: ret.append(k) return ret
After being encapsulated into a class, the usage method is similar to the dict provided by Python
Open address method
When the Python dictionary is implemented internally, the method to deal with hash conflicts is the open address method, which will be supplemented later
- Notes on Python source code analysis - Chapter 5 dict objects in Python
- Python dictionary implementation
Remember to give me some praise!
Carefully sorted out the video courses and e-books in all directions of the computer, including introduction, advanced and actual combat. According to the reasonable classification of the catalogue, you can always find the learning materials you need. What are you waiting for? Pay attention to the download!!!
Never forget, there must be an echo. My friends, please give me a compliment. Thank you very much.
I am a bright brother in the workplace, YY Senior Software Engineer, four years of working experience, and a slash programmer who refuses to be a leader.
Listen to me, more progress, program life is a shuttle
If you are lucky enough to help you, please give me a "like" and give me attention. If you can comment and encourage me, I will be very grateful.
List of articles in the workplace: More articles
All my articles and answers are in cooperation with the copyright protection platform. The copyright belongs to brother Liang in the workplace. Unauthorized reprinting must be investigated!