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):
 """定義一個(gè) hash 表 數(shù)組的槽
 注意，一個(gè)槽有三種狀態(tài)，看你能否想明白
 1.從未使用 HashMap.UNUSED。此槽沒有被使用和沖突過，查找時(shí)只要找到 UNUSED 就不用再繼續(xù)探查了
 2.使用過但是 remove 了，此時(shí)是 HashMap.EMPTY，該探查點(diǎn)后邊的元素扔可能是有key
 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)
  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è)槽不是未使用過的，才接著往下找；如果是未使用過的，這個(gè)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

 # 檢測(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.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