Detailed explanation of examples of dictionary implementation using the zipper method-Python Tutorial-php.cn

Detailed explanation of examples of dictionary implementation using the zipper method

高洛峰

Release： 2017-03-26 16:53:52

Original

1870 people have browsed it

Dictionary:

is also called a hash table. Its biggest feature is the time complexity of finding its corresponding value through key It is O(1).

How to use lists to implement dictionaries in Python?

The biggest problem in using lists to implement dictionaries is to solvehashConflict, if you get the same position in the list by calculating different keys, what should you do at this time?

The simplest way is to use the zipper method.

Detailed explanation of examples of dictionary implementation using 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.

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

Copy after login

The time found through key can be seen in the picture below

Detailed explanation of examples of dictionary implementation using the zipper method

The above is the detailed content of Detailed explanation of examples of dictionary implementation using the zipper method. For more information, please follow other related articles on the PHP Chinese website!