使用python實現(xiàn)哈希表、字典、集合操作
更新時間：2019年12月22日 15:06:51 作者：學(xué)海無涯苦作舟
這篇文章主要介紹了使用python實現(xiàn)哈希表、字典、集合操作，本文通過實例代碼給大家介紹的非常詳細，具有一定的參考借鑒價值,需要的朋友可以參考下
哈希表
哈希表（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}的存儲方式如下圖：
哈希沖突
由于哈希表的大小是有限的，而要存儲的值的總數(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ù)h1發(fā)生沖突時，則嘗試使用h2, h3,...
解決哈希沖突--拉鏈法
拉鏈法：哈希表每一個位置都連接一個鏈表，當(dāng)沖突發(fā)生時，沖突的元素將被加到該位置鏈表的最后。
哈希表的實現(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ù)找了，我認為 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 }
基于哈希表實現(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ù)找了，我認為 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ù)找了，我認為 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)哈希表、字典、集合操作，希望對大家有所幫助！
相關(guān)文章
這篇文章主要為大家介紹了Python?sklearn庫三種常用編碼格式實例展示，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-09-09
這篇文章主要介紹了python如何實現(xiàn)簡單遺傳算法，幫助大家更好的利用python進行數(shù)據(jù)分析，感興趣的朋友可以了解下2020-09-09
這篇文章主要介紹了python中opencv?Canny邊緣檢測，Canny邊緣檢測是一種使用多級邊緣檢測算法檢測邊緣的方法。OpenCV提供了函數(shù)cv2.Canny()實現(xiàn)Canny邊緣檢測。更多相關(guān)內(nèi)容需要的小伙伴可以參考下面文章內(nèi)容2022-06-06
教你如何用一行Python代碼實現(xiàn)GUI圖形界面
GUI(圖形用戶界面)，顧名思義就是用圖形的方式，來顯示計算機操作的界面，更加方便且直觀。本文將用一行代碼實現(xiàn)GUI界面的制作，需要的可以參考一下2022-05-05
Matplotlib是一個Python語言的2D繪圖庫，它支持各種平臺，并且功能強大，能夠輕易繪制出各種專業(yè)的圖像。本文是對Python 繪圖庫 Matplotlib 入門教程，感興趣的朋友跟隨腳本之家小編一起學(xué)習(xí)吧2018-04-04
這篇文章主要為大家詳細介紹了python石頭剪刀布小游，三局兩勝制，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01
這篇文章主要介紹了Python內(nèi)存管理方式和垃圾回收算法解析，介紹了傳統(tǒng)的垃圾回收機制，其工作方法，finalizer的問題等相關(guān)內(nèi)容，具有一定參考價值，需要的朋友可以了解下。2017-11-11
Python實現(xiàn)在tkinter中使用matplotlib繪制圖形的方法示例
這篇文章主要介紹了Python實現(xiàn)在tkinter中使用matplotlib繪制圖形的方法,結(jié)合實例形式分析了Python使用tkinter與matplotlib進行正弦曲線圖形繪制的相關(guān)操作技巧,需要的朋友可以參考下2018-01-01
這篇文章主要介紹了Python3邏輯運算符與成員運算符，文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的朋友可以參考一下2022-09-09
二維碼作為一種信息傳遞的工具，在當(dāng)今社會發(fā)揮了重要作用。從手機用戶登錄到手機支付，生活的各個角落都能看到二維碼的存在。下面我們就來看看Python如何生成一個優(yōu)雅的二維碼吧2022-09-09