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 itemclass Slot(object): '''定義一個 hash 表 數組的槽 注意，一個槽有三種狀態，看你能否想明白 1.從未使用 HashMap.UNUSED。此槽沒有被使用和沖突過，查找時只要找到 UNUSED 就不用再繼續探查了 2.使用過但是 remove 了，此時是 HashMap.EMPTY，該探查點后邊的元素扔可能是有key 3.槽正在使用 Slot 節點 ''' def __init__(self, key, value): self.key, self.value = key, valueclass 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.valueclass 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的資料請關注好吧啦網其它相關文章！