Hashing and Graph Traversal Notes

Open Addressing with Linear Probing

• Open Addressing:
  • Uses empty buckets to store items that belong in other buckets.
  • Linear Probing: Uses the next empty bucket.
• Problem: Clustered hash values result in a lot of searching.

Open Addressing with Quadratic Probing

• Quadratic Probing:
  • Jumps further ahead to avoid clustering of full buckets.
  • Linear probing looks at H, H+1, H+2, H+3, H+4, …
  • Quadratic probing looks at H, H+1, H+4, H+9, H+16, …
• Runtime:
  • May be faster, but may not be; depends on keys.
  • Worst-case is always $O(n)$.
  • In practice, average-case is $O(1)$ if you make good design decisions and insertions are not done maliciously.

Rehashing and Hashing for Non-Integers

• Hashing for non-integers and in Java.
• Hash function (so far): $h(x) = x \% C$
• Hashing Non-Integer Values:
  • If it's a value in memory, it's encoded in binary.
  • Interpret the bits as an integer and hash as before.
  • General theme: convert your type to an integer, then mod it.

Hashing Multiple Integers

• Hash a tuple of integers $(a, b, c, d)$
  • $h((a, b, c, d)) = (a + b + c + d) \% N$
  • $h((a, b, c, d)) = (ak<em>1 + bk</em>2 + ck<em>3 + dk</em>4) \% N$ for some constant $k$

Hashing Strings

• Convert each character to its integer character code (ASCII or unicode).
• Java's String uses: $s[0]<em>31^{n-1} + s[1]</em>31^{n-2} + \dots +s[n-1]$

Hashing in Java

• Scenario 1: Using a class someone else wrote.
  • Object has a hashCode method.
  • The class inherits from Object.
  • Just call its hashCode method.
  • Detail: hashCode returns an integer; mod it by your table's size.
  • Unless overridden, this returns the object’s address in memory.
• Scenario 2: Writing a class.
  • Object has a hashCode method.
  • Your class inherits from Object.
  • You may override hashCode.
  • If you're overriding equals, objects that are equal according to equals() must have the same hash code.

Graphs: Introduction

• Graph: a bunch of points connected by lines.
  • The lines may have directions, or not.
• Examples of Graphs:
  • The internet's undersea world
  • Social Networks
  • The USA as a graph (neighboring states connected by edges).
  • Electrical circuit as a graph

Formal Definitions of Graphs

• A directed graph (digraph) is a pair $(V, E)$ where:
  • $V$ is a (finite) set.
  • $E$ is a set of ordered pairs $(u, v)$ where $u, v$ are in $V$.
  • Often (not always): $u \neq v$ (i.e., no edges from a vertex to itself).
  • An element in $V$ is called a vertex or node.
  • Elements in $E$ are called edges or arcs.
  • $|V|$ = size of $V$ (traditionally called $n$ or $v$).
  • $|E|$ = size of $E$ (traditionally called $m$ or $e$).

Undirected Graphs

• An undirected graph is just like a digraph, but:
  • $E$ is a set of unordered pairs $(u, v)$ where $u, v$ are in $V$.
  • Any undirected graph has an equivalent directed graph: Replace each undirected edge with two directed edges.
  • A directed graph doesn't always have an equivalent undirected graph.

Graph Terminology: Adjacency

• Two vertices are adjacent if they are connected by an edge.
• Nodes $u$ and $v$ are called the source and sink of the directed edge $(u, v)$.
• Nodes $u$ and $v$ are endpoints of an edge $(u, v)$ (directed or undirected).

Graph Terminology: Degree

• The outdegree of a vertex $u$ in a directed graph is the number of edges for which $u$ is the source.
• The indegree of a vertex $v$ in a directed graph is the number of edges for which $v$ is the sink.
• The degree of a vertex $u$ in an undirected graph is the number of edges of which $u$ is an endpoint.

Graph Terminology: Paths and Cycles

• A path is a sequence of vertices in which each consecutive pair are adjacent.
• In a directed graph, paths must follow the direction of the edges (nodes must be ordered source then sink).
• A cycle is a path that ends where it started.
• A graph is acyclic if it has no cycles.

Graph Terminology: Connectedness

• A subgraph of a graph $G$ is a graph whose node and edge sets are subsets of $G$'s node and edge sets.
• An undirected graph is connected if there is a path between every pair of nodes in the graph.
• A directed graph is strongly connected if there is a path between every pair of nodes in the graph.
• A directed graph is weakly connected if the graph would be connected if its edges were undirected.

Representing Graphs

• Adjacency List
• Adjacency Matrix

Graph Traversals

• Graph Algorithms:
  • Search/traversal: search for a particular node or traverse all nodes
    • Breadth-first
    • Depth-first
  • Shortest Paths

Depth-First Search (DFS)

• Given a graph and one of its nodes $u$, "Visit" each node reachable from $u$
• Problem: multiple ways to get to the same node.
• Key Idea: keep track of where we've been.
  • boolean visited[]:
    • visited[u] is true iff Node u has been visited
    • Visiting u means setting visited[u] = true
    • v is explorable from u if there is a path $(u, …, v)$ in which all nodes along the path are unvisited.
• Recursive Implementation:

/** Visit all nodes that are explorable from u.
 * Precondition: u is unvisited. */
public static void dfs(int u) {
 visited[u] = true;
 for all edges (u, v) leaving u:
 if v is unvisited, dfs(v);
}

• Iterative Implementation (using a Stack):

/** Visit all nodes explorable from u.
* Pre: u is unvisited. */
public static void dfs(int nodeID) {
 Stack s = (nodeID); // Not Java!
 // inv: all nodes to be visited are
 // explorable from some node in s
 while (s is not empty) {
 u = s.pop();
 if (u has not been visited) {
 visit u;
 for each edge (u, v) from u:
 s.push(v);
 }
 }
}

Breadth-First Search (BFS)

• Iterative Implementation (using a Queue):

/** Visit all nodes explorable from u.
 * Pre: u is unvisited. */
public static void bfs(int nodeID) {
 Queue q = (nodeID); // Not Java!
 // inv: all nodes to be visited are
 // explorable from some node in q
 while (q is not empty) {
 u = q.dequeue();
 if (u has not been visited) {
 visit u;
 for each edge (u, v) from u:
 q.enqueue(v);
 }
 }
}