Python 实现集合Set的示例

Python的集合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的资料请关注易采站长站其它相关文章！