Ausführliche Erläuterung von Beispielen für die Wörterbuchimplementierung mithilfe der Zipper-Methode

Wörterbuch:

wird auch als Hash-Tabelle bezeichnet. Das größte Merkmal ist die zeitliche Komplexität, den entsprechenden Wert über Schlüssel zu finden Es ist O(1).

Wie verwende ich Listen zur Implementierung von Wörterbüchern in Python?

Das größte Problem besteht bei der Verwendung von Listen zur Implementierung von Wörterbüchern besteht darin, den HashKonflikt zu lösen. Was sollten Sie tun, wenn Sie durch die Berechnung verschiedener Schlüssel in der Liste die gleiche Position erhalten?

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.

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

Die durch den Schlüssel gefundene Zeit ist im Bild unten zu sehen

Das obige ist der detaillierte Inhalt vonAusführliche Erläuterung von Beispielen für die Wörterbuchimplementierung mithilfe der Zipper-Methode. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!