Python 實現集合Set的示例
Python的集合set原理
集合(set)是一個無序的不重復元素序列。
可以使用大括號 { } 或者 set() 函數創建集合,註意:創建一個空集合必須用 set() 而不是 { },因為 { } 是用來創建一個空字典。
class Array(object): def __init__(self, size=32, init=None): self._size = size self._items = [init] * self._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 表 數組的槽 註意,一個槽有三種狀態,看你能否想明白 1.從未使用 HashMap.UNUSED。此槽沒有被使用和沖突過,查找時隻要找到 UNUSED 就不用再繼續探查瞭 2.使用過但是 remove 瞭,此時是 HashMap.EMPTY,該探查點後邊的元素扔可能是有key 3.槽正在使用 Slot 節點 """ 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) self.length = 0 # 負載因子 @property def _load_factor(self): return self.length/float(len(self._table)) def __len__(self): return self.length # 哈希函數 用內置的哈希哈數進行哈希一下,然後對數組長度取模 def _hash(self, key): return abs(hash(key)) % len(self._table) def _find_key(self, key): # 得到第一個值的位置 index = self._hash(key) _len = len(self._table) # 當這個槽不是未使用過的,才接著往下找;如果是未使用過的,這個key肯定不存在 while self._table[index] is not HashTable.UNUSED: # 槽使用過,但是被刪除瞭 if self._table[index] is HashTable.EMPTY: # cpython解決哈希沖突的一種方式 index = (index*5 + 1) % _len continue elif self._table[index] == key: return index else: index = (index * 5 + 1) % _len return None # 檢測槽是否能被插入 def _slot_can_insert(self, index): return (self._table[index] is HashTable.EMPTY or self._table[index] is HashTable.UNUSED) # 找到能被插入的槽的index def _find_slot_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 # in 操作符 def __contains__(self, key): index = self._find_key(key) return index is not None def add(self, key, value): if key in self: index = self._find_key(key) # 更新值 self._table[index].value = value return False else: index = self._find_slot_insert(key) self._table[index] = Slot(key, value) self.length += 1 if self._load_factor > 0.8: return self._rehash() return True def _rehash(self): oldtable = self._table newsize = len(self._table) * 2 # 新的table self._table = Array(newsize, HashTable.UNUSED) self.length = 0 for slot in oldtable: if slot is not HashTable.UNUSED and slot is not HashTable.EMPTY: index = self._find_slot_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.UNUSED, HashTable.EMPTY): yield slot.value class SetADT(HashTable): def add(self, key): return super(SetADT, self).add(key, True) def __and__(self, other_set): # 求交集 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): # 求差集 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): # 求交集 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
以上就是Python 實現集合Set的示例的詳細內容,更多關於Python 實現集合Set的資料請關註WalkonNet其它相關文章!
推薦閱讀:
- HashMap底層實現原理詳解
- C++深入探究哈希表如何封裝出unordered_set和unordered_map
- C語言數據結構哈希表詳解
- PHP數組的內部實現你瞭解嗎
- Java1.7全網最深入HashMap源碼解析