Hashing in Data Structures: Introduction

What Is Hashing?

Hashing is a technique used in data structures to store and retrieve data efficiently. It transforms a key into an index or location where the associated data can be stored in a hash table.

Instead of searching through every stored element, a hash-based structure can use the key to calculate where the value should be located. Under good conditions, insertion, lookup, and deletion can be performed in approximately O(1) average time.

Why Is Hashing Useful?

Suppose an application stores thousands of users. If you need to find a user by an email address, scanning every user one by one can become inefficient as the number of users grows.

A hash table can use the email address as a key and calculate a location for that key. Instead of searching through every user, the structure can go directly to the calculated location.

Key
 ↓
Hash Function
 ↓
Hash Value
 ↓
Table Index
 ↓
Stored Value

What Is a Hash Table?

A hash table is a data structure that stores data using key-value relationships. It uses a hash function to determine where each key-value pair should be placed.

Conceptually, a hash table can be represented as an array of buckets:

Index     Data
-------------------------
0         empty
1         ("alice", 42)
2         empty
3         ("bob", 17)
4         empty
5         ("charlie", 29)

The actual implementation can be more sophisticated than a simple array. Hash tables need to handle collisions, resizing, deleted entries, and other implementation details.

Key and Value in Hashing

Hash-based structures commonly organize information as a key-value pair. The key identifies the data, while the value contains the associated information.

Key       Value
-------------------------
"user1"   "Alice"
"user2"   "Bob"
"user3"   "Charlie"

The key is passed to the hash function. The resulting hash value helps determine the location used by the hash table.

How Hashing Works

A simplified hashing process can be described in four stages.

1. Start with a key.
2. Pass the key through a hash function.
3. Convert the resulting hash value into a valid table index.
4. Store or retrieve the associated value at that location.

For example, imagine a simplified hash function that converts a string into a number and then uses the remainder operator to map it into a table with a fixed number of buckets.

hash("cat") = 27

table size = 10

index = 27 % 10
      = 7

"cat" → bucket 7

Real-world hash functions are generally more carefully designed than this simplified example.

What Is a Hash Function?

A hash function takes an input key and produces a hash value. A hash table then uses that value to determine a storage location.

A useful hash function should distribute keys across the available buckets effectively. Poor distribution can create many collisions and reduce the performance of the hash table.

Properties of a Useful Hash Function

• It should be deterministic: the same key should produce the same hash value.
• It should be efficient to calculate.
• It should distribute keys reasonably across the available table locations.
• It should reduce unnecessary clustering when used by a hash table.

Simple Hash Function Example

For learning purposes, a string can be converted into a numeric hash by combining the character codes.

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 is a teaching example rather than a production-quality general-purpose hash function. Its purpose is to demonstrate how a key can be transformed into a table index.

Hashing and Array Indexes

A hash table usually needs to convert a hash value into a valid index. If the table contains m buckets, a simplified approach is:

index = hashValue % tableSize

For example, if the hash value is 47 and the table contains 10 buckets:

47 % 10 = 7

The key would therefore be associated with bucket 7 in this simplified model.

What Is a Hash Collision?

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

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

Both keys map to bucket 4.

Collisions are normal in hash tables. There can be more possible keys than available table positions, so a good hash table must have a strategy for storing multiple keys that map to the same location.

Collision Handling

Two common collision-handling techniques are separate chaining and open addressing.

Separate Chaining

With separate chaining, each table bucket can contain multiple entries. A bucket may hold a linked list, array, or another collection of key-value pairs.

Bucket 4
   ↓
("cat", 10) → ("dog", 20) → ("fox", 30)

When looking up a key, the table calculates the bucket and then searches the entries stored in that bucket.

Open Addressing

With open addressing, entries are stored directly inside the table. When the calculated location is occupied, the implementation searches for another available location according to a probing strategy.

Common probing techniques include linear probing, quadratic probing, and double hashing.

Hashing Example in JavaScript

JavaScript provides built-in hash-based structures such as Map and Set. You normally do not need to implement the hash table yourself when building an application.

const users = new Map();

users.set('user101', 'Alice');
users.set('user102', 'Bob');
users.set('user103', 'Charlie');

console.log(users.get('user102'));
// Bob

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

users.delete('user101');

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

The Map abstraction handles the underlying hashing and collision management for you.

Hashing with JavaScript Set

A Set is useful when you need to store unique values rather than key-value pairs.

const skills = new Set();

skills.add('JavaScript');
skills.add('Python');
skills.add('JavaScript');

console.log(skills);
// Set(2) { 'JavaScript', 'Python' }

console.log(skills.has('Python'));
// true

Adding the same value more than once does not create a second distinct element in the set.

Hashing for Fast Lookup

One of the most common uses of hashing is fast membership or key lookup.

For example, suppose an application needs to determine whether a username already exists. A hash-based set can provide an efficient average-case membership check.

const registeredUsers = new Set([
  'alice',
  'bob',
  'charlie'
]);

const username = 'bob';

if (registeredUsers.has(username)) {
  console.log('Username already exists');
} else {
  console.log('Username is available');
}

Hashing for Frequency Counting

Hashing is also commonly used to count how often values occur. A map can store each value as a key and its frequency as the associated value.

const values = ['js', 'python', 'js', 'java', 'js', 'python'];

const frequency = new Map();

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

console.log(frequency);
// js → 3
// python → 2
// java → 1

This pattern appears frequently in data-structure problems involving duplicates, character counts, word frequencies, and grouping.

Hashing vs Direct Array Indexing

Direct array indexing is extremely efficient when the key is already a suitable integer index within a known range. Hashing becomes useful when keys are strings, large values, or objects that cannot directly serve as practical array indexes.

Average and Worst-Case Complexity

Hash tables are commonly described as having O(1) average-case complexity for insertion, lookup, and deletion when the table has a good distribution and an appropriate load factor.

The worst case can occur when many keys map to the same location and the collision-handling structure must examine many entries. Real implementations use techniques such as resizing and carefully designed hashing to maintain good average performance.

What Is Load Factor?

The load factor describes how full a hash table is. A simplified definition is:

Load Factor = Number of Stored Entries / Number of Buckets

As a table becomes crowded, collisions can become more frequent. Hash-table implementations commonly resize the underlying table when the load factor reaches an implementation-specific threshold.

Hash Table Resizing

A hash table may start with a relatively small number of buckets. As more elements are inserted, the implementation can allocate a larger table and redistribute existing entries.

Before resizing:

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


After resizing:

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

Existing entries generally need to be placed again because changing the table size can change the index calculated from their hash values. This resizing operation can temporarily require O(n) work, although hash-table insertion is still commonly described as O(1) amortized or average-case.

Hashing and Duplicate Detection

A hash set can detect duplicates efficiently because membership can be checked before adding a value.

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

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

    seen.add(value);
  }

  return false;
}

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

console.log(hasDuplicate([10, 20, 30, 40]));
// false

Hashing in Common Data Structures

Hashing is the underlying idea behind several commonly used structures and operations. Different programming languages expose these structures through different APIs.

Hashing vs Other Data Structures

Hashing is particularly useful when fast key-based lookup is more important than maintaining elements in sorted order.

When Should You Use Hashing?

Hashing is a natural choice when an application needs efficient lookup based on a key or needs to determine whether a value has already been seen.

• Finding users by unique identifiers.
• Checking whether a username or email already exists.
• Counting frequencies of values.
• Removing or detecting duplicates.
• Grouping related records by a key.
• Caching values using keys.
• Building indexes for fast application lookups.
• Tracking visited vertices in graph algorithms.

Hashing in Graph Algorithms

Hash-based structures are also useful in graph algorithms. For example, a Set can track visited vertices during BFS or DFS, while a Map can store adjacency lists or distances.

const visited = new Set();

visited.add('A');
visited.add('B');

console.log(visited.has('A'));
// true

const distance = new Map();

distance.set('A', 0);
distance.set('B', 1);

console.log(distance.get('B'));
// 1

This is one reason hashing is an important concept beyond standalone hash-table implementations.

Common Hashing Mistakes

1. Assuming Hashing Is Always O(1)

O(1) is the typical average-case expectation under suitable conditions. Poor distribution, excessive collisions, or other implementation details can lead to slower operations.

2. Ignoring Collisions

Different keys can map to the same bucket. A hash table must use a collision-resolution strategy such as chaining or open addressing.

3. Choosing a Poor Hash Function

A hash function that maps many keys to the same locations can create excessive collisions and degrade performance.

4. Confusing Hashing with Encryption

Hashing and encryption are different concepts. Hash functions used by data structures are designed primarily to map keys efficiently to locations. Encryption is designed for reversible protection of information using cryptographic techniques.

5. Expecting Sorted Order from a Hash Table

A standard hash table is designed for efficient key-based access, not for maintaining sorted order. If ordered traversal is required, a different data structure or an additional sorting step may be more appropriate.

Hashing Interview Concepts

Hashing appears frequently in data-structure and algorithm problems. Common patterns include using a map for frequency counting, a set for duplicate detection, and a map for remembering previously encountered values.

Input:
[2, 7, 11, 15]

Target:
9

Use a hash map:

2 → remember its index
7 → check whether 9 - 7 exists
11 → ...
15 → ...

Result:
2 + 7 = 9

This pattern is commonly known as the two-sum technique. The important idea is that hashing lets the algorithm remember previously encountered values and perform fast membership checks.

Hashing vs Hash Function vs Hash Table

These terms are related but describe different parts of the concept.

Key Takeaways

• Hashing maps keys to locations that can be used for efficient data access.
• A hash table stores key-value pairs using a hash function.
• A hash function converts a key into a hash value or table location.
• Different keys can produce the same location, creating hash collisions.
• Common collision-handling strategies include separate chaining and open addressing.
• Hash-table search, insertion, and deletion are typically O(1) on average.
• Load factor affects how frequently collisions occur and when resizing may be needed.
• JavaScript provides hash-based structures such as Map and Set.
• Hashing is widely used for frequency counting, duplicate detection, caching, lookup, and graph traversal.