Hash Table Concept and Hash Functions in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this hash function simulation?

Consider a simple hash function that sums the ASCII values of characters in a string and then takes modulo 10. What is the output of the hash function for the key 'abc'?

DSA Typescript

function simpleHash(key: string): number {
  let sum = 0;
  for (let i = 0; i < key.length; i++) {
    sum += key.charCodeAt(i);
  }
  return sum % 10;
}

console.log(simpleHash('abc'));

A 6

B 8

C 2

D 4

💡 Hint

Add ASCII codes of 'a', 'b', and 'c' then take modulo 10.

The ASCII codes are: 'a' = 97, 'b' = 98, 'c' = 99. Sum is 97 + 98 + 99 = 294. 294 % 10 = 4.

❓ Predict Output

intermediate

What is the output after inserting keys in a hash table with chaining?

A hash table uses chaining to handle collisions. The hash function is key % 5. Insert keys 12, 7, 22, 17, 5. What is the state of the hash table buckets after all insertions?

DSA Typescript

const hashTable: number[][] = [[], [], [], [], []];
function hash(key: number): number {
  return key % 5;
}
const keys = [12, 7, 22, 17, 5];
for (const key of keys) {
  hashTable[hash(key)].push(key);
}
console.log(hashTable);

A [[5], [], [12, 7, 22, 17], [], []]

B [[], [7, 17], [12, 22], [], [5]]

C [[], [7, 17], [], [12, 22], [5]]

D [[5], [7, 17], [12, 22], [], []]

💡 Hint

Calculate key % 5 for each key and place in corresponding bucket.

12 % 5 = 2 → bucket 2: [12]

7 % 5 = 2 → bucket 2: [12, 7]

22 % 5 = 2 → bucket 2: [12, 7, 22]

17 % 5 = 2 → bucket 2: [12, 7, 22, 17]

5 % 5 = 0 → bucket 0: [5]

Final state: [[5], [], [12, 7, 22, 17], [], []]

🔧 Debug

advanced

What error does this hash function code produce?

Identify the error when running this TypeScript hash function code.

DSA Typescript

function hash(key: string): number {
  let hashValue = 0;
  for (let i = 0; i < key.length; i++) {
    hashValue += key.charCodeAt(i);
  }
  return hashValue % 10;
}
console.log(hash('test'));

A SyntaxError: Unexpected token

B TypeError: Cannot read property 'charCodeAt' of undefined

C Output: 4

D Output: 5

💡 Hint

Check the loop condition and string indexing.

The loop runs from i = 0 to i <= key.length, which means it tries to access key.charCodeAt(key.length), which is undefined.

Calling charCodeAt on undefined causes a TypeError.

🧠 Conceptual

advanced

Which property is NOT essential for a good hash function?

Select the property that is NOT essential for a hash function used in hash tables.

A Deterministic output for the same input

B Uniform distribution of hash values

C Ability to reverse the hash to original key

D Fast computation time

💡 Hint

Think about what a hash function is supposed to do, not undo.

A good hash function must always produce the same output for the same input (deterministic), distribute keys uniformly to avoid collisions, and be fast.

It does NOT need to be reversible; in fact, reversibility is not required and often not possible.

🚀 Application

expert

What is the final state of the hash table after these operations?

A hash table with size 7 uses open addressing with linear probing. The hash function is key % 7. Insert keys 10, 20, 15, 7, 32 in order. What is the final array state?

DSA Typescript

const size = 7;
const table: (number | null)[] = Array(size).fill(null);
function hash(key: number): number {
  return key % size;
}
function insert(key: number) {
  let idx = hash(key);
  while (table[idx] !== null) {
    idx = (idx + 1) % size;
  }
  table[idx] = key;
}
[10, 20, 15, 7, 32].forEach(insert);
console.log(table);

A [7, 15, null, 10, 32, null, 20]

B [10, 20, 15, 7, 32, null, null]

C [10, null, 20, 15, 7, 32, null]

D [10, null, null, 20, 15, 7, 32]

💡 Hint

Calculate initial index and probe linearly until empty slot found.

Insert 10: 10%7=3 → table[3]=10. Table: [n,n,n,10,n,n,n]

Insert 20: 20%7=6 → table[6]=20. [n,n,n,10,n,n,20]

Insert 15: 15%7=1 → table[1]=15. [n,15,n,10,n,n,20]

Insert 7: 7%7=0 → table[0]=7. [7,15,n,10,n,n,20]

Insert 32: 32%7=4 → table[4]=32. [7,15,n,10,32,n,20]

Final: [7, 15, null, 10, 32, null, 20]

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