Graph & Hashing Cheat Sheet

Graphs represent relationships between objects, while hashing provides efficient data retrieval. Understanding both is crucial for advanced data structures and algorithms.

Core Principles

Graphs model networks and connections.
Hashing enables fast lookups via key-value pairs.
Graph traversal algorithms explore connections.
Hash tables minimize search time.
Adjacency lists and matrices represent graphs.
Hash functions map keys to indices.
Collision resolution is key for hash table performance.
Directed vs. Undirected graphs.
Weighted vs. Unweighted graphs.
Open vs. Closed addressing for collision handling.

Key Terms

Graph: A data structure consisting of nodes (vertices) and edges connecting them.
Vertex (Node): An individual element within a graph.
Edge: A connection between two vertices.
Adjacency List: A representation where each vertex has a list of its adjacent vertices.
Adjacency Matrix: A matrix where rows and columns represent vertices, and cells indicate edge presence.
Hashing: A technique to map data of arbitrary size to fixed-size values (hash codes).
Hash Table: A data structure that uses a hash function to map keys to values for efficient access.
Hash Function: A function that computes an index into an array from a key.
Collision: When two different keys hash to the same index.
Collision Resolution: Techniques to handle collisions (e.g., chaining, open addressing).
Chaining: Collision resolution where each bucket stores a linked list of entries.
Open Addressing: Collision resolution where colliding elements are stored in other available slots.
Breadth-First Search (BFS): Graph traversal exploring neighbors level by level.
Depth-First Search (DFS): Graph traversal exploring as far as possible along each branch before backtracking.

Real World Examples

Social Networks: Graphs model users (vertices) and friendships/connections (edges).
Navigation Systems: Graphs represent locations (vertices) and roads (edges) for route finding.
Database Indexing: Hash tables provide fast lookups for records based on primary keys.
Caching: Hash tables store frequently accessed data for quick retrieval.
Compilers: Hash tables manage symbol tables for variable and function lookups.

Timeline

1800s: Early concepts of graph theory emerge (Euler's Seven Bridges of Königsberg).
1950s: Development of hashing techniques for computer science applications.
1956: Hash table concept formalized by H. Sherman.
1959: Dijkstra's algorithm for shortest paths published.
1960s: Introduction of BFS and DFS algorithms.
1970s: Widespread adoption of hash tables in programming languages and databases.