Example of Python Implementation Collection Set

Sets of Python set Principle

A set (set) is an unordered sequence of non-repeating elements.

You can use curly braces {} or the set () function to create collections. Note: To create an empty collection, you must use set () instead of {}, because {} is used to create an empty dictionary.

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):
 """ Definition 1 A  hash  Table   The slot of an array 
  Attention, 1 There are three slots 3 This kind of state, see if you can understand it 
 1. Never used  HashMap.UNUSED . This slot has not been used or conflicted. When searching, just find it  UNUSED  You don't have to continue probing 
 2. Used but  remove  Now, at this time, it is  HashMap.EMPTY The element thrown behind the probe point may have key
 3. The slot is in use  Slot  Node 
 """
 def __init__(self, key, value):
  self.key, self.value = key, value

class HashTable(object):
 #  Indicates that it has never been used 
 UNUSED = None
 #  Used, but deleted 
 EMPTY = Slot(None, None)

 def __init__(self):
  self._table = Array(8, init=HashTable.UNUSED)
  self.length = 0

 #  Load factor 
 @property
 def _load_factor(self):
  return self.length/float(len(self._table))

 def __len__(self):
  return self.length

 #  Hash function   Hash with built-in hash hash number 1 Next, and then take the module of the array length 
 def _hash(self, key):
  return abs(hash(key)) % len(self._table)

 def _find_key(self, key):
  #  Get the first 1 Position of values 
  index = self._hash(key)
  _len = len(self._table)
  #  When this slot is not unused, then look down; If it is unused, this key It definitely doesn't exist 
  while self._table[index] is not HashTable.UNUSED:
   #  The slot was used, but it was deleted 
   if self._table[index] is HashTable.EMPTY:
    # cpython That resolves hash conflicts 1 A kind of way 
    index = (index*5 + 1) % _len
    continue
   elif self._table[index] == key:
    return index
   else:
    index = (index * 5 + 1) % _len
  return None

 #  Detect whether the slot can be inserted 
 def _slot_can_insert(self, index):
  return (self._table[index] is HashTable.EMPTY or self._table[index] is HashTable.UNUSED)

 #  Find a slot that can be inserted index
 def _find_slot_insert(self, key):
  #  Get the first 1 Position of values 
  index = self._hash(key)
  _len = len(self._table)
  while not self._slot_can_insert(index):
   index = (index * 5 + 1) % _len
  return index

 # in  Operator 
 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)
   #  Update value 
   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
  #  New 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
  #  Set the slot as an empty slot 
  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):
  #  Find intersection 
  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):
  #  Difference 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):
  #  Find intersection 
  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

The above is the Python implementation set Set example details, more about Python implementation set Set information please pay attention to other related articles on this site!