Implementing set() using Hash Tables

07.04.2015

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).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
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       
|