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的资料请关注www.887551.com其它相关文章！