Dictionary:
is also called a hash table. Its biggest feature is the time complexity of finding its corresponding value through key It is O(1).
How to use lists to implement dictionaries in Python?
The biggest problem in using lists to implement dictionaries is to solvehashConflict, if you get the same position in the list by calculating different keys, 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.
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[self._num](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 picture below
The above is the detailed content of Detailed explanation of examples of dictionary implementation using the zipper method. For more information, please follow other related articles on the PHP Chinese website!