What is a Hash Function?
You'll learn: How hash functions transform keys into array indices to enable fast data storage and retrieval.
The Core Idea
A hash function is a mathematical function that takes a key (like a name, number, or word) and converts it into an array index. This index tells you exactly where to store or find data in an underlying array.
Think of it like a filing system in a library. Instead of searching shelf by shelf for a book, the librarian uses a formula: "Fiction books go to floor = first letter's position in alphabet." The book "Dune" would map to floor 4 (D = 4th letter). The librarian's formula is the hash function; the floor number is the hash value.
Why We Need Hash Functions
You've learned about arrays, linked lists, stacks, and queues. Finding an item in these structures often requires searching sequentially—potentially checking every element. Hash functions aim to solve this by computing exactly where data lives in constant time.
A hash function takes your key and produces an integer index within the bounds of an array:
hash(key) → integer index (0 to array_size - 1)
For example, if you want to store student records by student ID:
hash(12345)might return7→ store student data at index 7hash(98765)might return203→ store student data at index 203
The Promise
With a good hash function, you can jump directly to where data is stored instead of searching through everything—transforming slow operations into fast ones.
Key Takeaway: A hash function maps keys to array indices, enabling direct access to data locations and forming the foundation of hash tables.