Python的集合set原理

集合（set）是一個(gè)無(wú)序的不重復(fù)元素序列。

可以使用大括號(hào) { } 或者 set() 函數(shù)創(chuàng)建集合，注意：創(chuàng)建一個(gè)空集合必須用 set() 而不是 { }，因?yàn)?{ } 是用來(lái)創(chuàng)建一個(gè)空字典。

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): '''定義一個(gè) hash 表 數(shù)組的槽 注意，一個(gè)槽有三種狀態(tài)，看你能否想明白 1.從未使用 HashMap.UNUSED。此槽沒(méi)有被使用和沖突過(guò)，查找時(shí)只要找到 UNUSED 就不用再繼續(xù)探查了 2.使用過(guò)但是 remove 了，此時(shí)是 HashMap.EMPTY，該探查點(diǎn)后邊的元素扔可能是有key 3.槽正在使用 Slot 節(jié)點(diǎn) ''' def __init__(self, key, value): self.key, self.value = key, valueclass HashTable(object): # 表示從未被使用過(guò) UNUSED = None # 使用過(guò)，但是被刪除了 EMPTY = Slot(None, None) def __init__(self): self._table = Array(8, init=HashTable.UNUSED) self.length = 0 # 負(fù)載因子 @property def _load_factor(self): return self.length/float(len(self._table)) def __len__(self): return self.length # 哈希函數(shù) 用內(nèi)置的哈希哈數(shù)進(jìn)行哈希一下，然后對(duì)數(shù)組長(zhǎng)度取模 def _hash(self, key): return abs(hash(key)) % len(self._table) def _find_key(self, key): # 得到第一個(gè)值的位置 index = self._hash(key) _len = len(self._table) # 當(dāng)這個(gè)槽不是未使用過(guò)的，才接著往下找；如果是未使用過(guò)的，這個(gè)key肯定不存在 while self._table[index] is not HashTable.UNUSED: # 槽使用過(guò)，但是被刪除了 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 # 檢測(cè)槽是否能被插入 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): # 得到第一個(gè)值的位置 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 # 把槽設(shè)置為空槽 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 實(shí)現(xiàn)集合Set的示例的詳細(xì)內(nèi)容，更多關(guān)于Python 實(shí)現(xiàn)集合Set的資料請(qǐng)關(guān)注好吧啦網(wǎng)其它相關(guān)文章！