Start learning →

Hash tables and graphs

Finding a value by its key in constant time with a hash table, and modelling connections with graphs that are searched breadth-first or depth-first.

About 8 hours of study

Learning objectives

Lessons

  1. 1

    Hash tables

    A hash function picks a bucket: collisions handled by chaining and by linear probing, and why the table must not get too full.

  2. 2

    Graphs

    Vertices and edges, directed and undirected, stored as an adjacency matrix or as adjacency lists.

  3. 3

    Graph traversal: BFS and DFS

    Breadth-first search with a queue finds the fewest edges to every vertex; depth-first search goes deep with recursion.

Module practice

Module quiz

1. What is a collision in a hash table?
2. An undirected graph has 5 edges. What is the sum of the degrees of all its vertices?
3. Keys 12, 22 and 32 are inserted with linear probing into a table of size 10, using hash(key) = key % 10. Where is 32 stored?
4. A graph has 1,000 vertices and 3,000 edges. How many cells does its adjacency matrix have?
5. A graph has edges A–B, A–C, B–D and C–D. Breadth-first search starts at A. What distance does it give D?
6. Why does breadth-first search mark a vertex when it joins the queue, and not when it leaves?
7. A hash table with chaining has 50 buckets and holds 200 items, spread evenly. About how many items does a search for a missing key examine?

‹ Trees and heapsChoosing structures and finding bugs ›