Today I started at 5 AM. Four tasks, all done.
Hash tables are the fastest data structure for lookups. The Big-O is O(1) — constant time. That means they take the same time to find something whether you have 10 items or 10 million items. If O(log n) is Michael Phelps, O(1) is teleportation.
How is that possible? A hash function takes a key (like "apple"), does some math on it, and gives you a slot number (like 73). You jump straight to slot 73. No searching.
In Python, hash tables are called dictionaries. I have been using them for a while without knowing they were hash tables. My Morse translator from Wednesday had morse_code = {'A': '.-', 'B': '-...'} — that was a hash table.
Collisions happen when two different keys get the same slot number. The fix: store a linked list at that slot. Both values live there, connected by arrows. That is why today’s project matters so much.
The load factor = occupied slots / total slots. When it goes above 0.7, the hash table doubles in size to keep collisions low.
I built two Python files:
linked_list.py — the Node class and the LinkedList classLinkedList_main.py — a separate test file that imports from linked_list.pyThe LinkedList has these methods:
insert_at_head(data) — O(1), the fast one. Change one arrow.insert_at_end(data) — O(n), the slow one. You have to walk to the end first.traverse() — walk from head, print every node.delete(data) — walk until you find the node, re-wire the previous node’s next to skip it.search(data) — walk until found, return the position.class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_at_head(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
I had three bugs today. All three were is not None where it should have been is None, or the opposite. Flipping that one word broke everything. Reading the output carefully is how I found each one.
Final output:
--- Insert at HEAD (3, 2, 1) ---
1->2->3->None
--- Insert at END (4, 5) ---
1->2->3->4->5->None
--- Delete 3 ---
1->2->4->5->None
--- Search ---
Found 4 at position 2!
99 not found!
Now I understand what hash tables USE when they have a collision. Not just read it — built it.
The chapter imagines you and your new neighbour want to send flashlight Morse code at night, but your bedroom windows don’t face each other. The fix: skip the flashlights, use wires. One battery, one bulb, one switch per house. Close the switch, bulb lights up. Morse code through a wire.
Two separate circuits need four wires. Petzold shows a trick: join the negative sides into a common wire. Now you only need three wires.
Then an even bigger trick: use the Earth itself as one of the wires. The planet is a giant conductor (not perfect, but very very big). You bury a copper pole, connect it to the circuit, and the earth replaces one wire. Petzold calls it ground in America, earth in England.
A new letter shows up: V = voltage. Voltage is the push on the electrons.
Longer wires = more resistance = less current = dimmer bulb. The telegraph people in the 1800s hit this problem for real. The next chapter is where Petzold shows the fix — a device that makes a weak signal strong again.
I also noticed the book cover for the first time. It spells CODE four times: in Morse, in Braille, in binary, and in English. The whole book is on the cover.
Grokking Chapter 6 and Petzold Chapter 6.