欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Python 实现集合Set的示例

程序员文章站 2022-07-03 19:11:36
python的集合set原理集合(set)是一个无序的不重复元素序列。可以使用大括号 { } 或者 set() 函数创建集合,注意:创建一个空集合必须用 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的资料请关注其它相关文章!

相关标签: python 集合 set