GkQ4XyBM

1#!/usr/bin/env python3
2# This code implements a hash table (for an exercise)
3# This hash table DOES NOT use a linked list to handle collisions
4
5class HashTable:
6    def __init__(self):
7        self.size = 11
8        self.slots = [None] * self.size
9        self.data = [None] * self.size
10
11    # create a hash function that returns an indice given a specific key and size of hash table
12    def hashfunction(self, key, size):
13        return key % size
14
15    # rehashes a value if collision occurs
16    def rehash(self, oldhash, size):
17        return (oldhash+1)%size
18
19    # add a key and value to the hash table
20    def put(self, key, value):
21        hashvalue = self.hashfunction(key, len(self.slots))
22
23        if self.slots[hashvalue] == None:
24            self.slots[hashvalue] = key
25            self.data[hashvalue] = value
26        else:
27            # add value to hash table if key exists but
28            if self.slots[hashvalue] == key:
29                self.data[hashvalue] = value
30            else:
31                nextslot = self.rehash(hashvalue, len(self.slots))
32
33                # move to next slot in hash table until a free slot opens up
34                while self.slots[nextslot] != None and self.slots[nextslot] != key:
35                    nextslot = self.rehash(nextslot, len(self.slots))
36
37                # add key and value
38                if self.slots[nextslot] == None:
39                    self.slots[nextslot] = key
40                    self.data[nextslot] = value
41                else:
42                    self.data[nextslot] = value
43
44    # return the value from a hash table given a key
45    def get(self, key):
46        startslot = self.hashfunction(key, len(self.slots))
47        value = None
48        found = False
49        stop = False
50        position = startslot
51
52        # iterate through hash table until key is found
53        while self.slots[position] != None and not found and not stop:
54            if self.slots[position] == key:
55                value = self.data[position]
56                found = True
57            else:
58                position = self.rehash(position, len(self.slots))
59                # catch if the entire hash table has been searched
60                if position == startslot:
61                    stop = True
62        return value
63
64    # replace Python's built-in method of retrieving a value "hashtable.get(key)" with our own get() method
65    def __getitem__(self, key):
66        return self.get(key)
67
68    # replace Python's built-in method of adding key-value pairs to a hash table "hashtable[key] = value" with our own method
69    def __setitem__(self, key, value):
70        self.put(key, value)
71
72# Create the hash table
73H = HashTable()
74H[54]="cat"
75H[26]="dog"
76H[93]="lion"
77H[17]="tiger"
78H[77]="bird"
79H[31]="cow"
80H[44]="goat"
81H[55]="pig"
82H[20]="chicken"
83
84# checks
85print(H.slots)
86print(H.data)
87print(H[20])
88print(H[17])
89H[20]='duck'
90print(H[20])
91print(H[99])