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!