Hash Table Data Structure Explained Tutorial

What Is a Hash Table?

A hash table is a data structure that stores information using key-value pairs. It uses a hash function to convert a key into a value that determines where the associated data should be stored.

The main purpose of a hash table is to provide efficient lookup, insertion, and deletion. Under suitable conditions, these operations typically take O(1) average time.

Core idea: A key is transformed by a hash function into a bucket location, allowing the hash table to locate associated data without scanning every stored element.

Hash Table Structure

A simplified hash table can be visualized as an array of buckets:

Index       Entry
----------------------------
0           empty
1           ("alice", 1001)
2           empty
3           ("bob", 1002)
4           ("charlie", 1003)
5           empty

When a key such as "bob" is supplied, the hash function calculates a hash value. That value is then mapped to a valid bucket index.

Key Components of a Hash Table

A hash table depends on several components working together.

Key: Identifies the stored entry.
Value: Data associated with the key.
Hash function: Converts the key into a hash value.
Buckets: Locations where entries are stored.
Collision strategy: Determines how multiple keys sharing a bucket are handled.
Load factor: Measures how full the table is and can influence resizing.

How a Hash Table Works

Suppose an application wants to store a user's account identifier using the username "alice".

Key:
"alice"

      ↓

Hash Function

      ↓

Hash Value:
42

      ↓

Table Size:
10

      ↓

Index:
42 % 10 = 2

      ↓

Bucket 2:
("alice", userId)

During a lookup, the same key is hashed again, allowing the table to determine where the corresponding entry should be located.

Hash Function in a Hash Table

The hash function converts a key into a numeric hash value. The hash value is then mapped to an available bucket.

A simplified table-index calculation can be represented as:

index = hash(key) % tableSize

A useful hash function should be deterministic, efficient, and capable of distributing keys reasonably across the table.

Simple String Hash Function

The following implementation demonstrates a simple hash function for strings. It is intended to explain the concept rather than serve as a production hashing implementation.

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

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

  return hashValue;
}

console.log(hash('alice', 10));
console.log(hash('bob', 10));

Hash Table Buckets

A bucket is a logical storage location inside a hash table. Multiple different keys can map to the same bucket because the number of possible keys is usually much larger than the number of available buckets.

Bucket 0 → empty
Bucket 1 → ("alice", 25)
Bucket 2 → empty
Bucket 3 → ("bob", 31)
Bucket 4 → ("cat", 12)

How entries are stored inside a bucket depends on the collision-resolution technique used by the hash table.

Hash Table Operations

The fundamental hash table operations are insert, search, and delete.

Insert

To insert an entry, the table hashes the key, calculates a bucket, and stores the key-value pair using its collision-handling strategy.

Search

To search for a key, the table calculates the same bucket and checks the relevant entry or entries stored there.

Delete

To delete a key, the table finds its bucket and removes the corresponding entry while maintaining the rules required by its collision strategy.

Hash Table Implementation with Separate Chaining

Separate chaining stores multiple entries in the same bucket. Each bucket can contain a collection of key-value pairs.

Bucket 2:
["alice" → 25] → ["bob" → 30] → ["cat" → 15]

When a collision occurs, the new entry is added to the collection associated with that bucket.

Hash Table in JavaScript

JavaScript provides Map as a built-in key-value collection. It provides a convenient abstraction for hash-table-like use cases without requiring manual bucket and collision management.

const users = new Map();

users.set('alice', 101);
users.set('bob', 102);
users.set('charlie', 103);

console.log(users.get('bob'));
// 102

console.log(users.has('alice'));
// true

users.delete('charlie');

console.log(users.size);
// 2

Building a Simple Hash Table in JavaScript

Implementing a small hash table from scratch helps demonstrate what happens underneath a higher-level map abstraction.

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(
      entry => entry.key === key
    );

    return entry ? entry.value : undefined;
  }

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

    const entryIndex = bucket.findIndex(
      entry => entry.key === key
    );

    if (entryIndex === -1) {
      return false;
    }

    bucket.splice(entryIndex, 1);
    return true;
  }
}

const table = new HashTable();

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

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

table.delete('alice');

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

This example uses arrays inside buckets, so collisions are handled through separate chaining. It is intentionally simple so that the main hash-table mechanics remain visible.

Handling Duplicate Keys

A hash table that stores key-value pairs normally treats the key as an identifier. If the same key is inserted again, the existing value is commonly updated rather than creating a second independent key.

const users = new Map();

users.set('alice', 'Developer');
users.set('alice', 'Senior Developer');

console.log(users.get('alice'));
// Senior Developer

The exact behavior depends on the hash-table API, but unique keys are a fundamental property of typical map-style hash tables.

What Is a Hash Collision?

A collision occurs when different keys map to the same bucket.

hash("alice") % 10 = 4
hash("bob") % 10 = 4

Bucket 4:
("alice", 101)
("bob", 102)

Collisions cannot generally be eliminated completely because a finite table contains fewer locations than the possible key space. The goal is to handle collisions efficiently.

Collision Resolution Techniques

Separate Chaining

Separate chaining keeps multiple entries in a bucket. A linked list, dynamic array, or another collection can be used to store entries that share the same bucket.

Open Addressing

Open addressing stores entries directly in the table. If the calculated bucket is already occupied, the table probes other positions according to a defined probing strategy.

Linear probing
Quadratic probing
Double hashing

These approaches have different performance and clustering characteristics.

Separate Chaining vs Open Addressing

Feature	Separate Chaining	Open Addressing
Collision storage	Multiple entries per bucket	Find another table position
Extra structure	Usually requires a bucket collection	Entries remain inside the table
Common techniques	Linked list, array, collection	Linear, quadratic, double hashing
Load factor	Can exceed 1 in some designs	Must remain below table capacity

What Is Load Factor?

The load factor measures how full a hash table is. A simplified formula is:

Load Factor = Number of Entries / Number of Buckets

For example, if a hash table contains 7 entries and 10 buckets:

Load Factor = 7 / 10
            = 0.7

A higher load factor can increase the likelihood of collisions. Hash-table implementations therefore commonly monitor the load factor and resize the table when necessary.

Hash Table Resizing

When a hash table becomes too full, it can create a larger underlying table and redistribute its entries. This process is often called rehashing.

Before:

[ A ][ B ][ C ][ D ]


Resize:


After:

[   ][ A ][   ][ B ][   ][ C ][ D ][   ]

The table size changes the bucket calculation, so existing entries usually need to be inserted into their new locations.

Why Resizing Matters

If a table becomes heavily crowded, many keys may map to occupied locations. This can make searches longer and reduce the practical benefit of hashing.

Resizing increases the number of available buckets and helps maintain a useful distribution of entries.

Hash Table Complexity

With a suitable hash function and controlled load factor, hash-table operations are typically efficient on average.

Operation	Average Case	Worst Case
Search	O(1)	O(n)
Insertion	O(1)	O(n)
Deletion	O(1)	O(n)

The worst case can occur when many keys collide and the collision-resolution structure requires a linear search. Resizing can also temporarily require O(n) work because existing entries may need to be redistributed.

Hash Table vs Array

Arrays and hash tables both provide efficient ways to access data, but they use different access models.

Feature	Array	Hash Table
Access model	Numeric index	Key
Typical direct lookup	O(1) by index	O(1) average by key
Ordering	Index order	Depends on the implementation/API
Typical use	Sequential data	Key-based lookup

Hash Table vs Binary Search Tree

A hash table is designed primarily for key-based access, while a binary search tree can maintain elements according to their ordering relationship.

Feature	Hash Table	Balanced BST
Average lookup	O(1)	O(log n)
Sorted order	Not the primary purpose	Supported naturally
Range queries	Not naturally supported	Can be supported efficiently
Primary strength	Fast key lookup	Ordered data operations

Practical Hash Table Example

Imagine an application that needs to retrieve a user's profile using a unique username. A hash table can map the username directly to the corresponding profile.

const userProfiles = new Map([
  [
    'alice',
    {
      id: 101,
      role: 'Developer'
    }
  ],
  [
    'bob',
    {
      id: 102,
      role: 'Designer'
    }
  ]
]);

const username = 'alice';
const profile = userProfiles.get(username);

console.log(profile);
// { id: 101, role: 'Developer' }

This pattern is useful when the application frequently needs to retrieve information by a unique identifier.

Hash Tables for Frequency Counting

A hash table can also be used to count occurrences of values. The value becomes the key, while its count becomes the associated value.

function countFrequency(values) {
  const frequency = new Map();

  for (const value of values) {
    frequency.set(
      value,
      (frequency.get(value) || 0) + 1
    );
  }

  return frequency;
}

const values = [
  'JavaScript',
  'Python',
  'JavaScript',
  'Java',
  'Python'
];

console.log(countFrequency(values));

// JavaScript → 2
// Python → 2
// Java → 1

Hash Tables for Duplicate Detection

A hash-based set can track values that have already appeared. This allows duplicate detection without repeatedly scanning the entire input.

function containsDuplicate(values) {
  const seen = new Set();

  for (const value of values) {
    if (seen.has(value)) {
      return true;
    }

    seen.add(value);
  }

  return false;
}

console.log(
  containsDuplicate([10, 20, 30, 20])
);
// true

When Should You Use a Hash Table?

A hash table is a good fit when the main requirement is efficient access based on a key rather than maintaining data in sorted order.

Finding records using unique identifiers.
Counting frequencies.
Detecting duplicates.
Checking membership efficiently.
Grouping records by a key.
Implementing caches.
Storing configuration or lookup data.
Tracking visited vertices in graph algorithms.

When a Hash Table May Not Be the Right Choice

Hash tables are not designed to solve every data-access problem. Another data structure may be more suitable when ordering or range operations are central requirements.

When data must remain naturally sorted.
When efficient range queries are required.
When ordered traversal is a primary requirement.
When predictable worst-case performance is more important than average-case lookup.

Common Hash Table Mistakes

1. Assuming Every Lookup Is O(1)

O(1) describes typical average-case behavior under suitable conditions. A large number of collisions can make operations slower.

2. Ignoring Collisions

Different keys can map to the same bucket. Every hash table implementation needs a way to resolve such collisions.

3. Using a Poor Hash Function

If a hash function distributes many keys into a small number of buckets, collision rates can increase and performance can degrade.

4. Ignoring Load Factor

As a table becomes crowded, collisions can become more frequent. Resizing helps maintain an appropriate distribution of entries.

5. Expecting Sorted Data

A standard hash table is optimized for key-based access rather than sorted traversal. Choose an ordered data structure when ordering is a core requirement.

Hash Table Interview Questions

Hash tables are frequently used in coding interviews because they can reduce many lookup-based problems from quadratic approaches to linear-time approaches.

Common interview patterns include:

Frequency counting.
Two-sum and complement lookup.
Duplicate detection.
Grouping values by a key.
Finding the first unique or repeated value.
Tracking visited states.
Memoization and caching.

Hash Table vs Hash Map vs Hash Set

These terms are related but are often used to describe different abstractions.

Term	Typical Purpose
Hash table	Underlying key-based storage technique/data structure
Hash map	Key-value mapping abstraction
Hash set	Stores unique values using hashing

Key Takeaways

A hash table stores data using key-value pairs.
A hash function converts a key into a hash value used to determine a bucket.
Hash collisions occur when different keys map to the same bucket.
Separate chaining and open addressing are common collision-resolution techniques.
Load factor describes how full a hash table is.
Hash tables may resize and rehash entries as they become crowded.
Search, insertion, and deletion are typically O(1) on average.
The worst-case complexity of basic hash-table operations can be O(n).
JavaScript provides Map and Set for common hash-based use cases.
Hash tables are widely used for lookup, caching, frequency counting, duplicate detection, and graph algorithms.

Topics

Hash Table Data Structure Explained