TL;DR

Hashing helps you store and retrieve data super fast by mapping keys to array indices. Graphs model relationships between data points, making them great for things like social networks or navigation. Together, they're fundamental tools for solving a wide range of computational problems efficiently.

1. The Mental Model

Imagine a super-organized library (hashing) where each book has a special code that tells you exactly which shelf it's on. Now imagine a subway map (graphs) showing all the stations and how they connect, letting you plan your route.

2. The Core Material

Hashing: Fast Lookups

Photo by Victor Bogdan on Pexels

Hashing is a technique that takes an input (a "key") and converts it into a fixed-size integer, which usually represents an index in an array (a "hash table"). The goal is to achieve O(1) average-case time complexity for insertions, deletions, and lookups.

The process involves:
1. Hash Function: Takes a key and produces a hash code (an integer).
2. Compression Function: Maps the hash code to a valid index within the hash table's array.

A common challenge is collisions, where two different keys produce the same hash index. We handle these using:

• Separate Chaining: Each array index points to a linked list (or another data structure) of keys that hash to that index.
• Open Addressing: If a slot is taken, you try to find another empty slot in the array using strategies like linear probing, quadratic probing, or double hashing.

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(self.size)] # Separate Chaining

    def _hash(self, key):
        return hash(key) % self.size # Simple hash function and compression

    def insert(self, key, value):
        index = self._hash(key)
        # Check if key already exists, update if it does
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        self.table[index].append((key, value)) # Add new key-value pair

    def get(self, key):
        index = self._hash(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None # Key not found

    def delete(self, key):
        index = self._hash(key)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                del self.table[index][i]
                return True
        return False # Key not found

Graphs: Representing Connections

Photo by Arturo A on Pexels

A graph is a non-linear data structure consisting of nodes (or vertices) and edges (or links) that connect them. Graphs are perfect for modeling relationships.

Key terms:
* Vertex (Node): A point in the graph.
* Edge: A connection between two vertices.
* Directed Graph: Edges have a direction (e.g., A -> B, but not necessarily B -> A).
* Undirected Graph: Edges have no direction (e.g., A -- B means B -- A).
* Weighted Graph: Edges have associated values (weights), often representing cost, distance, or time.
* Adjacency List: An array where each index i stores a list of vertices adjacent to vertex i. Space-efficient for sparse graphs.
* Adjacency Matrix: A 2D array where matrix[i][j] is 1 (or weight) if an edge exists between i and j, and 0 otherwise. Good for dense graphs, fast lookup of edge existence.

Common graph algorithms include:
* Traversal: Visiting every node (e.g., Breadth-First Search (BFS), Depth-First Search (DFS)).
* Shortest Path: Finding the shortest path between two nodes (e.g., Dijkstra's algorithm, Bellman-Ford).
* Minimum Spanning Tree: Finding a subset of edges that connect all vertices with the minimum total edge weight (e.g., Prim's, Kruskal's).

Here's how you might choose a graph representation:

graph TD
    A["Need to represent connections?"] --> B{How many edges compared to nodes?};
    B -- "Many edges (Dense Graph)" --> C["Adjacency Matrix (O(V^2) space)"];
    B -- "Few edges (Sparse Graph)" --> D["Adjacency List (O(V+E) space)"];
    C --> E["Fast edge existence check O(1)"];
    D --> F["Fast iteration over neighbors O(degree)"];
    E --> G["Algorithms: BFS, DFS, Dijkstra's (with matrix)"];
    F --> H["Algorithms: BFS, DFS, Dijkstra's (with list)"];

3. Worked Example

Let's use a hash table to store some user IDs and names, and then represent friendships using a graph.

Scenario: We have users: "Alice" (ID 101), "Bob" (ID 102), "Charlie" (ID 103), "David" (ID 104).

1. Hashing User IDs to names:
   We'll use our HashTable from above.

   ```python
   user_data = HashTable(10) # A hash table of size 10
   user_data.insert(101, "Alice")
   user_data.insert(102, "Bob")
   user_data.insert(103, "Charlie")
   user_data.insert(104, "David")

   print(f"User 102's name: {user_data.get(102)}") # Output: Bob
   user_data.insert(101, "Alicia") # Update Alice's name
   print(f"User 101's new name: {user_data.get(101)}") # Output: Alicia
   ```

2. Representing Friendships (Graph):
   Assume friendships: Alice-Bob, Bob-Charlie, Charlie-David, David-Alice. This is an undirected graph. We'll use an adjacency list.

   ```python

   Mapping names back to simple integer indices for graph representation

   name_to_idx = {"Alicia": 0, "Bob": 1, "Charlie": 2, "David": 3}
   idx_to_name = {0: "Alicia", 1: "Bob", 2: "Charlie", 3: "David"}

   num_users = len(name_to_idx)
   friendship_graph = [[] for _ in range(num_users)]

   def add_friendship(u1_name, u2_name):
   u1_idx = name_to_idx[u1_name]
   u2_idx = name_to_idx[u2_name]
   friendship_graph[u1_idx].append(u2_idx)
   friendship_graph[u2_idx].append(u1_idx) # Undirected graph

   add_friendship("Alicia", "Bob")
   add_friendship("Bob", "Charlie")
   add_friendship("Charlie", "David")
   add_friendship("David", "Alicia")

   Who are Alicia's friends?

   alicia_idx = name_to_idx["Alicia"]
   alicia_friends_indices = friendship_graph[alicia_idx]
   alicia_friends_names = [idx_to_name[idx] for idx in alicia_friends_indices]

   print(f"\nAlicia's friends: {alicia_friends_names}") # Output: ['Bob', 'David']
   ```

This example shows how hashing gives us fast access to user details, and a graph helps us model and query their relationships.

4. Key Takeaways

• Hashing converts keys into array indices for incredibly fast average-case data access.
• Collisions are inevitable in hashing and require strategies like chaining or open addressing to resolve.
• Graphs model relationships between data points using nodes and edges.
• Adjacency lists are generally preferred for sparse graphs, while adjacency matrices suit dense graphs.
• Both hashing and graphs are foundational for solving complex problems like database indexing, network routing, and social media analysis.
• Understanding the trade-offs between different hashing collision resolution methods is crucial for performance.

Common mistakes to avoid:
- Choosing a hash table size that's too small, leading to frequent collisions and poor performance.
- Not handling edge cases or non-existent keys when retrieving data from a hash table.
- Using an inappropriate graph representation (list vs. matrix) for your problem's density, leading to inefficient space or time complexity.
- Forgetting to handle both directions of an edge if your graph is undirected.

5. Now Try It

Implement a simple hash table using open addressing with linear probing. Your insert(key, value) method should place the key-value pair, and if the spot is taken, try the next available spot (wrapping around if needed). Your get(key) method should retrieve the value, searching linearly if the first spot doesn't match the key.

Success looks like:
You can insert several key-value pairs, including some that might collide with others. Then, you can get all those values back correctly, demonstrating your linear probing logic works for both insertion and retrieval.