Hashing in Data Structures: Hash Maps and Collisions

Introduction to Hashing

Hashing is a technique used to store and retrieve data efficiently based on a key. It is commonly used when a problem requires frequent operations such as finding whether an element exists, inserting a new element, deleting an element, or counting how many times an element occurs.

For example, consider the array:

[2, 5, 2, 8, 5, 2]

If the task is to find how many times each number occurs, repeatedly scanning the entire array would require unnecessary work. Hashing provides a way to store the frequency of each element while traversing the array.

For the above array, the frequency information can be stored as:

2 → 3
5 → 2
8 → 1

Here, 2, 5, and 8 are the keys, while their frequencies are the values associated with those keys.

Why Is Hashing Used?

Many problems require repeatedly checking or updating information associated with a particular value.

For example:

• Checking whether an element exists in an array.

• Counting the frequency of each element.

• Finding the most frequent element.

• Counting distinct elements.

• Storing key-value relationships.

• Checking whether two elements or strings have already been seen.

• Quickly inserting or deleting elements.

Without hashing, these operations may require repeatedly traversing the entire array.

For example, to count the frequency of every element in:

[2, 5, 2, 8, 5, 2]

a simple approach would be to take each element and scan the array again to count its occurrences.

Hashing avoids this repeated scanning by maintaining the required information while processing the elements.

How Does Hashing Work?

The main idea behind hashing is to transform a key into an index or location where the corresponding information can be stored.

A hash function takes a key and produces a hash value.

For example, consider a simple hash function:

hash(key) = key % 10

For the values:

12, 25, 37

the hash values are:

12 % 10 = 2
25 % 10 = 5
37 % 10 = 7

These values can be used as positions in a hash table.

Hash Table

A hash table is a data structure used to store information using hashing.

It stores elements based on the result produced by the hash function. Depending on the problem, a hash table can store either a value itself or additional information associated with that value.

For frequency counting, the hash table can store:

Key → Frequency

For example:

Array: [2, 5, 2, 8, 5, 2]

Hash Table:

2 → 3
5 → 2
8 → 1

Here, the key represents the element and the value represents its frequency.

In programming, hash tables are commonly provided through data structures such as hash maps and hash sets.

Hash Set and Hash Map

Hashing is commonly used through two important data structures: hash set and hash map.

Hash Set

A hash set stores unique elements.

For example:

Input:  [2, 5, 2, 8, 5, 2]

Hash Set:

2
5
8

Duplicate values are stored only once.

Therefore, a hash set is useful when the main requirement is to determine whether an element exists or to count distinct elements.

Hash Map

A hash map stores data in the form of:

Key → Value

For example, while counting frequencies:

2 → 3
5 → 2
8 → 1

A hash map is useful when additional information needs to be associated with each key.

For example:

Element → Frequency
Character → Frequency
Student ID → Marks
Word → Count

Collision in Hashing

Different keys can sometimes produce the same hash value. This situation is called a collision.

For example, using:

hash(key) = key % 10

both 12 and 22 produce the same hash value:

12 % 10 = 2
22 % 10 = 2

Therefore, both keys are mapped to the same position.

Hash tables use techniques such as separate chaining and open addressing to handle collisions.

• Separate Chaining: Stores multiple elements that map to the same index in a linked list or another suitable data structure. Each index can therefore hold multiple elements, allowing collisions to be handled without searching for another empty position.

• Open Addressing: Stores all elements directly within the hash table. When a collision occurs, it searches for another empty position using a probing technique such as linear probing or quadratic probing.

The exact implementation can differ between programming languages and libraries, but the main idea remains the same: multiple keys that map to the same location must still be stored and retrieved correctly.

Search, Insert, and Delete in Hashing

Hash-based data structures are mainly useful because they provide efficient operations.

Search

The search operation checks whether a key is present.

For example, in:

Hash Set: {2, 5, 8}

searching for 5 finds the element directly through its hash-based location.

The average time complexity of searching in a hash table is: O(1)

Insert

The insert operation adds a new key or key-value pair to the hash table.

For example:

Hash Map:

2 → 3
5 → 2

Inserting:

8 → 1

adds a new key-value pair.

The average time complexity of insertion is: O(1)

Delete

The delete operation removes a key or key-value pair from the hash table.

For example:

Hash Set: {2, 5, 8}

After deleting 5:

{2, 8}

The average time complexity of deletion is: O(1)

These are average-case complexities. In the worst case, when many keys experience collisions, hash-table operations can take O(N) time.

Problems Based on Hashing

The following problems demonstrate some of the most common applications of hashing.

1. Highest Frequency Element

Given an integer array nums, find the element that occurs the maximum number of times in the array.

If multiple elements have the same highest frequency, return the element that appears first in the array.

2. Character Frequency

Given a string s, count the frequency of every character present in the string.

The frequency of each character represents the number of times it occurs in the string.

3. Count Distinct Elements

Given an integer array nums, count the number of distinct elements present in the array.

Each different value should be counted only once, regardless of how many times it appears.