Detaillierte Erläuterung des Beispielcodes von Python unter Verwendung der Zipper-Methode zur Implementierung der Wörterbuchmethode

In diesem Artikel wird hauptsächlich die Python-Methode zur Implementierung eines Wörterbuchs vorgestellt. Der Artikel bietet einen gewissen Referenzwert für alle, die ihn benötigen Besuchen Sie uns unten.

Vorwort

Wörterbücher werden auch Hash-Tabellen genannt. Die größte Funktion besteht darin, den entsprechenden Wert über Schlüssel zu finden. 1) Im folgenden Artikel erfahren Sie, wie Sie mithilfe der Zipper-Methode ein Wörterbuch in Python implementieren.

Wie implementiert man ein Wörterbuch mithilfe einer Liste in Python?

Das größte Problem bei der Verwendung einer Liste zur Implementierung eines Wörterbuchs besteht darin, den Hash Konflikt. Wenn in der Liste verschiedene Schlüssel berechnet und die gleiche Position ermittelt wird. Was sollten Sie zu diesem Zeitpunkt tun?

Am einfachsten geht es mit der Zipper-Methode.

Die Zipper-Methode: Fügen Sie an jeder Position in einer Liste eine weitere Liste hinzu, damit diese auch dort vorhanden ist Es können auch Hash-Konflikte gespeichert werden, wenn die ausgewählte Hash-

-Funktion gut genug ist und die Anzahl der

num groß genug ist, kann sichergestellt werden, dass in jeder Liste nur ein Element vorhanden ist die Liste. Berechnen Sie die Position des Elements basierend auf dem Schlüssel und ermitteln Sie dann den Wert, um

bis O(1)-Zeit zu erreichen.

Methodenbeispiel

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

Die durch den Schlüssel gefundene Zeit ist in der Abbildung unten zu sehen

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung des Beispielcodes von Python unter Verwendung der Zipper-Methode zur Implementierung der Wörterbuchmethode. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!