溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

使用python實現(xiàn)哈希表、字典、集合操作

發(fā)布時間：2020-08-29 22:50:19 來源：腳本之家 閱讀：251 作者：學(xué)海無涯苦作舟 欄目：開發(fā)技術(shù)

哈希表

哈希表（Hash Table, 又稱為散列表），是一種線性表的存儲結(jié)構(gòu)。哈希表由一個直接尋址表和一個哈希函數(shù)組成。哈希函數(shù)h(k)將元素關(guān)鍵字k作為自變量，返回元素的存儲下標(biāo)。

簡單哈希函數(shù)：

除法哈希：h(k) = k mod m乘法哈希：h(k) = floor(m(kA mod 1)) 0<A<1

假設(shè)有一個長度為7的數(shù)組，哈希函數(shù)h(k) = k mod 7,元素集合{14, 22, 3, 5}的存儲方式如下圖：

使用python實現(xiàn)哈希表、字典、集合操作

哈希沖突

由于哈希表的大小是有限的，而要存儲的值的總數(shù)量是無限的，因此對于任何哈希函數(shù)，都會出現(xiàn)兩個不同的元素映射到同一個位置上的情況，這種情況叫做哈希沖突。

比如：h(k) = k mod 7, h(0) = h(7) = h(14) = ...

解決哈希沖突--開放尋址法

開放尋址法：如果哈希函數(shù)返回的位置已經(jīng)有值，則可以向后探查新的位置來存儲這個值

線性探查：如果位置i被占用，則探查i+1, i+2,...二次探查：如果位置i被占用，則探查i+12, i-12, i+22, i-22,...二度哈希：有n個哈希函數(shù)，當(dāng)使用第一個哈希函數(shù)h2發(fā)生沖突時，則嘗試使用h3, h4,...

解決哈希沖突--拉鏈法

拉鏈法：哈希表每一個位置都連接一個鏈表，當(dāng)沖突發(fā)生時，沖突的元素將被加到該位置鏈表的最后。

使用python實現(xiàn)哈希表、字典、集合操作

哈希表的實現(xiàn)

class Array(object):

 def __init__(self, size=32, init=None):
  self._size = size
  self._items = [init] * size

 def __getitem__(self, index):
  return self._items[index]

 def __setitem__(self, index, value):
  self._items[index] = value

 def __len__(self):
  return self._size

 def clear(self, value=None):
  for i in range(len(self._items)):
   self._items[i] = value

 def __iter__(self):
  for item in self._items:
   yield item


class Slot(object):
 """
 定義一個 hash 表數(shù)組的槽(slot 這里指的就是數(shù)組的一個位置)
 hash table 就是一個數(shù)組，每個數(shù)組的元素（也叫slot槽）是一個對象，對象包含兩個屬性 key 和 value。

 注意，一個槽有三種狀態(tài)，看你能否想明白。相比鏈接法解決沖突，探查法刪除一個 key 的操作稍微復(fù)雜。
 1.從未使用 HashMap.UNUSED。此槽沒有被使用和沖突過，查找時只要找到 UNUSED 就不用再繼續(xù)探查了
 2.使用過但是 remove 了，此時是 HashMap.EMPTY，該探查點后邊的元素仍然可能是有key的，需要繼續(xù)查找
 3.槽正在使用 Slot 節(jié)點
 """

 def __init__(self, key, value):
  self.key, self.value = key, value


class HashTable(object):
 UNUSED = None # 沒被使用過
 EMPTY = Slot(None, None) # 使用卻被刪除過

 def __init__(self):
  self._table = Array(8, init=HashTable.UNUSED) # 保持 2*i 次方
  self.length = 0

 @property
 def _load_factor(self):
  # load_factor 超過 0.8 重新分配
  return self.length / float(len(self._table))

 def __len__(self):
  return self.length

 # 進行哈希
 def _hash(self, key):
  return abs(hash(key)) % len(self._table)

 # 查找key
 def _find_key(self, key):
  """
  解釋一個 slot 為 UNUSED 和 EMPTY 的區(qū)別
  因為使用的是二次探查的方式，假如有兩個元素 A，B 沖突了，
  首先A hash 得到是 slot 下標(biāo)5，A 放到了第5個槽，之后插入 B 因為沖突了，所以繼續(xù)根據(jù)二次探查方式放到了 slot下標(biāo)8。
  然后刪除 A，槽 5 被置為 EMPTY。然后我去查找 B，
  第一次 hash 得到的是 槽5，但是這個時候我還是需要第二次計算 hash 才能找到 B。
  但是如果槽是 UNUSED 我就不用繼續(xù)找了，我認(rèn)為 B 就是不存在的元素。這個就是 UNUSED 和 EMPTY 的區(qū)別。
  """
  origin_index = index = self._hash(key) # origin_index 判斷是否又走到了起點，如果查找一圈了都找不到則無此元素
  _len = len(self._table)
  while self._table[index] is not HashTable.UNUSED:
   if self._table[index] is HashTable.EMPTY: # 注意如果是 EMPTY，繼續(xù)尋找下一個槽
    index = (index * 5 + 1) % _len
    if index == origin_index:
     break
    continue
   if self._table[index].key == key: # 找到了key
    return index
   else:
    index = (index * 5 + 1) % _len # 沒有找到繼續(xù)找下一個位置
    if index == origin_index:
     break

  return None

 # 找能插入的槽
 def _find_slot_for_insert(self, key):
  index = self._hash(key)
  _len = len(self._table)
  while not self._slot_can_insert(index): # 直到找到一個可以用的槽
   index = (index * 5 + 1) % _len
  return index

 # 槽是否能插入
 def _slot_can_insert(self, index):
  return self._table[index] is HashTable.EMPTY or self._table[index] is HashTable.UNUSED

 # in operator，實現(xiàn)之后可以使用 in 操作符判斷
 def __contains__(self, key):
  index = self._find_key(key)
  return index is not None

 # 添加元素
 def add(self, key, value):
  if key in self: # update
   index = self._find_key(key)
   self._table[index].value = value
   return False
  else:
   index = self._find_slot_for_insert(key)
   self._table[index] = Slot(key, value)
   self.length += 1
   if self._load_factor >= 0.8:
    self._rehash()
   return True

 # 槽不夠時，重哈希
 def _rehash(self):
  old_table = self._table
  newsize = len(self._table) * 2
  self._table = Array(newsize, HashTable.UNUSED)

  self.length = 0

  for slot in old_table:
   if slot is not HashTable.UNUSED and slot is not HashTable.EMPTY:
    index = self._find_slot_for_insert(slot.key)
    self._table[index] = slot
    self.length += 1

 # 獲取值
 def get(self, key, default=None):
  index = self._find_key(key)
  if index is None:
   return default
  else:
   return self._table[index].value

 # 移除
 def remove(self, key):
  index = self._find_key(key)
  if index is None:
   raise KeyError()
  value = self._table[index].value
  self.length -= 1
  self._table[index] = HashTable.EMPTY
  return value

 # 遍歷
 def __iter__(self):
  for slot in self._table:
   if slot not in (HashTable.EMPTY, HashTable.UNUSED):
    yield slot.key

哈希表的使用

h = HashTable()
h.add('a', 0)
h.add('b', 1)
h.add('c', 2)
print(len(h)) # 3
print(h.get('a')) # 0
print(h.get('b')) # 1
print(h.get('hehe')) # None
h.remove('a')
print(h.get('a')) # None
print(sorted(list(h))) # ['b', 'c']

字典

字典是另一種可變?nèi)萜髂Ｐ?，且可存儲任意類型對象?/p>

字典的每個鍵值key=>value對用冒號:分割，每個鍵值對之間用逗號,分割，整個字典包括在花括號{}中 ,格式如下所示：

d = {key1 : value1, key2 : value2 }

使用python實現(xiàn)哈希表、字典、集合操作

基于哈希表實現(xiàn)字典

class Array(object):

 def __init__(self, size=32, init=None):
  self._size = size
  self._items = [init] * size

 def __getitem__(self, index):
  return self._items[index]

 def __setitem__(self, index, value):
  self._items[index] = value

 def __len__(self):
  return self._size

 def clear(self, value=None):
  for i in range(len(self._items)):
   self._items[i] = value

 def __iter__(self):
  for item in self._items:
   yield item


class Slot(object):
 """
 定義一個 hash 表數(shù)組的槽(slot 這里指的就是數(shù)組的一個位置)
 hash table 就是一個數(shù)組，每個數(shù)組的元素（也叫slot槽）是一個對象，對象包含兩個屬性 key 和 value。

 注意，一個槽有三種狀態(tài)，看你能否想明白。相比鏈接法解決沖突，探查法刪除一個 key 的操作稍微復(fù)雜。
 1.從未使用 HashMap.UNUSED。此槽沒有被使用和沖突過，查找時只要找到 UNUSED 就不用再繼續(xù)探查了
 2.使用過但是 remove 了，此時是 HashMap.EMPTY，該探查點后邊的元素仍然可能是有key的，需要繼續(xù)查找
 3.槽正在使用 Slot 節(jié)點
 """

 def __init__(self, key, value):
  self.key, self.value = key, value


class HashTable(object):
 UNUSED = None # 沒被使用過
 EMPTY = Slot(None, None) # 使用卻被刪除過

 def __init__(self):
  self._table = Array(8, init=HashTable.UNUSED) # 保持 2*i 次方
  self.length = 0

 @property
 def _load_factor(self):
  # load_factor 超過 0.8 重新分配
  return self.length / float(len(self._table))

 def __len__(self):
  return self.length

 # 進行哈希
 def _hash(self, key):
  return abs(hash(key)) % len(self._table)

 # 查找key
 def _find_key(self, key):
  """
  解釋一個 slot 為 UNUSED 和 EMPTY 的區(qū)別
  因為使用的是二次探查的方式，假如有兩個元素 A，B 沖突了，
  首先A hash 得到是 slot 下標(biāo)5，A 放到了第5個槽，之后插入 B 因為沖突了，所以繼續(xù)根據(jù)二次探查方式放到了 slot下標(biāo)8。
  然后刪除 A，槽 5 被置為 EMPTY。然后我去查找 B，
  第一次 hash 得到的是 槽5，但是這個時候我還是需要第二次計算 hash 才能找到 B。
  但是如果槽是 UNUSED 我就不用繼續(xù)找了，我認(rèn)為 B 就是不存在的元素。這個就是 UNUSED 和 EMPTY 的區(qū)別。
  """
  origin_index = index = self._hash(key) # origin_index 判斷是否又走到了起點，如果查找一圈了都找不到則無此元素
  _len = len(self._table)
  while self._table[index] is not HashTable.UNUSED:
   if self._table[index] is HashTable.EMPTY: # 注意如果是 EMPTY，繼續(xù)尋找下一個槽
    index = (index * 5 + 1) % _len
    if index == origin_index:
     break
    continue
   if self._table[index].key == key: # 找到了key
    return index
   else:
    index = (index * 5 + 1) % _len # 沒有找到繼續(xù)找下一個位置
    if index == origin_index:
     break

  return None

 # 找能插入的槽
 def _find_slot_for_insert(self, key):
  index = self._hash(key)
  _len = len(self._table)
  while not self._slot_can_insert(index): # 直到找到一個可以用的槽
   index = (index * 5 + 1) % _len
  return index

 # 槽是否能插入
 def _slot_can_insert(self, index):
  return self._table[index] is HashTable.EMPTY or self._table[index] is HashTable.UNUSED

 # in operator，實現(xiàn)之后可以使用 in 操作符判斷
 def __contains__(self, key):
  index = self._find_key(key)
  return index is not None

 # 添加元素
 def add(self, key, value):
  if key in self: # update
   index = self._find_key(key)
   self._table[index].value = value
   return False
  else:
   index = self._find_slot_for_insert(key)
   self._table[index] = Slot(key, value)
   self.length += 1
   if self._load_factor >= 0.8:
    self._rehash()
   return True

 # 槽不夠時，重哈希
 def _rehash(self):
  old_table = self._table
  newsize = len(self._table) * 2
  self._table = Array(newsize, HashTable.UNUSED)

  self.length = 0

  for slot in old_table:
   if slot is not HashTable.UNUSED and slot is not HashTable.EMPTY:
    index = self._find_slot_for_insert(slot.key)
    self._table[index] = slot
    self.length += 1

 # 獲取值
 def get(self, key, default=None):
  index = self._find_key(key)
  if index is None:
   return default
  else:
   return self._table[index].value

 # 移除
 def remove(self, key):
  index = self._find_key(key)
  if index is None:
   raise KeyError()
  value = self._table[index].value
  self.length -= 1
  self._table[index] = HashTable.EMPTY
  return value

 # 遍歷
 def __iter__(self):
  for slot in self._table:
   if slot not in (HashTable.EMPTY, HashTable.UNUSED):
    yield slot.key


class DictADT(HashTable):
 # 執(zhí)行dict[key]=value時執(zhí)行
 def __setitem__(self, key, value):
  self.add(key, value)

 # 執(zhí)行dict[key]時執(zhí)行
 def __getitem__(self, key, default=None):
  if key not in self:
   raise KeyError()
  return self.get(key, default)

 # 遍歷時執(zhí)行
 def _iter_slot(self):
  for slot in self._table:
   if slot not in (self.UNUSED, self.EMPTY):
    yield slot

 # 實現(xiàn)items方法
 def items(self):
  for slot in self._iter_slot():
   yield (slot.key, slot.value)

 # 實現(xiàn)keys方法
 def keys(self):
  for slot in self._iter_slot():
   yield slot.key

 # 實現(xiàn)values方法
 def values(self):
  for slot in self._iter_slot():
   yield slot.value

字典的使用

d = DictADT()
d['a'] = 1
print(d['a']) # 1

集合

集合是一種不包含重復(fù)元素的數(shù)據(jù)結(jié)構(gòu)，經(jīng)常用來判斷是否重復(fù)這種操作，或者集合中是否存在一個元素。

集合可能最常用的就是去重，判斷是否存在一個元素等，但是 set 相比 dict 有更豐富的操作，主要是數(shù)學(xué)概念上的。

如果你學(xué)過《離散數(shù)學(xué)》中集合相關(guān)的概念，基本上是一致的。 python 的 set 提供了如下基本的集合操作， 假設(shè)有兩個集合 A，B，有以下操作

  • 交集: A & B，表示同時在 A 和 B 中的元素。 python 中重載 __and__ 實現(xiàn)
  • 并集: A | B，表示在 A 或者 B 中的元素，兩個集合相加。python 中重載 __or__ 實現(xiàn)
  • 差集: A - B，表示在 A 中但是不在 B 中的元素。 python 中重載 __sub__ 實現(xiàn)

基于哈希表實現(xiàn)集合

class Array(object):

  def __init__(self, size=32, init=None):
    self._size = size
    self._items = [init] * size

  def __getitem__(self, index):
    return self._items[index]

  def __setitem__(self, index, value):
    self._items[index] = value

  def __len__(self):
    return self._size

  def clear(self, value=None):
    for i in range(len(self._items)):
      self._items[i] = value

  def __iter__(self):
    for item in self._items:
      yield item


class Slot(object):
  """
  定義一個 hash 表數(shù)組的槽(slot 這里指的就是數(shù)組的一個位置)
  hash table 就是一個數(shù)組，每個數(shù)組的元素（也叫slot槽）是一個對象，對象包含兩個屬性 key 和 value。

  注意，一個槽有三種狀態(tài)，看你能否想明白。相比鏈接法解決沖突，探查法刪除一個 key 的操作稍微復(fù)雜。
  1.從未使用 HashMap.UNUSED。此槽沒有被使用和沖突過，查找時只要找到 UNUSED 就不用再繼續(xù)探查了
  2.使用過但是 remove 了，此時是 HashMap.EMPTY，該探查點后邊的元素仍然可能是有key的，需要繼續(xù)查找
  3.槽正在使用 Slot 節(jié)點
  """

  def __init__(self, key, value):
    self.key, self.value = key, value


class HashTable(object):
  UNUSED = None # 沒被使用過
  EMPTY = Slot(None, None) # 使用卻被刪除過

  def __init__(self):
    self._table = Array(8, init=HashTable.UNUSED) # 保持 2*i 次方
    self.length = 0

  @property
  def _load_factor(self):
    # load_factor 超過 0.8 重新分配
    return self.length / float(len(self._table))

  def __len__(self):
    return self.length

  # 進行哈希
  def _hash(self, key):
    return abs(hash(key)) % len(self._table)

  # 查找key
  def _find_key(self, key):
    """
    解釋一個 slot 為 UNUSED 和 EMPTY 的區(qū)別
    因為使用的是二次探查的方式，假如有兩個元素 A，B 沖突了，
    首先A hash 得到是 slot 下標(biāo)5，A 放到了第5個槽，之后插入 B 因為沖突了，所以繼續(xù)根據(jù)二次探查方式放到了 slot下標(biāo)8。
    然后刪除 A，槽 5 被置為 EMPTY。然后我去查找 B，
    第一次 hash 得到的是 槽5，但是這個時候我還是需要第二次計算 hash 才能找到 B。
    但是如果槽是 UNUSED 我就不用繼續(xù)找了，我認(rèn)為 B 就是不存在的元素。這個就是 UNUSED 和 EMPTY 的區(qū)別。
    """
    origin_index = index = self._hash(key) # origin_index 判斷是否又走到了起點，如果查找一圈了都找不到則無此元素
    _len = len(self._table)
    while self._table[index] is not HashTable.UNUSED:
      if self._table[index] is HashTable.EMPTY: # 注意如果是 EMPTY，繼續(xù)尋找下一個槽
        index = (index * 5 + 1) % _len
        if index == origin_index:
          break
        continue
      if self._table[index].key == key: # 找到了key
        return index
      else:
        index = (index * 5 + 1) % _len # 沒有找到繼續(xù)找下一個位置
        if index == origin_index:
          break

    return None

  # 找能插入的槽
  def _find_slot_for_insert(self, key):
    index = self._hash(key)
    _len = len(self._table)
    while not self._slot_can_insert(index): # 直到找到一個可以用的槽
      index = (index * 5 + 1) % _len
    return index

  # 槽是否能插入
  def _slot_can_insert(self, index):
    return self._table[index] is HashTable.EMPTY or self._table[index] is HashTable.UNUSED

  # in operator，實現(xiàn)之后可以使用 in 操作符判斷
  def __contains__(self, key):
    index = self._find_key(key)
    return index is not None

  # 添加元素
  def add(self, key, value):
    if key in self: # update
      index = self._find_key(key)
      self._table[index].value = value
      return False
    else:
      index = self._find_slot_for_insert(key)
      self._table[index] = Slot(key, value)
      self.length += 1
      if self._load_factor >= 0.8:
        self._rehash()
      return True

  # 槽不夠時，重哈希
  def _rehash(self):
    old_table = self._table
    newsize = len(self._table) * 2
    self._table = Array(newsize, HashTable.UNUSED)

    self.length = 0

    for slot in old_table:
      if slot is not HashTable.UNUSED and slot is not HashTable.EMPTY:
        index = self._find_slot_for_insert(slot.key)
        self._table[index] = slot
        self.length += 1

  # 獲取值
  def get(self, key, default=None):
    index = self._find_key(key)
    if index is None:
      return default
    else:
      return self._table[index].value

  # 移除
  def remove(self, key):
    index = self._find_key(key)
    if index is None:
      raise KeyError()
    value = self._table[index].value
    self.length -= 1
    self._table[index] = HashTable.EMPTY
    return value

  # 遍歷
  def __iter__(self):
    for slot in self._table:
      if slot not in (HashTable.EMPTY, HashTable.UNUSED):
        yield slot.key


class SetADT(HashTable):
  # 添加元素
  def add(self, key):
    super().add(key, True)
  
  def __and__(self, other_set):
    """交集 A&B"""
    new_set = SetADT()
    for element_a in self:
      if element_a in other_set:
        new_set.add(element_a)
    return new_set

  def __sub__(self, other_set):
    """差集 A-B"""
    new_set = SetADT()
    for element_a in self:
      if element_a not in other_set:
        new_set.add(element_a)
    return new_set

  def __or__(self, other_set):
    """并集 A|B"""
    new_set = SetADT()
    for element_a in self:
      new_set.add(element_a)
    for element_b in other_set:
      new_set.add(element_b)
    return new_set

集合的使用

sa = SetADT()
sa.add(1)
sa.add(2)
sa.add(3)

sb = SetADT()
sb.add(3)
sb.add(4)
sb.add(5)

print(sorted(list(sa & sb))) # [3]
print(sorted(list(sa - sb))) # [1, 2]
print(sorted(list(sa | sb))) # [1, 2, 3, 4, 5]

總結(jié)

以上所述是小編給大家介紹的使用python實現(xiàn)哈希表、字典、集合操作，希望對大家有所幫助！

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手