지퍼 방식을 사용하여 사전 방식을 구현한 파이썬의 예제 코드에 대한 자세한 설명

이 글에서는 지퍼 방식을 사용하여 사전을 구현하는 python 방법을 주로 소개합니다. 이 글은 상세한 샘플 코드를 제공하므로 필요한 모든 사람들이 찾아올 수 있을 것입니다. 아래에서 함께 살펴보세요.

서문

사전은 해시 테이블이라고도 합니다. 가장 큰 특징은 키를 통해 해당 값을 찾는 것입니다. 1) 다음 글에서는 지퍼 방식을 사용하여 파이썬에서 사전을 구현하는 방법을 소개하겠습니다.

Python에서 목록을 사용하여 사전을 구현하는 방법은 무엇입니까?

목록을 사용하여 사전을 구현할 때 가장 큰 문제는 해시 충돌이 발생하는 경우 다른 키를 계산하여 동일한 위치를 얻으려면 어떻게 해야 합니까?

가장 간단한 방법은 지퍼 방식을 사용하는 것입니다.

지퍼 방식: 목록의 각 위치에 다른 목록을 추가합니다. 해시 충돌도 저장할 수 있습니다. 선택한 해시

함수 가 충분하고

num의 수가 충분히 크면 각 목록에 하나의 요소만 있는지 확인할 수 있습니다. 목록. 키를 기준으로 요소의 위치를 ​​계산한 후

을 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

키로 찾아낸 시간은 아래 그림에서 확인할 수 있습니다

위 내용은 지퍼 방식을 사용하여 사전 방식을 구현한 파이썬의 예제 코드에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!