Hash Functions Explained Tutorial | Learn Data Structures

What Is a Hash Function?

A hash function is a function that takes an input called a key and converts it into a numeric value called a hash value. In a hash table, this value is used to determine where the corresponding data should be stored or searched for.

Hash functions are a fundamental part of hashing because they provide the connection between a key and a location in a hash table.

Basic flow: Key → Hash Function → Hash Value → Table Index → Stored Entry

Why Do We Need a Hash Function?

Consider a collection containing thousands of users. If a user needs to be retrieved using a username, searching every record one by one could require O(n) time.

A hash table uses a hash function to transform the username into a location. This makes key-based lookup typically O(1) on average when the table is appropriately designed.

"alice"
   ↓
Hash Function
   ↓
42
   ↓
42 % 10
   ↓
Bucket 2

How a Hash Function Works

A hash function processes the input key and produces a hash value. The hash table then converts that value into a valid bucket index.

A simplified example for a table containing 10 buckets might look like this:

Key:
"apple"

Hash value:
37

Table size:
10

Index:
37 % 10 = 7

Storage location:
Bucket 7

During a lookup, the same key is passed through the same hash function so that the table can calculate the same bucket location.

Hash Value vs Table Index

A hash value and a table index are related but are not necessarily the same thing. A hash function can produce a large integer, while a hash table usually contains a much smaller number of buckets.

Hash value = 123456

Table size = 100

Index = 123456 % 100
      = 56

The table index identifies an actual bucket, while the hash value is the intermediate result generated from the key.

Properties of a Good Hash Function

A hash function used by a hash table should have several important characteristics.

1. Deterministic

The same key should produce the same hash value when evaluated under the same hashing configuration.

hash("alice") → 42
hash("alice") → 42

2. Efficient

A hash function should be inexpensive to calculate because it may be executed for every insertion, lookup, or deletion.

3. Good Distribution

Keys should be distributed reasonably across the available buckets. Concentrating many keys in a small number of buckets creates more collisions.

4. Consistent

The function must use the same rules during insertion and lookup. Otherwise, the table may calculate different locations for the same key.

Hash Function for Strings

Strings cannot normally be used directly as numeric array indexes, so a hash function can process their characters and produce a number.

A simple educational implementation can use the character code of each character:

function hashString(key, tableSize) {
  let hash = 0;

  for (const char of key) {
    hash = (hash * 31 + char.charCodeAt(0)) % tableSize;
  }

  return hash;
}

console.log(hashString('apple', 10));
console.log(hashString('banana', 10));

This example directly returns a bucket index because the modulo operation is applied during the calculation. It is useful for understanding the mechanics, but production systems may use more sophisticated hashing strategies.

Character Codes and Hashing

Computers represent characters using numeric character codes. A simple string hash function can use these numbers as part of its calculation.

console.log('A'.charCodeAt(0));
// 65

console.log('B'.charCodeAt(0));
// 66

console.log('a'.charCodeAt(0));
// 97

A hash function can combine these character values to produce a number representing the complete key.

Hashing an Integer Key

Integer keys can be simpler to hash because they already have numeric representations. A basic educational example can use the remainder operator to map an integer into the available buckets.

function hashNumber(key, tableSize) {
  return key % tableSize;
}

console.log(hashNumber(42, 10));
// 2

console.log(hashNumber(87, 10));
// 7

This works well as a simple demonstration, although a real implementation may need to account for key distributions and other requirements.

Hash Collisions

A hash collision occurs when two different keys produce the same bucket index.

hash("cat") % 10 = 4
hash("dog") % 10 = 4

Both keys → Bucket 4

A collision does not mean that the hash function is necessarily incorrect. A finite table has a limited number of buckets, while the number of possible keys can be extremely large. Hash tables therefore require a collision-resolution strategy.

Hash Function and Collision Frequency

The distribution produced by a hash function affects how often collisions occur. If many different keys map to the same bucket, operations may require more work to identify the correct entry.

Poor distribution:

Bucket 0 → A → B → C → D → E
Bucket 1 → empty
Bucket 2 → empty
Bucket 3 → empty

Better distribution:

Bucket 0 → A
Bucket 1 → C
Bucket 2 → E
Bucket 3 → B
Bucket 4 → D

A good distribution helps keep collision chains or probing sequences manageable.

Hash Function and Table Size

The table size affects the mapping from hash values to bucket indexes. A common simplified approach is to use the modulo operation.

index = hashValue % tableSize

For example:

hashValue = 73

tableSize = 10

index = 73 % 10
      = 3

When a hash table is resized, the table size changes and entries generally need to be redistributed because their bucket indexes may change.

Hash Function and Load Factor

The load factor describes how many entries are stored relative to the number of buckets.

Load Factor =
Number of Entries / Number of Buckets

If a table contains 6 entries and 10 buckets:

6 / 10 = 0.6

A high load factor can increase collisions. Hash-table implementations commonly resize their underlying storage when an implementation-specific threshold is reached.

Hash Function Must Be Deterministic

Determinism is essential because a key must map to a consistent location. If the hash result changes unexpectedly between insertion and lookup, the table may not be able to find the stored entry.

Insert:

"alice" → bucket 4


Lookup:

"alice" → bucket 4

The same hashing rules must therefore be used consistently for all operations on the table.

Hash Function and Equality

A hash function helps determine where a key may be located, but a hash value alone does not prove that two keys are equal.

Two different keys can have the same hash value:

Key A → Hash 42
Key B → Hash 42

Hash values are equal,
but Key A and Key B may be different.

The hash table must therefore compare the actual keys when resolving a collision or confirming that a requested key exists.

Separate Chaining with a Hash Function

In separate chaining, the hash function determines the bucket, while a collection inside that bucket handles entries that share the same index.

hash("alice") → 2
hash("bob")   → 2

Bucket 2:
[
  { key: "alice", value: 100 },
  { key: "bob", value: 200 }
]

The hash function narrows the search to bucket 2, after which the table checks the entries in that bucket.

Open Addressing with a Hash Function

With open addressing, the hash function determines the initial position. If that position is occupied, the table uses a probing strategy to find another position.

hash("alice") → 3

Bucket 3 is occupied

Linear probing:
3 → 4 → 5 → ...

Find the next available bucket.

The hash function therefore works together with the collision-resolution strategy rather than solving collisions by itself.

A Complete Simple Hash Table Example

The following implementation combines a string hash function with separate chaining to demonstrate a basic hash table.

class HashTable {
  constructor(size = 10) {
    this.buckets = Array.from(
      { length: size },
      () => []
    );
  }

  hash(key) {
    let hashValue = 0;

    for (const char of key) {
      hashValue =
        (hashValue * 31 + char.charCodeAt(0)) %
        this.buckets.length;
    }

    return hashValue;
  }

  set(key, value) {
    const index = this.hash(key);
    const bucket = this.buckets[index];

    const existing = bucket.find(
      entry => entry.key === key
    );

    if (existing) {
      existing.value = value;
      return;
    }

    bucket.push({ key, value });
  }

  get(key) {
    const index = this.hash(key);
    const bucket = this.buckets[index];

    const entry = bucket.find(
      item => item.key === key
    );

    return entry ? entry.value : undefined;
  }
}

const table = new HashTable();

table.set('alice', 100);
table.set('bob', 200);

console.log(table.get('alice'));
// 100

console.log(table.get('bob'));
// 200

Hash Function for Composite Keys

Applications sometimes need to identify data using more than one field. A composite key can be converted into a string and then passed through a hash function.

function createKey(userId, courseId) {
  return `${userId}:${courseId}`;
}

const key = createKey(101, 25);

console.log(key);
// 101:25

The resulting key can then be hashed by a hash-table implementation. Care should be taken when constructing composite keys so that different logical combinations do not accidentally produce the same representation.

Hash Functions and Security

Hash functions used in data structures should not automatically be confused with cryptographic hash functions. Their requirements are different.

A data-structure hash function is primarily concerned with efficient computation and good distribution of keys. A cryptographic hash function is designed to provide security properties such as resistance to finding inputs that produce particular outputs.

Important distinction: Do not choose a general-purpose data-structure hash function for password storage or other security-sensitive hashing requirements.

Hash Function Complexity

The cost of calculating a hash depends on the type and size of the key. For a string with k characters, a straightforward character-by-character hash function generally takes O(k) time.

function hashString(key, tableSize) {
  let hash = 0;

  for (const char of key) {
    hash = (hash * 31 + char.charCodeAt(0)) % tableSize;
  }

  return hash;
}

// k = number of characters
// Time: O(k)

The hash-table lookup is commonly described as O(1) average-case when considering the expected table operation, but hashing the key itself may have a cost based on the key size.

Hash Function vs Hash Table

A hash function and a hash table are not the same thing. The hash function performs the mapping, while the hash table provides the storage and lookup mechanism.

Concept	Purpose
Hash function	Converts a key into a hash value or index
Hash table	Stores and retrieves entries using hashing
Bucket	Storage location selected by the hash process
Collision strategy	Handles multiple keys mapping to the same location

Common Hash Function Mistakes

1. Producing Different Results for the Same Key

A hash table needs consistent hashing. If the same key maps to different locations during insertion and lookup, stored data may become inaccessible.

2. Assuming Hash Values Are Unique

Different keys can produce the same hash value. Hash collisions are a normal property of hash tables and must be handled correctly.

3. Creating Poor Distribution

If a hash function concentrates many keys into a small number of buckets, collisions increase and the practical performance of the table can degrade.

4. Forgetting the Table Size

A hash value may be much larger than the number of available buckets. The hash-table implementation needs a consistent method for converting the hash value into a valid index.

5. Confusing Data-Structure Hashing with Cryptographic Hashing

Hash functions for hash tables and cryptographic hash functions solve different problems. Their performance goals and security properties should not be treated as interchangeable.

Hash Function in Interview Problems

Understanding hash functions helps explain why hash maps and hash sets can provide efficient average-case lookup. In coding problems, you will often use a language-provided map or set rather than implementing the hash function yourself.

Common problems that use hash-based structures include:

Frequency counting.
Duplicate detection.
Two-sum and complement lookup.
Grouping values.
Checking whether an item has already been seen.
Tracking visited vertices during graph traversal.
Memoization and caching.

Key Takeaways

A hash function converts a key into a hash value.
A hash table uses the hash value to determine a bucket or table index.
A good hash function should be deterministic, efficient, and distribute keys reasonably.
Different keys can produce the same hash value, resulting in collisions.
Hash functions work together with collision-resolution techniques such as chaining and open addressing.
The table size affects how hash values are converted into bucket indexes.
Load factor and resizing influence the practical performance of a hash table.
The cost of hashing a string depends on the size of the key.
Data-structure hash functions should not be confused with cryptographic hash functions.

Topics

Hash Functions Explained