Hash Table Concept and Hash Functions in DSA Java

Mental Model

A hash table stores data by turning keys into numbers to find spots quickly. This lets us find things fast without searching everything.

Analogy: Imagine a library where each book has a special code that tells you exactly which shelf and spot to find it, so you don't have to look through all shelves.

Hash Table: [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Keys:       k1  k2  k3  null null null null null null null
Values:     v1  v2  v3  null null null null null null null
Hash Func: key -> index in table

Dry Run Walkthrough

Input: Insert keys: "cat", "dog", "bat" with values 1, 2, 3 into a hash table of size 5

Goal: Show how keys are converted to indexes and stored in the table

Step 1: Calculate hash for "cat" and find index 2, insert (cat,1)

[ ] [ ] [(cat,1)] [ ] [ ]

Why: We use the hash function to find where to put "cat" quickly

Step 2: Calculate hash for "dog" and find index 4, insert (dog,2)

[ ] [ ] [(cat,1)] [ ] [(dog,2)]

Why: Hash function gives index 4 for "dog", so we store it there

Step 3: Calculate hash for "bat" and find index 1, insert (bat,3)

[ ] [(bat,3)] [(cat,1)] [ ] [(dog,2)]

Why: Hash function gives index 1 for "bat", so we store it there

Result:

[ ] [(bat,3)] [(cat,1)] [ ] [(dog,2)]

Annotated Code

DSA Java

import java.util.*;

class HashTable {
    private static class Entry {
        String key;
        int value;
        Entry(String key, int value) {
            this.key = key;
            this.value = value;
        }
        public String toString() {
            return "(" + key + "," + value + ")";
        }
    }

    private Entry[] table;
    private int size;

    public HashTable(int size) {
        this.size = size;
        table = new Entry[size];
    }

    private int hash(String key) {
        int hashVal = 0;
        for (int i = 0; i < key.length(); i++) {
            hashVal += key.charAt(i);
        }
        return hashVal % size;
    }

    public void insert(String key, int value) {
        int index = hash(key);
        table[index] = new Entry(key, value); // direct insert, no collision handling
    }

    public void printTable() {
        for (int i = 0; i < size; i++) {
            if (table[i] != null) {
                System.out.print(table[i] + " ");
            } else {
                System.out.print("null ");
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        HashTable ht = new HashTable(5);
        ht.insert("cat", 1);
        ht.insert("dog", 2);
        ht.insert("bat", 3);
        ht.printTable();
    }
}

int hashVal = 0; for (int i = 0; i < key.length(); i++) { hashVal += key.charAt(i); } return hashVal % size;

Calculate hash by summing character codes and mod by table size

int index = hash(key); table[index] = new Entry(key, value);

Use hash to find index and insert entry directly

Output

null (bat,3) (cat,1) null (dog,2) 

Complexity Analysis

Time: O(1) average because hash function gives direct index to store or find data

Space: O(n) because we store n entries in an array of fixed size

vs Alternative: Compared to searching a list O(n), hash table gives faster average lookup O(1) but needs extra space and a good hash function

Edge Cases

Empty key string

Hash function returns 0, inserts at index 0

DSA Java

return hashVal % size;

Keys that produce same hash index (collision)

Current code overwrites previous entry at that index

DSA Java

table[index] = new Entry(key, value);

Table size smaller than number of keys

Some keys overwrite others due to collisions, no collision handling

DSA Java

table[index] = new Entry(key, value);

When to Use This Pattern

When you need very fast lookup by key and can convert keys to numbers, use a hash table with a hash function to jump directly to data location.

Common Mistakes

Mistake: Not using modulo operator to keep hash index inside table size
Fix: Always use modulo with table size to avoid index out of bounds

Mistake: Ignoring collisions causing data overwrite
Fix: Implement collision handling like chaining or probing to store multiple entries at same index

Summary

Stores key-value pairs using a function to convert keys into array indexes for fast access.

Use when you want quick insert and lookup by key without scanning all data.

The key insight is turning keys into numbers that point directly to where data lives.

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