Hash Table Concept and Hash Functions in DSA Javascript

Mental Model

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

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

Hash Table:
[0] -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Hash Function: key -> index (0 to 4)

Dry Run Walkthrough

Input: Insert keys 'cat', 'dog', 'bird' with values 5, 7, 3 into a hash table of size 5 using a simple hash function

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

Step 1: Calculate hash for 'cat' and insert value 5

[0] -> null
[1] -> null
[2] -> ('cat',5) -> null
[3] -> null
[4] -> null

Why: We need to find the right slot for 'cat' using the hash function

Step 2: Calculate hash for 'dog' and insert value 7

[0] -> null
[1] -> null
[2] -> ('cat',5) -> null
[3] -> null
[4] -> ('dog',7) -> null

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

Step 3: Calculate hash for 'bird' and insert value 3

[0] -> null
[1] -> null
[2] -> ('cat',5) -> ('bird',3) -> null
[3] -> null
[4] -> ('dog',7) -> null

Why: Hash function gives index 2 for 'bird', so we store it there

Result:

[0] -> null
[1] -> null
[2] -> ('cat',5) -> ('bird',3) -> null
[3] -> null
[4] -> ('dog',7) -> null

Annotated Code

DSA Javascript

class HashTable {
  constructor(size) {
    this.size = size;
    this.buckets = Array(size).fill(null).map(() => []);
  }

  // Simple hash function: sum of char codes mod size
  hash(key) {
    let total = 0;
    for (const char of key) {
      total += char.charCodeAt(0);
    }
    return total % this.size;
  }

  set(key, value) {
    const index = this.hash(key); // get index from hash
    const bucket = this.buckets[index];
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket[i][1] = value; // update if key exists
        return;
      }
    }
    bucket.push([key, value]); // add new key-value pair
  }

  print() {
    for (let i = 0; i < this.size; i++) {
      const bucket = this.buckets[i];
      if (bucket.length === 0) {
        console.log(`[${i}] -> null`);
      } else {
        const pairs = bucket.map(pair => `('${pair[0]}',${pair[1]})`).join(' -> ');
        console.log(`[${i}] -> ${pairs} -> null`);
      }
    }
  }
}

// Driver code
const ht = new HashTable(5);
ht.set('cat', 5);
ht.set('dog', 7);
ht.set('bird', 3);
ht.print();

const index = this.hash(key);

compute index from key using hash function

for (let i = 0; i < bucket.length; i++) { if (bucket[i][0] === key) { bucket[i][1] = value; return; } }

check if key exists to update value

bucket.push([key, value]);

insert new key-value pair at computed index

Output

[0] -> null

[1] -> null

[2] -> ('cat',5) -> ('bird',3) -> null

[3] -> null

[4] -> ('dog',7) -> null

Complexity Analysis

Time: O(1) average because hash function gives direct index, but worst case O(n) if many keys collide

Space: O(n) because we store all key-value pairs in buckets

vs Alternative: Compared to arrays where search is O(n), hash tables give faster average lookup by using hashing

Edge Cases

Empty hash table

No keys stored, print shows all null buckets

DSA Javascript

for (let i = 0; i < this.size; i++) { const bucket = this.buckets[i]; if (bucket.length === 0) { console.log(`[${i}] -> null`); } }

Duplicate key insertion

Value for existing key is updated, no duplicate keys stored

DSA Javascript

if (bucket[i][0] === key) { bucket[i][1] = value; return; }

Keys causing hash collision

Multiple key-value pairs stored in same bucket array

DSA Javascript

bucket.push([key, value]);

When to Use This Pattern

When you need fast lookup by key and can use a function to convert keys to indexes, use a hash table with a hash function to store and find data quickly.

Common Mistakes

Mistake: Not handling collisions, causing overwriting or lost data
Fix: Use buckets (arrays) at each index to store multiple key-value pairs

Mistake: Using a poor hash function that causes many collisions
Fix: Use a hash function that spreads keys evenly across buckets

Summary

Stores key-value pairs using a hash function to find indexes quickly.

Use when you want fast insert and lookup by keys.

The key insight is turning keys into array indexes using a hash function to avoid searching all data.

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