Hash Table Concept and Hash Functions in DSA Java - 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. This index points to where the value is stored or retrieved in the array. Collisions are handled if multiple keys map to the same index.

Execution Sample

DSA Java

int hash = Math.abs(key.hashCode()) % array.length;
if (array[hash] == null) {
  array[hash] = value;
} else {
  // handle collision
}

This code calculates the hash index for a key and stores the value at that index, handling collisions if needed.

Execution Table

Step	Operation	Key	Hash Index	Array State	Collision Handling	Visual State
1	Calculate hash	apple	2	[null, null, null, null, null]	No	[null, null, null, null, null]
2	Check index 2	apple	2	[null, null, null, null, null]	No	[null, null, null, null, null]
3	Store value	apple	2	[null, null, 'apple:value', null, null]	No	[null, null, 'apple:value', null, null]
4	Calculate hash	banana	4	[null, null, 'apple:value', null, null]	No	[null, null, 'apple:value', null, null]
5	Check index 4	banana	4	[null, null, 'apple:value', null, null]	No	[null, null, 'apple:value', null, null]
6	Store value	banana	4	[null, null, 'apple:value', null, 'banana:value']	No	[null, null, 'apple:value', null, 'banana:value']
7	Calculate hash	grape	2	[null, null, 'apple:value', null, 'banana:value']	Yes	[null, null, 'apple:value', null, 'banana:value']
8	Collision at index 2	grape	2	[null, null, 'apple:value', null, 'banana:value']	Yes	[null, null, 'apple:value -> grape:value', null, 'banana:value']
9	Store value with chaining	grape	2	[null, null, 'apple:value -> grape:value', null, 'banana:value']	Yes	[null, null, 'apple:value -> grape:value', null, 'banana:value']
10	End	-	-	[null, null, 'apple:value -> grape:value', null, 'banana:value']	-	[null, null, 'apple:value -> grape:value', null, 'banana:value']

💡 All keys processed and stored with collision handled by chaining at index 2.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	Final
array	[null, null, null, null, null]	[null, null, 'apple:value', null, null]	[null, null, 'apple:value', null, 'banana:value']	[null, null, 'apple:value -> grape:value', null, 'banana:value']	[null, null, 'apple:value -> grape:value', null, 'banana:value']
hash	-	2	4	2	-
collision	No	No	No	Yes	-

Key Moments - 3 Insights

Why do two different keys sometimes map to the same index?

Because the hash function converts keys to a limited range of indexes, different keys can produce the same index, causing a collision as shown in steps 7-9.

How is the collision handled when two keys map to the same index?

In this example, collision is handled by chaining, which means storing multiple key-value pairs in a linked list at the same index, as seen in step 9.

Why do we use modulo (%) with array length in hash calculation?

Modulo ensures the hash index fits within the array size, preventing out-of-bound errors, as shown in step 1 and repeated for each key.

Visual Quiz - 3 Questions

Look at the execution table, what is the hash index for the key 'banana'?

A 2

B 4

C 0

D 3

💡 Hint

Check the 'Hash Index' column for the row where Operation is 'Calculate hash' and Key is 'banana'.

At which step does the collision occur?

A Step 6

B Step 9

C Step 7

D Step 3

💡 Hint

Look for the first row where 'Collision Handling' is 'Yes'.

If the array size was increased, how would the hash index for 'apple' change?

A It could change because modulo depends on array length

B It would always become 0

C It would stay the same

D It would become negative

💡 Hint

Recall that hash index is key.hashCode() % array.length, so changing array length affects the result.

Concept Snapshot

Hash Table stores key-value pairs using a hash function.
Hash function converts keys to array indexes.
Collisions happen when different keys map to same index.
Collision handled by chaining or open addressing.
Fast average lookup, insert, delete operations.
Modulo operator keeps index within array size.

Full Transcript

A hash table uses a hash function to convert a key into an index in an array. This index tells where to store or find the value. Sometimes, two keys produce the same index, causing a collision. We handle collisions by chaining, which links multiple values at the same index. The modulo operator ensures the index fits inside the array size. This structure allows fast data access by key.

Practice

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

easy

A. To encrypt the data stored in the table

B. To sort the keys in ascending order

C. To convert a key into an index for storing values

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 transforms it into an index number that points to a location in the hash table.

2. Step 2: Compare options with the hash function role

   Only To convert a key into an index for storing values describes converting a key into an index, which is the main purpose of a hash function.

3. Final Answer:

   To convert a key into an index for storing values -> Option C

4. Quick Check:

   Hash function = key to index [OK]

Hint: Hash function maps keys to indexes in the table [OK]

Common Mistakes:

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

2. Which of the following is the correct way to declare a HashMap in Java using built-in classes?

easy

A. Hashtable map = new Hashtable();

B. HashMap map = new HashMap<>();

C. HashTable map = new HashTable<>();

D. HashMap map = new HashMap();

Solution

1. Step 1: Identify correct class names and syntax

   Java's standard hash table class is HashMap (case-sensitive). Hashtable is also valid but legacy and requires type parameters.

2. Step 2: Check each option's syntax

   HashMap map = new HashMap<>(); uses correct generic syntax with HashMap. Hashtable map = new Hashtable(); misses generics. HashTable map = new HashTable<>(); uses wrong class name 'HashTable' (capital T). HashMap map = new HashMap(); reverses generic placement incorrectly.

3. Final Answer:

   HashMap map = new HashMap<>(); -> Option B

4. Quick Check:

   Correct Java HashMap syntax = HashMap map = new HashMap<>(); [OK]

Hint: Use HashMap with generics and diamond operator <> [OK]

Common Mistakes:

• Using wrong class name 'HashTable'
• Omitting generics for type safety
• Incorrect generic syntax placement

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

import java.util.HashMap;
public class Main {
  public static void main(String[] args) {
    HashMap map = new HashMap<>();
    map.put("apple", 10);
    map.put("banana", 20);
    map.put("apple", 30);
    System.out.println(map.get("apple"));
  }
}

medium

A. 30

B. 20

C. 10

D. null

Solution

1. Step 1: Understand put() behavior in HashMap

   When a key already exists, put() replaces the old value with the new one.

2. Step 2: Trace the put() calls for key "apple"

   First put("apple", 10) adds key with value 10. Second put("apple", 30) replaces value 10 with 30.

3. Final Answer:

   30 -> Option A

4. Quick Check:

   Last value for "apple" = 30 [OK]

Hint: Last put for a key overwrites previous value [OK]

Common Mistakes:

• Assuming values accumulate instead of overwrite
• Confusing keys and values
• Expecting null for existing keys

4. Identify the error in the following Java code that uses a hash table:

import java.util.HashMap;
public class Main {
  public static void main(String[] args) {
    HashMap map = new HashMap<>();
    map.put(1, "One");
    map.put(2, "Two");
    System.out.println(map.get("1"));
  }
}

medium

A. HashMap cannot store Integer keys

B. Missing import statement for HashMap

C. Incorrect syntax for put() method

D. Using wrong key type in get() method

Solution

1. Step 1: Check key types used in HashMap and get()

   The HashMap is declared with Integer keys. The get() method is called with a String "1" instead of Integer 1.

2. Step 2: Understand type mismatch effect

   Since keys are Integer, get("1") returns null because "1" (String) is not equal to 1 (Integer).

3. Final Answer:

   Using wrong key type in get() method -> Option D

4. Quick Check:

   Key type mismatch causes null result [OK]

Hint: Match key types exactly when using get() [OK]

Common Mistakes:

• Passing String key instead of Integer
• Ignoring type safety warnings
• Assuming automatic type conversion

5. You want to design a hash function for a hash table that stores student IDs (integers) as keys. Which of the following hash functions is best to minimize collisions for IDs mostly ranging from 1000 to 9999?

hard

A. hash(key) = key % 100

B. hash(key) = key % 10000

C. hash(key) = key / 1000

D. hash(key) = key % 10

Solution

1. Step 1: Analyze the key range and hash function outputs

   Keys range from 1000 to 9999. Using modulo 10 (hash(key) = key % 10) gives only 10 buckets, causing many collisions. Modulo 10000 (hash(key) = key % 10000) returns the key itself, which is too large for typical table size. Division by 1000 (hash(key) = key / 1000) gives values 1 to 9, only 9 buckets, too small.

2. Step 2: Evaluate modulo 100 (hash(key) = key % 100)

   Modulo 100 gives values from 0 to 99, creating 100 buckets. This spreads keys better and reduces collisions compared to options A and C.

3. Final Answer:

   hash(key) = key % 100 -> Option A

4. Quick Check:

   More buckets (100) reduce collisions best [OK]

Hint: Choose modulo near expected bucket count for spread [OK]

Common Mistakes:

• Choosing too few buckets causing collisions
• Using modulo equal to key range (too large)
• Using division that reduces bucket count too much