ジッパー方式による辞書実装例を詳しく解説

辞書:

は、keyを介して対応する値を見つけるための時間計算量がO(1)であることは、ハッシュテーブルとも呼ばれます。 辞書の実装?

リストを使用して辞書を実装する場合の最大の問題は、リスト内の異なるキーを計算して同じ位置が得られる場合、この時点でどうすればよいでしょうか?

最も簡単な方法は、Zipper メソッドを使用することです。

Zipper メソッド: リスト内の各位置に別のリストを追加して、ハッシュの競合があってもそのリストに格納できるようにします。選択されたハッシュ関数

が十分である場合、

num の数は、リスト内の各リストに要素が 1 つだけ含まれるようにするのに十分な大きさです。キーに基づいて要素の位置を計算し、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('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

キーを通して見つけた時刻は下の写真で見ることができます

以上がジッパー方式による辞書実装例を詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。