この記事では主に Python を使用して辞書を実装する方法を紹介します。この記事には詳細なサンプルコードが記載されているので、必要な方は以下を参照してください。
はじめに
辞書はハッシュテーブルとも呼ばれ、その最大の特徴はkeyを介して対応する値を見つけることです。次の記事ではPythonでジッパーを使用する方法を紹介します。辞書を実装するメソッド。
Python でリストを使用して辞書を実装する方法
リストを使用して辞書を実装する場合の最大の問題は、リスト内の異なるキーを計算して同じ位置を取得した場合にどうするかです。 ? ? 最も簡単な方法は、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(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
キーによって検索された時刻は、下の写真に表示されます
以上がジッパーメソッドを使って辞書メソッドを実装するPythonのサンプルコードを詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。