Home > Article > Backend Development > Detailed explanation of python's example code for implementing dictionary method using zipper method
This article mainly introduces the method of python using the zipper method to implement a dictionary. The article gives detailed sample codes. I believe it has certain reference value for everyone. Friends who need it can come and join us below. Let's see.
Preface
The dictionary is also called a hash table. The biggest feature is to find the corresponding value through key. Its time complexity is O( 1), the following article will introduce to you how to implement a dictionary in Python using the zipper method.
How to use a list to implement a dictionary in Python?
The biggest problem with using a list to implement a dictionary is to solve the hash conflict. If passed in the list Calculate different keys and get the same position. What should you do at this time?
The simplest way is to use the zipper method.
The zipper method: Add another list at each position in a list, so that even if there is Hash conflicts can also be stored. When the selected hashfunction is good enough and the number of
num is large enough, it can ensure that there is only one element in each list. Calculate the location of the element based on the key, and then get the value to achieve
to O(1) time.
Method example
class MyDict: def init(self, num=100): # 指定列表大小 self._num = num self._lst = [] for _ in range(self._num): self._lst.append([]) def update(self, key, value): # 添加 key-value key_index = hash(key) % self._num for i, (k, v) in enumerate(self._lst[key_index]): if key == k: self._lst[key_index][i] = [key, value] break else: self._lst[key_index].append([key, value]) def get(self, key): # 根据指定的 key 弹出值 key_index = hash(key) % self._num for k, v in self._lst[key_index]: if k == key: return v else: raise KeyError('No such {} key'.format(key)) def pop(self, key): # 根据 key 弹出元素 并且删除 key_index = hash(key) % self._num for i, (k, v) in enumerate(self._lst[key_index]): if k == key: result = v self._lst.pop(i) return result else: raise KeyError('No such {} key'.format(key)) def getitem(self, key): # 可以通过下标来取值 key_index = hash(key) % self._num for k, v in self._lst[key_index]: if k == key: return v else: raise KeyError('No such {} key'.format(key)) def keys(self): # 取得所有的key for index in range(self._num): for k, v in self._lst[index]: yield k def values(self): # 取得所有的 value for index in range(self._num): for k, v in self._lst[index]: yield v def items(self): # 取得所有的条目 for index in range(self._num): for item in self._lst[index]: yield item
The time found through key can be seen in the figure below
The above is the detailed content of Detailed explanation of python's example code for implementing dictionary method using zipper method. For more information, please follow other related articles on the PHP Chinese website!