Hash Table Concept and Hash Functions in DSA Typescript

Mental Model

A hash table stores data by turning keys into numbers to find values quickly. It uses a special function to do this conversion.

Analogy: Imagine a library where each book has a unique code made by a librarian. Instead of searching all shelves, you go directly to the shelf number from the code to find the book fast.

Keys: ["cat", "dog", "bird"]
Hash Function: key -> number
Hash Table:
[0] -> "cat"
[1] -> null
[2] -> "dog"
[3] -> "bird"
[4] -> null
[5] -> null

Dry Run Walkthrough

Input: Insert keys "cat", "dog", "bird" into an empty hash table of size 6 using a simple hash function: sum of character codes mod 6.

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

Step 1: Calculate hash for "cat": (99 + 97 + 116) % 6 = 312 % 6 = 0; store "cat" at index 0

[0] -> "cat"
[1] -> null
[2] -> null
[3] -> null
[4] -> null
[5] -> null

Why: We convert the key "cat" to an index to know where to store it.

Step 2: Calculate hash for "dog": (100 + 111 + 103) % 6 = 314 % 6 = 2; store "dog" at index 2

[0] -> "cat"
[1] -> null
[2] -> "dog"
[3] -> null
[4] -> null
[5] -> null

Why: We convert "dog" to index 2 to store it quickly.

Step 3: Calculate hash for "bird": (98 + 105 + 114 + 100) % 6 = 417 % 6 = 3; store "bird" at index 3

[0] -> "cat"
[1] -> null
[2] -> "dog"
[3] -> "bird"
[4] -> null
[5] -> null

Why: We convert "bird" to index 3 to store it quickly.

Result:

[0] -> "cat"
[1] -> null
[2] -> "dog"
[3] -> "bird"
[4] -> null
[5] -> null

Annotated Code

DSA Typescript

class HashTable {
  private size: number;
  private table: (string | null)[];

  constructor(size: number) {
    this.size = size;
    this.table = new Array(size).fill(null);
  }

  private hash(key: string): number {
    // sum character codes mod table size
    let sum = 0;
    for (const char of key) {
      sum += char.charCodeAt(0);
    }
    return sum % this.size;
  }

  insert(key: string): void {
    const index = this.hash(key);
    this.table[index] = key; // store key at hashed index
  }

  print(): void {
    for (let i = 0; i < this.size; i++) {
      console.log(`[${i}] -> ${this.table[i]}`);
    }
  }
}

// Driver code
const ht = new HashTable(6);
ht.insert("cat");
ht.insert("dog");
ht.insert("bird");
ht.print();

for (const char of key) { sum += char.charCodeAt(0); }

Calculate sum of character codes to convert key to a number

return sum % this.size;

Use modulo to fit number into table size as index

const index = this.hash(key);

Get index for key using hash function

this.table[index] = key;

Store key at computed index in the table

Output

[0] -> cat

[1] -> null

[2] -> dog

[3] -> bird

[4] -> null

[5] -> null

Complexity Analysis

Time: O(k) where k is key length because we sum character codes once per key

Space: O(n) where n is table size because we store keys in an array of fixed size

vs Alternative: Compared to searching a list (O(n)), hash table insertion is faster (O(1) average) because it uses direct indexing

Edge Cases

Empty key string

Hash function returns 0, stores key at index 0

DSA Typescript

for (const char of key) { sum += char.charCodeAt(0); }

Keys that produce same hash index (collision)

Current code overwrites previous key at that index (no collision handling)

DSA Typescript

this.table[index] = key;

Very long key string

Hash function sums all characters, still works but slower

DSA Typescript

for (const char of key) { sum += char.charCodeAt(0); }

When to Use This Pattern

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

Common Mistakes

Mistake: Not using modulo to keep index inside table size
Fix: Always use modulo operator on hash sum to get valid index

Mistake: Ignoring collisions causing data overwrite
Fix: Implement collision handling like chaining or open addressing

Summary

It stores data by converting keys into indexes using a hash function for quick access.

Use it when you want fast 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 sort the keys in ascending order

B. To count the number of elements in the table

C. To encrypt the stored data for security

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

Solution

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

   A hash function takes a key and converts it into a number called an index.

2. Step 2: Connect index to storage in hash table

   This index tells where to store or find the value in the hash table.

3. Final Answer:

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

4. Quick Check:

   Hash function = key to index [OK]

Hint: Hash function maps keys to storage spots [OK]

Common Mistakes:

• Thinking hash function sorts keys
• Confusing hash function with encryption
• Believing hash function counts elements

2. Which of the following is the correct way to declare a hash table (Map) in TypeScript?

easy

A. const map = new map();

B. const map = Map;

C. const map = new Map();

D. const map = new Map(); string, number;

Solution

1. Step 1: Recall TypeScript Map syntax

   In TypeScript, a Map is created with new Map().

2. Step 2: Check each option's syntax

   const map = new Map(); uses correct syntax: new Map(). Others have syntax errors or wrong usage.

3. Final Answer:

   const map = new Map(); -> Option C

4. Quick Check:

   Map declaration = new Map<Key, Value>() [OK]

Hint: Use new Map() to declare [OK]

Common Mistakes:

• Omitting 'new' keyword
• Using lowercase 'map' instead of 'Map'
• Incorrect generic syntax

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

const map = new Map();
map.set('apple', 5);
map.set('banana', 3);
map.set('apple', 10);
console.log(map.get('apple'));

medium

A. 10

B. Error

C. undefined

D. 5

Solution

1. Step 1: Understand Map set behavior

   Setting a key that already exists updates its value.

2. Step 2: Trace the code

   First 'apple' is set to 5, then updated to 10. So map.get('apple') returns 10.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Updated value = 10 [OK]

Hint: Last set value for key is stored [OK]

Common Mistakes:

• Assuming first value stays
• Thinking get returns undefined if key repeated
• Confusing Map with object property behavior

4. Identify the error in the following TypeScript code using a hash table:

const map = new Map();
map.set(1, 'one');
map.set(2, 'two');
console.log(map.get('1'));

medium

A. Missing parentheses in map.get call

B. Using string '1' instead of number 1 as key

C. Map keys must be strings only

D. Cannot mix number and string values in Map

Solution

1. Step 1: Check Map key type

   Map is declared with number keys, so keys must be numbers.

2. Step 2: Analyze map.get argument

   map.get('1') uses string '1', which does not match number 1 key, so returns undefined.

3. Final Answer:

   Using string '1' instead of number 1 as key -> Option B

4. Quick Check:

   Key type mismatch causes undefined [OK]

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

Common Mistakes:

• Assuming '1' and 1 are same keys
• Thinking Map keys must be strings
• Ignoring type mismatch errors

5. You want to design a hash function for strings that minimizes collisions for English words. Which approach is best?

hard

A. Multiply each character code by a prime number and sum, then modulo table size

B. Use the length of the string as the hash value

C. Sum the ASCII codes of all characters and take modulo table size

D. Use the first character's ASCII code only

Solution

1. Step 1: Understand collision minimization

   Good hash functions spread keys evenly to reduce collisions.

2. Step 2: Evaluate each approach

   Sum the ASCII codes of all characters and take modulo table size sums codes but can cause many collisions (e.g., 'abc' and 'cab'). Use the length of the string as the hash value uses length only, very poor. Use the first character's ASCII code only uses first char only, also poor. Multiply each character code by a prime number and sum, then modulo table size uses weighted sum with primes, better distribution.

3. Final Answer:

   Multiply each character code by a prime number and sum, then modulo table size -> Option A

4. Quick Check:

   Weighted sum with primes = better hash [OK]

Hint: Use prime multipliers for better hash spread [OK]

Common Mistakes:

• Using simple sums causing collisions
• Ignoring character positions
• Using string length as hash