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

来源：https://www.cnblogs.com/guotianbao/p/12731390.html