Explication détaillée d'exemples d'implémentation de dictionnaire à l'aide de la méthode Zipper-Tutoriel Python-php.cn

Explication détaillée d'exemples d'implémentation de dictionnaire à l'aide de la méthode Zipper

高洛峰

Libérer： 2017-03-26 16:53:52

original

1898 Les gens l'ont consulté

Dictionnaire :

est également appelé table de hachage. Sa plus grande caractéristique est la complexité temporelle nécessaire pour trouver sa valeur correspondante via clé. C'est O(1).

Comment utiliser des listes pour implémenter des dictionnaires en Python ?

Le plus gros problème dans l'utilisation de listes pour implémenter des dictionnaires est de résoudre le conflit de hachage, si vous obtenez la même position en calculant différentes clés dans la liste, que devez-vous faire ?

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

Explication détaillée dexemples dimplémentation de dictionnaire à laide de la méthode Zipper

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).

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(&#39;No such {} key&#39;.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(&#39;No such {} key&#39;.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(&#39;No such {} key&#39;.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

Copier après la connexion

L'heure trouvée grâce à la clé est visible dans l'image ci-dessous

Explication détaillée dexemples dimplémentation de dictionnaire à laide de la méthode Zipper