Algorithms and Data Structures · Chapter 8

Hashing and graphs

In a list you find an element in O(n), in a sorted array with binary search in O(log n). A hash table manages it in O(1) on average. After that, this chapter is about graphs: nodes and edges that describe road networks, friendships or computer networks, and the algorithms that find paths in them.

The idea of hashing

A hash table is an array of buckets. A hash function turns the key into a number, and number % size picks the bucket. To search, you calculate the same function again and only look in that one bucket instead of going through all elements.

A simple hash function for strings:

1h = 02for every character c:  h = (h * 31 + c) % size

A good hash function spreads the keys evenly and always gives the same result for equal keys. This is exactly how HashMap works: it calls hashCode() on the key and compares inside the bucket with equals. That's why your own classes used as keys have to override both methods to match.

Collisions and load factor

If two different keys land in the same bucket, that is a collision. Collisions can't be avoided: there are far more possible strings than buckets. The usual solution is separate chaining: every bucket is a list, and colliding keys sit in it one after another.

How full the table is is measured by the load factor α = number of elements / number of buckets. With an even spread, every bucket holds α elements on average. Searching, inserting and deleting then cost O(1 + α) on average, so O(1) as long as α stays small. That's why HashMap enlarges its array automatically as soon as α goes above 0.75. In the worst case, when all keys land in the same bucket, it becomes O(n).

1import java.util.*;2
3public class Main {4    static int hash(String key, int size) {5        int h = 0;6        for (int i = 0; i < key.length(); i++) {7            h = (h * 31 + key.charAt(i)) % size;8        }9        return h;10    }11
12    public static void main(String[] args) {13        int size = 7;14        List<List<String>> buckets = new ArrayList<>();15        for (int i = 0; i < size; i++) {16            buckets.add(new LinkedList<>());17        }18
19        String[] names = {"Tom", "Ana", "Max", "Eva", "Leo"};20        for (String name : names) {21            buckets.get(hash(name, size)).add(name);22        }23
24        for (int i = 0; i < size; i++) {25            System.out.println(i + ": " + buckets.get(i));26        }27        System.out.println("load factor: " + (double) names.length / size);28    }29}

Tom and Eva collide in bucket 1. With 5 elements in 7 buckets, the load factor is about 0.71.

Storing graphs

A graph consists of nodes and edges. In an undirected graph an edge works in both directions, in a directed one only in one. If edges have a length or a cost, the graph is weighted. The easiest way is to number the nodes 0 to n - 1.

There are two common representations, with n nodes and m edges:

Adjacency list: memory O(n + m). Checking for the edge a–b and finding all neighbours of a take O(degree of a).
Adjacency matrix: memory O(n²). Checking for the edge a–b takes O(1), all neighbours of a cost O(n).

The adjacency list (List<List<Integer>>) suits most graphs, because it only needs as much space as there are edges. The matrix (boolean[][]) pays off for very dense graphs or when you often check single edges.

1import java.util.*;2
3public class Main {4    public static void main(String[] args) {5        int n = 5;6        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}};7
8        // adjacency list: one list of neighbours per node9        List<List<Integer>> list = new ArrayList<>();10        for (int i = 0; i < n; i++) {11            list.add(new ArrayList<>());12        }13        // adjacency matrix: matrix[a][b] is true if there is an edge14        boolean[][] matrix = new boolean[n][n];15
16        for (int[] e : edges) {17            list.get(e[0]).add(e[1]);18            list.get(e[1]).add(e[0]);19            matrix[e[0]][e[1]] = true;20            matrix[e[1]][e[0]] = true;21        }22
23        System.out.println("neighbours of 1: " + list.get(1));24        System.out.println("edge 2-4? " + matrix[2][4]);25        System.out.println("edge 3-4? " + matrix[3][4]);26    }27}

Breadth-first and depth-first search

Both visit every node that can be reached from the start, each exactly once. A boolean array remembers who has been visited already, otherwise they run in circles.

Breadth-first search (BFS) works with a queue: first all neighbours, then their neighbours, layer by layer. That's why it finds the shortest path in an unweighted graph: a node in layer k is exactly k edges away from the start.
Depth-first search (DFS) first goes as deep as possible and then turns back. It can be written briefly recursively (the call stack replaces the stack) and is good for finding components or walking through a whole graph.

With an adjacency list, both cost O(n + m): every node gets its turn once, and every edge is looked at once from each end.

1import java.util.*;2
3public class Main {4    static List<List<Integer>> graph = List.of(5            List.of(1, 2), List.of(0, 3, 4), List.of(0, 4), List.of(1), List.of(1, 2));6
7    static List<Integer> bfs(int start) {8        List<Integer> order = new ArrayList<>();9        boolean[] visited = new boolean[graph.size()];10        Deque<Integer> queue = new ArrayDeque<>();11        visited[start] = true;12        queue.add(start);13        while (!queue.isEmpty()) {14            int v = queue.poll();15            order.add(v);16            for (int w : graph.get(v)) {17                if (!visited[w]) {18                    visited[w] = true; // mark when adding, not when taking out19                    queue.add(w);20                }21            }22        }23        return order;24    }25
26    static void dfs(int v, boolean[] visited, List<Integer> order) {27        visited[v] = true;28        order.add(v);29        for (int w : graph.get(v)) {30            if (!visited[w]) {31                dfs(w, visited, order);32            }33        }34    }35
36    public static void main(String[] args) {37        System.out.println("BFS: " + bfs(0));38        List<Integer> order = new ArrayList<>();39        dfs(0, new boolean[graph.size()], order);40        System.out.println("DFS: " + order);41    }42}

Shortest paths with Dijkstra

If edges have different lengths, breadth-first search isn't enough: the path with the fewest edges isn't necessarily the shortest. Dijkstra's algorithm solves this for graphs without negative weights:

dist[start] = 0, all others "infinite".
Take the unfinished node with the smallest dist. Its distance is now final.
Check its neighbours: if the path through it is shorter, store the new distance (relaxing).
Repeat until all reachable nodes are finished.

A PriorityQueue (a heap from chapter 7) delivers the node with the smallest distance. This way Dijkstra costs O((n + m) · log n).

1import java.util.*;2
3public class Main {4    public static void main(String[] args) {5        // neighbours as {node, length}6        List<List<int[]>> graph = List.of(7                List.of(new int[]{1, 4}, new int[]{2, 1}),8                List.of(new int[]{0, 4}, new int[]{2, 2}, new int[]{3, 1}),9                List.of(new int[]{0, 1}, new int[]{1, 2}, new int[]{3, 5}),10                List.of(new int[]{1, 1}, new int[]{2, 5}));11
12        int[] dist = new int[graph.size()];13        Arrays.fill(dist, Integer.MAX_VALUE);14        dist[0] = 0;15        PriorityQueue<int[]> queue = new PriorityQueue<>((x, y) -> Integer.compare(x[1], y[1]));16        queue.add(new int[]{0, 0});17
18        while (!queue.isEmpty()) {19            int[] current = queue.poll();20            int v = current[0];21            if (current[1] > dist[v]) {22                continue; // outdated entry23            }24            System.out.println("done: " + v + " at " + dist[v]);25            for (int[] edge : graph.get(v)) {26                int candidate = dist[v] + edge[1];27                if (candidate < dist[edge[0]]) {28                    dist[edge[0]] = candidate;29                    queue.add(new int[]{edge[0], candidate});30                }31            }32        }33        System.out.println(Arrays.toString(dist));34    }35}

Node 1 first gets the distance 4 through the direct edge. Via node 2 it's only 1 + 2 = 3. The old entry {1, 4} is still in the queue afterwards and gets skipped.

Common mistakes

Keys compared with ==
In your own hash table, entry.key == key checks whether it's the same object, not whether the strings are equal. A key built at runtime is then not found. Compare with entry.key.equals(key). For the same reason, your own key classes have to override equals and hashCode together.
Marked as visited too late
If you only mark a node in breadth-first search when you take it out of the queue, another neighbour can put it in again before that. It then gets visited twice. So mark it when you put it in:
```
1if (!visited[w]) {2    visited[w] = true;3    queue.add(w);4}
```
Wrong algorithm for the shortest path
Breadth-first search counts edges. In a weighted graph it therefore gives wrong distances; there you need Dijkstra. Dijkstra in turn requires that no weight is negative: a distance that is final must not get smaller later.