使用python實(shí)現(xiàn)哈希表、字典、集合操作
哈希表
哈希表(Hash Table, 又稱為散列表),是一種線性表的存儲(chǔ)結(jié)構(gòu)。哈希表由一個(gè)直接尋址表和一個(gè)哈希函數(shù)組成。哈希函數(shù)h(k)將元素關(guān)鍵字k作為自變量,返回元素的存儲(chǔ)下標(biāo)。
簡單哈希函數(shù):
除法哈希:h(k) = k mod m乘法哈希:h(k) = floor(m(kA mod 1)) 0<A<1
假設(shè)有一個(gè)長度為7的數(shù)組,哈希函數(shù)h(k) = k mod 7,元素集合{14, 22, 3, 5}的存儲(chǔ)方式如下圖:
哈希沖突
由于哈希表的大小是有限的,而要存儲(chǔ)的值的總數(shù)量是無限的,因此對(duì)于任何哈希函數(shù),都會(huì)出現(xiàn)兩個(gè)不同的元素映射到同一個(gè)位置上的情況,這種情況叫做哈希沖突。
比如:h(k) = k mod 7, h(0) = h(7) = h(14) = ...
解決哈希沖突--開放尋址法
開放尋址法:如果哈希函數(shù)返回的位置已經(jīng)有值,則可以向后探查新的位置來存儲(chǔ)這個(gè)值
線性探查:如果位置i被占用,則探查i+1, i+2,...二次探查:如果位置i被占用,則探查i+12, i-12, i+22, i-22,...二度哈希:有n個(gè)哈希函數(shù),當(dāng)使用第一個(gè)哈希函數(shù)h1發(fā)生沖突時(shí),則嘗試使用h2, h3,...
解決哈希沖突--拉鏈法
拉鏈法:哈希表每一個(gè)位置都連接一個(gè)鏈表,當(dāng)沖突發(fā)生時(shí),沖突的元素將被加到該位置鏈表的最后。
哈希表的實(shí)現(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): """ 定義一個(gè) hash 表數(shù)組的槽(slot 這里指的就是數(shù)組的一個(gè)位置) hash table 就是一個(gè)數(shù)組,每個(gè)數(shù)組的元素(也叫slot槽)是一個(gè)對(duì)象,對(duì)象包含兩個(gè)屬性 key 和 value。 注意,一個(gè)槽有三種狀態(tài),看你能否想明白。相比鏈接法解決沖突,探查法刪除一個(gè) key 的操作稍微復(fù)雜。 1.從未使用 HashMap.UNUSED。此槽沒有被使用和沖突過,查找時(shí)只要找到 UNUSED 就不用再繼續(xù)探查了 2.使用過但是 remove 了,此時(shí)是 HashMap.EMPTY,該探查點(diǎn)后邊的元素仍然可能是有key的,需要繼續(xù)查找 3.槽正在使用 Slot 節(jié)點(diǎn) """ 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 # 進(jìn)行哈希 def _hash(self, key): return abs(hash(key)) % len(self._table) # 查找key def _find_key(self, key): """ 解釋一個(gè) slot 為 UNUSED 和 EMPTY 的區(qū)別 因?yàn)槭褂玫氖嵌翁讲榈姆绞?,假如有兩個(gè)元素 A,B 沖突了, 首先A hash 得到是 slot 下標(biāo)5,A 放到了第5個(gè)槽,之后插入 B 因?yàn)闆_突了,所以繼續(xù)根據(jù)二次探查方式放到了 slot下標(biāo)8。 然后刪除 A,槽 5 被置為 EMPTY。然后我去查找 B, 第一次 hash 得到的是 槽5,但是這個(gè)時(shí)候我還是需要第二次計(jì)算 hash 才能找到 B。 但是如果槽是 UNUSED 我就不用繼續(xù)找了,我認(rèn)為 B 就是不存在的元素。這個(gè)就是 UNUSED 和 EMPTY 的區(qū)別。 """ origin_index = index = self._hash(key) # origin_index 判斷是否又走到了起點(diǎn),如果查找一圈了都找不到則無此元素 _len = len(self._table) while self._table[index] is not HashTable.UNUSED: if self._table[index] is HashTable.EMPTY: # 注意如果是 EMPTY,繼續(xù)尋找下一個(gè)槽 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ù)找下一個(gè)位置 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): # 直到找到一個(gè)可以用的槽 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,實(shí)現(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 # 槽不夠時(shí),重哈希 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停铱纱鎯?chǔ)任意類型對(duì)象。
字典的每個(gè)鍵值key=>value對(duì)用冒號(hào):分割,每個(gè)鍵值對(duì)之間用逗號(hào),分割,整個(gè)字典包括在花括號(hào){}中 ,格式如下所示:
d = {key1 : value1, key2 : value2 }
基于哈希表實(shí)現(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): """ 定義一個(gè) hash 表數(shù)組的槽(slot 這里指的就是數(shù)組的一個(gè)位置) hash table 就是一個(gè)數(shù)組,每個(gè)數(shù)組的元素(也叫slot槽)是一個(gè)對(duì)象,對(duì)象包含兩個(gè)屬性 key 和 value。 注意,一個(gè)槽有三種狀態(tài),看你能否想明白。相比鏈接法解決沖突,探查法刪除一個(gè) key 的操作稍微復(fù)雜。 1.從未使用 HashMap.UNUSED。此槽沒有被使用和沖突過,查找時(shí)只要找到 UNUSED 就不用再繼續(xù)探查了 2.使用過但是 remove 了,此時(shí)是 HashMap.EMPTY,該探查點(diǎn)后邊的元素仍然可能是有key的,需要繼續(xù)查找 3.槽正在使用 Slot 節(jié)點(diǎn) """ 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 # 進(jìn)行哈希 def _hash(self, key): return abs(hash(key)) % len(self._table) # 查找key def _find_key(self, key): """ 解釋一個(gè) slot 為 UNUSED 和 EMPTY 的區(qū)別 因?yàn)槭褂玫氖嵌翁讲榈姆绞?,假如有兩個(gè)元素 A,B 沖突了, 首先A hash 得到是 slot 下標(biāo)5,A 放到了第5個(gè)槽,之后插入 B 因?yàn)闆_突了,所以繼續(xù)根據(jù)二次探查方式放到了 slot下標(biāo)8。 然后刪除 A,槽 5 被置為 EMPTY。然后我去查找 B, 第一次 hash 得到的是 槽5,但是這個(gè)時(shí)候我還是需要第二次計(jì)算 hash 才能找到 B。 但是如果槽是 UNUSED 我就不用繼續(xù)找了,我認(rèn)為 B 就是不存在的元素。這個(gè)就是 UNUSED 和 EMPTY 的區(qū)別。 """ origin_index = index = self._hash(key) # origin_index 判斷是否又走到了起點(diǎn),如果查找一圈了都找不到則無此元素 _len = len(self._table) while self._table[index] is not HashTable.UNUSED: if self._table[index] is HashTable.EMPTY: # 注意如果是 EMPTY,繼續(xù)尋找下一個(gè)槽 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ù)找下一個(gè)位置 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): # 直到找到一個(gè)可以用的槽 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,實(shí)現(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 # 槽不夠時(shí),重哈希 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時(shí)執(zhí)行 def __setitem__(self, key, value): self.add(key, value) # 執(zhí)行dict[key]時(shí)執(zhí)行 def __getitem__(self, key, default=None): if key not in self: raise KeyError() return self.get(key, default) # 遍歷時(shí)執(zhí)行 def _iter_slot(self): for slot in self._table: if slot not in (self.UNUSED, self.EMPTY): yield slot # 實(shí)現(xiàn)items方法 def items(self): for slot in self._iter_slot(): yield (slot.key, slot.value) # 實(shí)現(xiàn)keys方法 def keys(self): for slot in self._iter_slot(): yield slot.key # 實(shí)現(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ù)這種操作,或者集合中是否存在一個(gè)元素。
集合可能最常用的就是去重,判斷是否存在一個(gè)元素等,但是 set 相比 dict 有更豐富的操作,主要是數(shù)學(xué)概念上的。
如果你學(xué)過《離散數(shù)學(xué)》中集合相關(guān)的概念,基本上是一致的。 python 的 set 提供了如下基本的集合操作, 假設(shè)有兩個(gè)集合 A,B,有以下操作
- 交集: A & B,表示同時(shí)在 A 和 B 中的元素。 python 中重載 __and__ 實(shí)現(xiàn)
- 并集: A | B,表示在 A 或者 B 中的元素,兩個(gè)集合相加。python 中重載 __or__ 實(shí)現(xiàn)
- 差集: A - B,表示在 A 中但是不在 B 中的元素。 python 中重載 __sub__ 實(shí)現(xiàn)
基于哈希表實(shí)現(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): """ 定義一個(gè) hash 表數(shù)組的槽(slot 這里指的就是數(shù)組的一個(gè)位置) hash table 就是一個(gè)數(shù)組,每個(gè)數(shù)組的元素(也叫slot槽)是一個(gè)對(duì)象,對(duì)象包含兩個(gè)屬性 key 和 value。 注意,一個(gè)槽有三種狀態(tài),看你能否想明白。相比鏈接法解決沖突,探查法刪除一個(gè) key 的操作稍微復(fù)雜。 1.從未使用 HashMap.UNUSED。此槽沒有被使用和沖突過,查找時(shí)只要找到 UNUSED 就不用再繼續(xù)探查了 2.使用過但是 remove 了,此時(shí)是 HashMap.EMPTY,該探查點(diǎn)后邊的元素仍然可能是有key的,需要繼續(xù)查找 3.槽正在使用 Slot 節(jié)點(diǎn) """ 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 # 進(jìn)行哈希 def _hash(self, key): return abs(hash(key)) % len(self._table) # 查找key def _find_key(self, key): """ 解釋一個(gè) slot 為 UNUSED 和 EMPTY 的區(qū)別 因?yàn)槭褂玫氖嵌翁讲榈姆绞?,假如有兩個(gè)元素 A,B 沖突了, 首先A hash 得到是 slot 下標(biāo)5,A 放到了第5個(gè)槽,之后插入 B 因?yàn)闆_突了,所以繼續(xù)根據(jù)二次探查方式放到了 slot下標(biāo)8。 然后刪除 A,槽 5 被置為 EMPTY。然后我去查找 B, 第一次 hash 得到的是 槽5,但是這個(gè)時(shí)候我還是需要第二次計(jì)算 hash 才能找到 B。 但是如果槽是 UNUSED 我就不用繼續(xù)找了,我認(rèn)為 B 就是不存在的元素。這個(gè)就是 UNUSED 和 EMPTY 的區(qū)別。 """ origin_index = index = self._hash(key) # origin_index 判斷是否又走到了起點(diǎn),如果查找一圈了都找不到則無此元素 _len = len(self._table) while self._table[index] is not HashTable.UNUSED: if self._table[index] is HashTable.EMPTY: # 注意如果是 EMPTY,繼續(xù)尋找下一個(gè)槽 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ù)找下一個(gè)位置 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): # 直到找到一個(gè)可以用的槽 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,實(shí)現(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 # 槽不夠時(shí),重哈希 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實(shí)現(xiàn)哈希表、字典、集合操作,希望對(duì)大家有所幫助!
相關(guān)文章
Python?sklearn庫三種常用編碼格式實(shí)例
這篇文章主要為大家介紹了Python?sklearn庫三種常用編碼格式實(shí)例展示,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-09-09教你如何用一行Python代碼實(shí)現(xiàn)GUI圖形界面
GUI(圖形用戶界面),顧名思義就是用圖形的方式,來顯示計(jì)算機(jī)操作的界面,更加方便且直觀。本文將用一行代碼實(shí)現(xiàn)GUI界面的制作,需要的可以參考一下2022-05-05Python實(shí)現(xiàn)在tkinter中使用matplotlib繪制圖形的方法示例
這篇文章主要介紹了Python實(shí)現(xiàn)在tkinter中使用matplotlib繪制圖形的方法,結(jié)合實(shí)例形式分析了Python使用tkinter與matplotlib進(jìn)行正弦曲線圖形繪制的相關(guān)操作技巧,需要的朋友可以參考下2018-01-01