Introductions
Hashing is a technique used to store and retrieve data using a key. A hash table uses a hash function to convert a key into an index where the value can be stored. These practice questions focus on practical hashing concepts such as creating hash indexes, inserting and retrieving values, handling collisions, chaining, checking duplicate values, counting frequencies, and implementing a simple hash table using JavaScript. Data Structure Hashing and Hash Tables practice questions with solutions help to understand the concepts.
Question 1: Create a Simple Hash Function
Question
Create a hash function that converts a numeric key into an array index. Use a hash table of size 10 and find the index for the keys:
15, 27, 42
Solution
A simple hash function can use the modulo operator:
key % tableSize
Create the function:
function hash(key, tableSize) {
return key % tableSize;
}
For 15:
15 % 10 = 5
For 27:
27 % 10 = 7
For 42:
42 % 10 = 2
Complete code:
function hash(key, tableSize) {
return key % tableSize;
}
console.log(hash(15, 10));
console.log(hash(27, 10));
console.log(hash(42, 10));
Output
5
7
2
Answer
The keys are mapped to these indexes:
15 → 5
27 → 7
42 → 2
The modulo operation is commonly used in simple hash functions to keep the index within the table size.
Question 2: Insert Key-Value Pairs into a Hash Table
Question
Create a hash table of size 10 and insert these key-value pairs:
101 → "Rahul"
102 → "Priya"
103 → "Amit"
Use the key to calculate the storage index.
Solution
Use:
key % 10
For key 101:
101 % 10 = 1
For key 102:
102 % 10 = 2
For key 103:
103 % 10 = 3
Create the table:
let table = new Array(10);
Insert the values:
table[101 % 10] = "Rahul";
table[102 % 10] = "Priya";
table[103 % 10] = "Amit";
Complete code:
let table = new Array(10);
table[101 % 10] = "Rahul";
table[102 % 10] = "Priya";
table[103 % 10] = "Amit";
console.log(table);
Output
[
<1 empty item>,
'Rahul',
'Priya',
'Amit',
<6 empty items>
]
Answer
The values are stored at:
101 → index 1 → Rahul
102 → index 2 → Priya
103 → index 3 → Amit
Question 3: Search for a Value Using a Hash Table
Question
A hash table stores the following values:
101 → Rahul
102 → Priya
103 → Amit
Search for key 102 and print the corresponding name.
Solution
The hash function is:
key % 10
For key 102:
102 % 10 = 2
Therefore, we check index 2.
let table = new Array(10);
table[101 % 10] = "Rahul";
table[102 % 10] = "Priya";
table[103 % 10] = "Amit";
let key = 102;
let index = key % 10;
console.log(table[index]);
Output
Priya
Answer
Key 102 maps to index 2, where "Priya" is stored.
Question 4: Find a Hash Collision
Question
Use a hash table of size 10 and calculate the indexes for:
15
25
35
Determine whether a collision occurs.
Solution
Use:
key % 10
For 15:
15 % 10 = 5
For 25:
25 % 10 = 5
For 35:
35 % 10 = 5
All three keys produce the same index:
15 → 5
25 → 5
35 → 5
Complete code:
function hash(key) {
return key % 10;
}
console.log("15:", hash(15));
console.log("25:", hash(25));
console.log("35:", hash(35));
Output
15: 5
25: 5
35: 5
Answer
A collision occurs because multiple keys are mapped to the same index.
15 ─┐
25 ─┼──→ Index 5
35 ─┘
A hash table needs a collision-handling technique when this happens.
Question 5: Handle Collisions Using Chaining
Question
Store these key-value pairs in a hash table of size 5:
10 → "A"
15 → "B"
20 → "C"
Use chaining to handle collisions.
Solution
Calculate the indexes:
10 % 5 = 0
15 % 5 = 0
20 % 5 = 0
All three keys go to index 0.
Instead of replacing the previous value, we can store multiple entries in an array at the same index.
Create the table:
let table = Array.from({ length: 5 }, () => []);
Insert the values:
table[10 % 5].push([10, "A"]);
table[15 % 5].push([15, "B"]);
table[20 % 5].push([20, "C"]);
Complete code:
let table = Array.from({ length: 5 }, () => []);
table[10 % 5].push([10, "A"]);
table[15 % 5].push([15, "B"]);
table[20 % 5].push([20, "C"]);
console.log(table);
The table contains:
Index 0:
[10, "A"]
[15, "B"]
[20, "C"]
Output
[
[ [10, "A"], [15, "B"], [20, "C"] ],
[],
[],
[],
[]
]
Answer
Chaining stores multiple key-value pairs at the same hash index instead of losing previously stored values.
Question 6: Count the Frequency of Elements Using Hashing
Question
Given the array:
[10, 20, 10, 30, 20, 10]
Use hashing to count how many times each number appears.
Solution
We can use an object as a simple hash table.
Start with:
let frequency = {};
For every number, increase its count.
let numbers = [10, 20, 10, 30, 20, 10];
let frequency = {};
for (let number of numbers) {
if (frequency[number]) {
frequency[number]++;
} else {
frequency[number] = 1;
}
}
console.log(frequency);
Let’s process the values:
10 → 1
20 → 1
10 → 2
30 → 1
20 → 2
10 → 3
Output
{
'10': 3,
'20': 2,
'30': 1
}
Answer
The frequency is:
10 → 3 times
20 → 2 times
30 → 1 time
This is one of the most common practical uses of hashing.
Question 7: Find Duplicate Elements Using Hashing
Question
Find all duplicate values in:
[10, 20, 30, 20, 40, 10, 50]
Use a hash table to solve the problem.
Solution
We can store every value we have already seen.
If a value is already present in the hash table, it is a duplicate.
let numbers = [10, 20, 30, 20, 40, 10, 50];
let seen = {};
let duplicates = [];
for (let number of numbers) {
if (seen[number]) {
duplicates.push(number);
} else {
seen[number] = true;
}
}
console.log(duplicates);
Let’s process the values:
10 → New
20 → New
30 → New
20 → Duplicate
40 → New
10 → Duplicate
50 → New
Output
[20, 10]
Answer
The duplicate values are:
20
10
Hashing allows us to check whether a value has already appeared.
Question 8: Find the First Repeated Element
Question
Find the first element that appears more than once in:
[5, 8, 2, 9, 8, 3, 2]
Solution
Use a hash table to remember values already seen.
let numbers = [5, 8, 2, 9, 8, 3, 2];
let seen = {};
for (let number of numbers) {
if (seen[number]) {
console.log("First repeated element:", number);
break;
}
seen[number] = true;
}
Step by step:
5 → New
8 → New
2 → New
9 → New
8 → Already exists
The first repeated element is 8.
Output
First repeated element: 8
Answer
The first repeated element is 8.
The search stops immediately after finding the first repeated value.
Question 9: Implement a Simple Hash Table Class
Question
Create a HashTable class with these operations:
set(key, value)
get(key)
Use a simple modulo-based hash function.
Solution
Create the class:
class HashTable {
constructor(size) {
this.size = size;
this.table = new Array(size);
}
}
Create a hash function:
hash(key) {
return key % this.size;
}
Create the set() operation:
set(key, value) {
let index = this.hash(key);
this.table[index] = value;
}
Create the get() operation:
get(key) {
let index = this.hash(key);
return this.table[index];
}
Complete code:
class HashTable {
constructor(size) {
this.size = size;
this.table = new Array(size);
}
hash(key) {
return key % this.size;
}
set(key, value) {
let index = this.hash(key);
this.table[index] = value;
}
get(key) {
let index = this.hash(key);
return this.table[index];
}
}
let hashTable = new HashTable(10);
hashTable.set(101, "Rahul");
hashTable.set(102, "Priya");
hashTable.set(103, "Amit");
console.log(hashTable.get(101));
console.log(hashTable.get(102));
console.log(hashTable.get(103));
The calculations are:
101 % 10 = 1 → Rahul
102 % 10 = 2 → Priya
103 % 10 = 3 → Amit
Output
Rahul
Priya
Amit
Answer
The class can store and retrieve values using keys and a hash function.
Question 10: Find the Most Frequent Element Using Hashing
Question
Find the element that appears most frequently in:
[4, 2, 4, 3, 2, 4, 5, 2]
If two values have the same frequency, return the first one with the highest frequency encountered during the scan.
Solution
First create a frequency hash table.
let numbers = [4, 2, 4, 3, 2, 4, 5, 2];
let frequency = {};
for (let number of numbers) {
if (frequency[number]) {
frequency[number]++;
} else {
frequency[number] = 1;
}
}
The frequency table becomes:
4 → 3
2 → 3
3 → 1
5 → 1
Now find the highest frequency:
let mostFrequent = numbers[0];
for (let number of numbers) {
if (frequency[number] > frequency[mostFrequent]) {
mostFrequent = number;
}
}
Complete code:
let numbers = [4, 2, 4, 3, 2, 4, 5, 2];
let frequency = {};
for (let number of numbers) {
if (frequency[number]) {
frequency[number]++;
} else {
frequency[number] = 1;
}
}
let mostFrequent = numbers[0];
for (let number of numbers) {
if (frequency[number] > frequency[mostFrequent]) {
mostFrequent = number;
}
}
console.log("Most frequent:", mostFrequent);
console.log("Frequency:", frequency[mostFrequent]);
The frequencies are:
4 → 3
2 → 3
3 → 1
5 → 1
Both 4 and 2 appear three times. Since 4 appears first in the original array, it remains the selected element.
Output
Most frequent: 4
Frequency: 3
Answer
The most frequent element is 4, with a frequency of 3.
Key Takeaways
- Hashing maps a key to an index using a hash function.
- A hash table stores data using keys and values.
- The modulo operator can create a simple hash index for numeric keys.
- A collision occurs when two or more keys produce the same hash index.
- Chaining is one technique for handling collisions.
- Hashing is useful for fast searching, counting, duplicate detection, and frequency calculations.
- Frequency counting is a common real-world application of hash tables.
- Hash tables can be implemented using arrays, objects, or dedicated data structures.
- A good hash function distributes keys across the table to reduce collisions.
- Average-case lookup, insertion, and deletion in a well-designed hash table can be O(1).
- Hash-table operations can become O(n) in the worst case when many keys collide.
- The size of the hash table affects how keys are distributed and how frequently collisions occur.
- Understanding collisions is essential for understanding how hash tables work internally.
FAQs
1. What is hashing in data structures?
Hashing is a technique that converts a key into an index using a hash function so that data can be stored and retrieved efficiently.
2. What is a hash table?
A hash table is a data structure that stores information using key-value pairs. A hash function determines where a key-value pair should be stored.
3. What is a hash function?
A hash function takes a key as input and produces an index used to locate the corresponding data in a hash table.
4. What is a collision in hashing?
A collision occurs when two or more different keys produce the same hash-table index.
5. How are collisions handled in hash tables?
Common collision-handling techniques include chaining and open addressing. Chaining stores multiple entries at the same index, while open addressing searches for another available position.
6. What is the average time complexity of a hash table?
Insertion, searching, and deletion can have an average time complexity of O(1) when the hash function distributes keys efficiently.
7. Where is hashing used in programming?
Hashing is used in dictionaries, caches, databases, symbol tables, frequency counting, duplicate detection, indexing, and many algorithms that require fast lookup.
Written by Shubhranshu Shekhar, who has trained 20000+ students in coding.
