Today I built a hash table. A hash table stores information so you can get it back instantly by putting in a word. The word is called the key and what you get back is the value.
I had 10 boxes, numbered 0 to 9. The big question was how to turn a word into a box number.
My first idea was to count the letters. But then “cat”, “dog”, “sun” and every 3-letter word would go in box 3. My next idea was the first letter, but then “pen”, “pig” and “pizza” would crowd together.
So I added up all the letters instead. Python has ord, which turns a letter into its secret number. I found out t is 116, so I worked backwards and predicted a would be 97. I was right!
c + a + t = 99 + 97 + 116 = 312.
But 312 is way more than 10 boxes. At first I wanted to make the boxes bigger, but then I used the remainder. 312 ÷ 10 is 31 remainder 2, so “cat” goes in box 2. In Python the remainder is %.
Then I tried “act”. It also went in box 2, because it has the same letters, and adding doesn’t care about order. Two keys in one box is called a collision.
My fix was to put a linked list in every box. That’s called chaining. Each node remembers a key, a value, and next.
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
class HashTable:
def __init__(self):
self.array = [None] * 10
def hash(self, key):
total = 0
for letter in key:
total = total + ord(letter)
return total % 10
def put(self, key, value):
index = self.hash(key)
new_node = Node(key, value)
if self.array[index] == None:
self.array[index] = new_node
else:
new_node.next = self.array[index]
self.array[index] = new_node
def get(self, key):
index = self.hash(key)
current = self.array[index]
while current is not None:
if current.key == key:
return current.value
current = current.next
main = HashTable()
print(main.hash("cat"))
print(main.hash("act"))
main.put("cat",123)
main.put("act",456)
print(main.get("cat"))
print(main.get("act"))
When a new word goes in a box that’s already full, I put it at the front, like insert at head. The order matters! If you move the head first, cat gets lost forever.
To get a value back, you go to the box and walk along the chain until the key matches.
My test: I put “cat” as 123 and “act” as 456. Both were in box 2, and I still got back 123 and 456.
Also, if you print something that has no return, Python prints None. That confused me at first!