Implementing set() using Hash Tables
Main reference: here.
The wikipedia entry is also great.
Super basic implementation of Set()
; we only have one hash table where the keys are the values. Collision resolution is handled through open addressing (basically we rehash the key until we get an empty slot in the bucket).
class HashTable: def __init__(self): self.size = 11 self.slots = [None] * self.size def hash(self, key, size): return key % size def reHash(self, old_hash, size): return (old_hash+1) % size def add(self, key): hash_value = self.hash(key, self.size) # if the key is already there, do nothing if self.slots[hash_value] == key: return # add key elif self.slots[hash_value] is None: self.slots[hash_value] = key # reash until it finds an empty slot or the same key else: next_slot = self.reHash(hash_value, len(self.slots)) while self.slots[next_slot] is not None and \ self.slots[next_slot] != key: next_slot = self.reHash(next_slot, len(self.slots)) # got an empty slot, use it if self.slots[next_slot] is None: self.slots[next_slot] = key # got the same key, do nothing else: return def remove(self, key): hash_value = self.hash(key, self.size) if self.slots[hash_value] == key: self.slots[hash_value] = None else: # rehash while self.slots[hash_value] != key: hash_value = self.reHash(hash_value, self.size) if self.slots[hash_value] is None: return # key found, delete it self.slots[hash_value] = None def __repr__(self): v = [x for x in self.slots if x is not None] return str(v) myset = HashTable() myset.add(99) myset.add(4) myset.add(55) myset.add(55) print myset myset.remove(55) print myset