Hash Table Concept and Hash Functions in DSA Javascript - Execution Trace

Concept Flow - Hash Table Concept and Hash Functions

Input: Key

↓

Apply Hash Function

↓

Get Index in Array

↓

Store or Retrieve Value at Index

↓

Handle Collisions if Needed

↓

Return Value or Store New Entry

The key is converted by a hash function into an index, which points to a place in an array where the value is stored or retrieved.

Execution Sample

DSA Javascript

function simpleHash(key, size) {
  let hash = 0;
  for (let char of key) {
    hash += char.charCodeAt(0);
  }
  return hash % size;
}

const index = simpleHash('cat', 10);

This code calculates a simple hash index for the key 'cat' in an array of size 10.

Execution Table

Step	Operation	Key	Hash Calculation	Index (Hash % Size)	Array State (Index: Value)
1	Start hashing	cat	hash=0	N/A	{}
2	Add 'c' char code	cat	hash=0+99=99	N/A	{}
3	Add 'a' char code	cat	hash=99+97=196	N/A	{}
4	Add 't' char code	cat	hash=196+116=312	N/A	{}
5	Calculate index	cat	hash=312	312 % 10 = 2	{}
6	Store value at index	cat	hash=312	2	{2: 'value'}
7	Retrieve value at index	cat	hash=312	2	{2: 'value'}
8	End	cat	hash=312	2	{2: 'value'}

💡 Hash function completed and index calculated; value stored and retrieved at index 2.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
hash	0	99	196	312	312	312
index	N/A	N/A	N/A	N/A	2	2
array	{}	{}	{}	{}	{}	{2: 'value'}

Key Moments - 3 Insights

Why do we use the modulo operator (%) with the hash value?

Because the hash value can be very large, modulo limits it to the array size, ensuring the index fits inside the array bounds as shown in step 5 of the execution_table.

What happens if two different keys produce the same index?

This is called a collision. The concept_flow shows 'Handle Collisions if Needed' which means we need extra steps like chaining or open addressing to store multiple values at the same index.

Why do we add character codes of each character in the key?

Adding character codes creates a numeric hash from a string key, which is necessary because arrays use numeric indexes, as demonstrated in steps 2 to 4.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the calculated index for key 'cat'?

A 3

B 2

C 5

D 7

💡 Hint

Check the 'Index (Hash % Size)' column at step 5 in the execution_table.

At which step does the hash variable first become 196?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look at the 'Hash Calculation' column in the execution_table for when hash equals 196.

If the array size changes from 10 to 5, what would be the new index for key 'cat'?

A 3

B 4

C 2

D 1

💡 Hint

Calculate 312 % 5 and compare with the 'Index (Hash % Size)' column in the execution_table.

Concept Snapshot

Hash Table stores key-value pairs using an array.
A hash function converts keys to numeric indexes.
Use modulo (%) to fit index inside array size.
Collisions happen when different keys map to same index.
Collision handling methods include chaining or open addressing.
Fast lookup depends on good hash functions and collision handling.

Full Transcript

A hash table stores data by converting keys into array indexes using a hash function. The example code adds character codes of each letter in the key 'cat' to get a hash number. Then it uses modulo with the array size to get a valid index. The value is stored at that index. If two keys get the same index, a collision occurs and extra steps are needed to handle it. The execution table shows each step of calculating the hash and index, and how the array changes. The variable tracker shows how the hash and index variables update. Key moments explain why modulo is used, what collisions are, and why character codes are added. The quiz tests understanding of the index calculation and hash updates. The snapshot summarizes the main points about hash tables and hash functions.

Practice

1. What is the main purpose of a hash function in a hash table?

easy

A. To convert a key into an index for storing data

B. To sort the keys in alphabetical order

C. To encrypt the data stored in the table

D. To count the number of elements in the table

Solution

1. Step 1: Understand the role of a hash function

   A hash function takes a key and converts it into a number that can be used as an index in the hash table.

2. Step 2: Identify the correct purpose

   Sorting keys or encrypting data is not the job of a hash function; it only maps keys to indexes.

3. Final Answer:

   To convert a key into an index for storing data -> Option A

4. Quick Check:

   Hash function = key to index [OK]

Hint: Hash functions map keys to indexes, not sort or encrypt [OK]

Common Mistakes:

• Thinking hash functions sort keys
• Confusing hash functions with encryption
• Believing hash functions count elements

2. Which of the following is the correct way to create an empty hash table (object) in JavaScript?

easy

A. const table = [];

B. const table = {};

C. const table = new Map();

D. const table = new HashTable();

Solution

1. Step 1: Recall JavaScript object syntax

   In JavaScript, an empty object is created using curly braces {} which can act as a hash table.

2. Step 2: Evaluate options

   const table = []; creates an array, not a hash table. const table = new Map(); creates a Map, which is a different structure. const table = new HashTable(); is invalid as HashTable is not a built-in class.

3. Final Answer:

   const table = {}; -> Option B

4. Quick Check:

   Empty hash table = {} [OK]

Hint: Use curly braces {} to create an empty object hash table [OK]

Common Mistakes:

• Using [] which creates an array, not a hash table
• Using Map() which is different from object
• Assuming HashTable is a built-in JavaScript class

3. What will be the output of the following code?

const hashTable = {};
hashTable['apple'] = 5;
hashTable['banana'] = 3;
hashTable['apple'] = 10;
console.log(hashTable['apple']);

medium

A. 10

B. 3

C. 5

D. undefined

Solution

1. Step 1: Understand key assignment in hash tables

   Assigning a value to an existing key updates the value stored at that key.

2. Step 2: Trace the code

   Initially, 'apple' is set to 5, then updated to 10. So, hashTable['apple'] will be 10.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Last assignment to 'apple' = 10 [OK]

Hint: Last value assigned to a key is stored [OK]

Common Mistakes:

• Thinking the first assigned value remains
• Confusing keys and values
• Expecting undefined for existing keys

4. Identify the error in the following code snippet that tries to use a hash function:

function hash(key) {
  return key.length % 10;
}
const table = {};
table[hash('cat')] = 'animal';
table[hash('dog')] = 'animal';
console.log(table['cat']);

medium

A. Using key.length causes runtime error

B. Cannot use numbers as keys in JavaScript objects

C. Accessing table['cat'] is incorrect; should use table[hash('cat')]

D. Hash function should return a string, not a number

Solution

1. Step 1: Understand how keys are stored and accessed

   The hash function returns a number used as a key in the table object.

2. Step 2: Check how the table is accessed

   The code tries to access table['cat'], but the key stored is a number from hash('cat'), so it should access table[hash('cat')].

3. Final Answer:

   Accessing table['cat'] is incorrect; should use table[hash('cat')] -> Option C

4. Quick Check:

   Access key must match stored key type [OK]

Hint: Access hash table with hashed key, not original key [OK]

Common Mistakes:

• Accessing with original key instead of hashed key
• Thinking keys must be strings only
• Assuming hash function causes error due to key.length

5. Given the hash function below, what is the best way to handle collisions when two keys produce the same hash?

function simpleHash(key) {
  let sum = 0;
  for (let char of key) {
    sum += char.charCodeAt(0);
  }
  return sum % 5;
}

Choose the best collision handling method.

hard

A. Increase the hash size to avoid collisions

B. Overwrite the existing value with the new one

C. Ignore the new key and keep the old value

D. Use chaining by storing multiple values in a list at the same index

Solution

1. Step 1: Understand collision in hash tables

   When two keys produce the same hash index, a collision occurs and must be handled to store both values.

2. Step 2: Evaluate collision handling methods

   Overwriting loses data, ignoring new keys is incorrect, increasing hash size alone doesn't solve collisions. Chaining stores multiple values in a list at the same index, preserving all data.

3. Final Answer:

   Use chaining by storing multiple values in a list at the same index -> Option D

4. Quick Check:

   Chaining handles collisions by lists [OK]

Hint: Use lists (chaining) to store multiple values at one index [OK]

Common Mistakes:

• Overwriting values causing data loss
• Ignoring new keys on collision
• Thinking increasing hash size removes all collisions