Hash Tables and Hash Functions

Hash Table

For example, when developing a student management system, we need to retrieve a student's name quickly by entering their student ID. Rather than query the database every time, we can keep a cache table in memory to improve lookup efficiency.

Student list

As another example, to count the frequency of certain words in an English book, we traverse the book and record the number of occurrences of these words in memory.

Word frequencies

These needs gave rise to an important data structure: the hash table. A hash table provides a mapping from keys to values. Given a key, we can efficiently retrieve its matching value.

With a uniformly distributed hash function and a controlled load factor, expected lookup time is $O(1)$; worst-case time can be $O(n)$.

A hash table has two basic jobs:

1. Calculate a position: construct a hash function to determine where a key is stored.

2. Resolve collisions: apply a strategy when multiple keys map to the same position.

Hash Function

The basic idea of hashing is to pass a key through a deterministic function whose result gives the storage address of the data object. This function is the hash function.

Hash function

Hash tables are usually based on arrays. Arrays are accessed by index, while hash-table keys can be integers, strings, and other types.

Hash-function implementations vary across languages. For integer values, conversion to an array index is straightforward. The simplest approach is to take the remainder modulo the array length.

A good hash function should consider two factors:

1. Simple computation to make the conversion fast.

2. Uniform distribution of keys across the address space to reduce collisions.