Hash Table Concept and Hash Functions in DSA Typescript - Deep Dive

Overview - Hash Table Concept and Hash Functions

What is it?

A hash table is a way to store data so you can find it very quickly. It uses a special function called a hash function to turn keys (like names or numbers) into an index where the data is kept. This lets you add, find, or remove items fast without searching everything. Hash functions help spread data evenly to avoid crowding in one spot.

Why it matters

Without hash tables, finding data in large collections would be slow because you'd have to look through everything one by one. Hash tables make searching almost instant, which powers many apps like phonebooks, databases, and caches. They help computers work faster and handle lots of data smoothly.

Where it fits

Before learning hash tables, you should understand arrays and basic data storage. After this, you can learn about collision handling, advanced hashing techniques, and other data structures like trees and graphs that build on fast data access.

Mental Model

Core Idea

A hash table uses a hash function to turn a key into an index, letting you store and find data quickly by jumping directly to its spot.

Think of it like...

Imagine a library where each book has a unique code. Instead of searching every shelf, you use the code to go straight to the exact shelf and position where the book is kept.

Hash Table Structure:

Key: "apple"  -> Hash Function -> Index 3
Key: "banana" -> Hash Function -> Index 7

┌─────────────┐
│ Index 0     │ -> Empty
│ Index 1     │ -> Empty
│ Index 2     │ -> Empty
│ Index 3     │ -> "apple" data
│ Index 4     │ -> Empty
│ Index 5     │ -> Empty
│ Index 6     │ -> Empty
│ Index 7     │ -> "banana" data
└─────────────┘

Build-Up - 6 Steps

1

Foundation

Understanding Key-Value Storage

Concept: Learn what key-value pairs are and why they are useful for storing data.

A key-value pair is like a label and its content. For example, a phonebook entry has a name (key) and a phone number (value). Storing data this way helps you find the value if you know the key.

Result

You understand that data can be stored as pairs, making it easier to look up information by its label.

Knowing key-value pairs is the base for hash tables because they organize data by keys for quick access.

2

Foundation

What is a Hash Function?

Concept: Introduce the hash function as a tool to convert keys into numbers (indexes).

A hash function takes a key like a word or number and turns it into a number within a fixed range. This number points to where the data will be stored in the hash table. For example, hashing "apple" might give 3, so we store "apple" at index 3.

Result

You see how keys become indexes, allowing direct access to data spots.

Understanding hash functions is crucial because they map keys to storage locations, enabling fast data retrieval.

3

Intermediate

Handling Collisions in Hash Tables

🤔Before reading on: do you think two different keys can have the same index? Commit to yes or no.

Concept: Learn that different keys can produce the same index, causing collisions, and see basic ways to handle them.

Sometimes, two keys hash to the same index. This is called a collision. To fix this, we can use methods like chaining, where each index holds a list of items, or open addressing, where we find another empty spot.

Result

You understand collisions happen and basic strategies to keep data organized despite them.

Knowing collisions are normal helps you appreciate why hash tables need extra logic to keep fast access reliable.

4

Intermediate

Designing Good Hash Functions

🤔Before reading on: do you think any function that returns a number can be a hash function? Commit to yes or no.

Concept: Explore what makes a hash function good: spreading keys evenly and being fast to compute.

A good hash function spreads keys evenly across the table to avoid clustering. It should also be quick to calculate. For example, summing character codes and using modulo with table size is simple but can cause clusters if keys are similar.

Result

You learn criteria for choosing or creating hash functions that keep hash tables efficient.

Understanding hash function quality prevents slowdowns caused by uneven data distribution.

5

Advanced

Implementing a Hash Table in TypeScript

🤔Before reading on: do you think a hash table can store any type of key directly? Commit to yes or no.

Concept: See how to build a hash table with a hash function, storage array, and collision handling in TypeScript.

We create a class with an array to hold data. The hash function converts string keys to indexes. We use chaining with arrays at each index to store multiple items if collisions happen. Methods include set(key, value), get(key), and remove(key).

Result

You get a working hash table that stores and retrieves data quickly, handling collisions safely.

Building a hash table from scratch shows how all parts work together and prepares you for real coding tasks.

6

Expert

Performance and Limitations of Hash Tables

🤔Before reading on: do you think hash tables always guarantee constant time operations? Commit to yes or no.

Concept: Understand the average and worst-case performance of hash tables and when they might slow down.

Hash tables usually give O(1) time for insert, search, and delete. But if many collisions happen, operations degrade to O(n). Choosing a good hash function and resizing the table when it gets full helps keep performance high.

Result

You grasp when hash tables perform well and when they can become slow.

Knowing performance limits helps you decide when hash tables are the right tool and how to maintain their speed.

Under the Hood

Internally, a hash table uses an array and a hash function. The hash function converts keys into array indexes. When collisions occur, the table stores multiple items at the same index using linked lists or arrays (chaining) or finds alternative indexes (open addressing). The table may resize and rehash keys to keep operations fast as it grows.

Why designed this way?

Hash tables were designed to provide fast average-time data access by avoiding linear searches. Early designs balanced simplicity and speed, choosing arrays for direct access and hash functions for mapping keys. Alternatives like trees offer ordered data but slower average access, so hash tables fill the need for quick lookups without order.

Hash Table Internal Flow:

Key -> Hash Function -> Index
          │
          ▼
┌─────────────────────┐
│ Array of Buckets     │
│ ┌───────────────┐   │
│ │ Bucket 0      │ -> Empty
│ │ Bucket 1      │ -> List: (key1,value1) -> (key2,value2)
│ │ Bucket 2      │ -> Empty
│ │ Bucket 3      │ -> List: (key3,value3)
│ │ ...           │
│ └───────────────┘   │
└─────────────────────┘

Myth Busters - 4 Common Misconceptions

Quick: do you think hash tables keep data in sorted order? Commit to yes or no.

Common Belief: Hash tables store data in sorted order by keys.

Reality: Hash tables do not keep data sorted; they focus on fast access by key, not order.

Why it matters: Assuming sorted order can lead to wrong results when order matters, causing bugs in programs that expect sorted data.

Quick: do you think a perfect hash function exists for all possible keys? Commit to yes or no.

Common Belief: There is a hash function that never causes collisions for any set of keys.

Reality: No perfect hash function exists for all keys; collisions are inevitable with limited table size.

Why it matters: Expecting no collisions can cause ignoring collision handling, leading to data loss or errors.

Quick: do you think hash tables always have constant time operations no matter what? Commit to yes or no.

Common Belief: Hash tables always perform insert, search, and delete in constant time.

Reality: In worst cases with many collisions, operations degrade to linear time.

Why it matters: Ignoring worst-case scenarios can cause performance issues in critical applications.

Quick: do you think any function that returns a number can be used as a hash function? Commit to yes or no.

Common Belief: Any function that returns a number from a key is a good hash function.

Reality: A good hash function must distribute keys evenly and be fast; arbitrary functions may cause clustering.

Why it matters: Using poor hash functions leads to slow lookups and inefficient storage.

Expert Zone

1

The choice of hash function affects not just speed but also security, as weak functions can be exploited for denial-of-service attacks.

2

Dynamic resizing of hash tables involves rehashing all keys, which is costly but necessary to maintain performance.

3

Open addressing collision methods require careful probing sequences to avoid clustering and maintain efficiency.

When NOT to use

Hash tables are not ideal when data needs to be kept in sorted order or when memory is very limited. In such cases, balanced trees or skip lists are better alternatives.

Production Patterns

In production, hash tables are used in caches, symbol tables in compilers, and database indexing. They often combine with other structures for hybrid solutions, like hash maps with linked lists for order preservation.

Connections

Balanced Binary Search Trees

Alternative data structure for key-value storage with ordered keys.

Understanding hash tables helps appreciate why trees are chosen when order matters despite slower average access.

Cryptographic Hash Functions

Specialized hash functions designed for security rather than speed or distribution.

Knowing general hash functions clarifies why cryptographic hashes have different goals and properties.

Cache Memory in Computer Architecture

Both use hashing concepts to quickly locate data in limited storage.

Recognizing hashing in hardware caches shows how fundamental the idea is across computing layers.

Common Pitfalls

#1 Ignoring collision handling causes data overwrite.

Wrong approach:

class HashTable {
private table: (string | null)[] = new Array(10).fill(null);
hash(key: string): number {
return key.length % 10;
}
set(key: string, value: string) {
const index = this.hash(key);
this.table[index] = value; // overwrites existing data
}
get(key: string): string | null {
const index = this.hash(key);
return this.table[index];
}
}

Correct approach:

class HashTable {
private table: Map = new Map();
hash(key: string): number {
return key.length % 10;
}
set(key: string, value: string) {
const index = this.hash(key);
if (!this.table.has(index)) {
this.table.set(index, []);
}
const bucket = this.table.get(index)!;
const found = bucket.findIndex(item => item[0] === key);
if (found >= 0) {
bucket[found][1] = value;
} else {
bucket.push([key, value]);
}
}
get(key: string): string | null {
const index = this.hash(key);
const bucket = this.table.get(index);
if (!bucket) return null;
const item = bucket.find(item => item[0] === key);
return item ? item[1] : null;
}
}

Root cause:

Not handling collisions means new data can overwrite existing data at the same index, losing information.

#2 Using a poor hash function causing clustering.

Wrong approach:

hash(key: string): number {
return 1; // returns same index for all keys
}

Correct approach:

hash(key: string): number {
let hash = 0;
for (const char of key) {
hash += char.charCodeAt(0);
}
return hash % 10;
}

Root cause:

A hash function that returns the same index for all keys causes all data to cluster, degrading performance.

#3 Assuming hash tables keep keys sorted.

Wrong approach:

const keys = Object.keys(hashTable);
keys.sort(); // expecting keys to be already sorted in hash table

Correct approach:

const keys = Object.keys(hashTable);
keys.sort(); // explicitly sort keys when order is needed

Root cause:

Hash tables do not maintain order; sorting must be done separately if needed.

Key Takeaways

Hash tables store data as key-value pairs using a hash function to find storage indexes quickly.

Collisions are normal and must be handled to avoid data loss or slowdowns.

Good hash functions spread keys evenly and are fast to compute, keeping operations efficient.

Hash tables offer fast average-time access but can degrade if poorly designed or overloaded.

They are best used when quick lookup is needed without concern for data order.

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