Maison  >  Article  >  développement back-end  >  Explication détaillée de l'exemple de code Python utilisant la méthode Zipper pour implémenter la méthode du dictionnaire

Explication détaillée de l'exemple de code Python utilisant la méthode Zipper pour implémenter la méthode du dictionnaire

高洛峰
高洛峰original
2017-03-26 09:46:281854parcourir

Cet article présente principalement la méthode python d'utilisation de la méthode zipper pour implémenter un dictionnaire. L'article fournit un exemple de code détaillé. Je pense qu'il a une certaine valeur de référence pour tous les amis qui en ont besoin. rejoignez-nous ci-dessous.

Préface

Les dictionnaires sont également appelés tables de hachage. La plus grande fonctionnalité est de trouver la valeur correspondante via clé. 1), l'article suivant vous présentera comment implémenter un dictionnaire en Python à l'aide de la méthode zipper.

Comment implémenter un dictionnaire à l'aide d'une liste en Python ?

Le plus gros problème lié à l'utilisation d'une liste pour implémenter un dictionnaire est de résoudre le hachage conflit. Si passé dans la liste Calculer différentes clés et obtenir la même position Que devez-vous faire à ce moment-là ?

Le moyen le plus simple est d'utiliser la méthode de la fermeture éclair.

Explication détaillée de lexemple de code Python utilisant la méthode Zipper pour implémenter la méthode du dictionnaire

La méthode de la fermeture éclair : ajoutez une autre liste à chaque position d'une liste, de sorte que même s'il y a Ces conflits de hachage peuvent également être stockés. Lorsque la fonction de hachage sélectionnée est suffisamment bonne et que le nombre de

num est suffisamment grand, il peut garantir qu'il n'y a qu'un seul élément dans chaque liste. la liste. Calculez l'emplacement de l'élément en fonction de la clé, puis obtenez la valeur à atteindre

au temps O(1).

Exemple de méthode


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

L'heure trouvée par clé est visible dans la figure ci-dessous

Explication détaillée de lexemple de code Python utilisant la méthode Zipper pour implémenter la méthode du dictionnaire

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn