Module 7: Hash Tables & Hashing

Course Navigation

Hash tables, functions, collision resolution, and applications

Overall Progress0%

0 of 4 completed

3-4 hours

Foundations of DSA

Memory & Efficiency

Arrays & Memory Fundamentals

Stacks & Queues

Linked Lists

Trees & Hierarchical Structures

Graph Theory & Algorithms

Hash Tables & HashingCurrent

Dynamic Programming

Sorting & Searching

Module Progress

Section 2 of 4

Module Stats

Total Sections:4

Estimated Time:3-4 hours

Difficulty:Advanced

Progress:0%

Hash Table Basics Hash Functions Collision Resolution Hash Table Applications

Back to Module 7

Lesson 2 of 4

Hash Functions

Deep dive into different hash function implementations and their characteristics

Interactive Hash Function Demo

Input Key

Table Size (m)

Hash Results

Division Method:Index 6

Multiplication Method:Index 2

Universal Hashing:Index 6

Division Method

h(k) = k mod m

The division method is the simplest hash function. It takes the key value and returns the remainder when divided by the table size.

Implementation Steps:

Convert string key to numeric value (sum of ASCII values)
Apply modulo operation with table size
Result is the hash table index

Advantages

• Very fast computation
• Simple to understand
• Memory efficient

Disadvantages

• Poor distribution for certain patterns
• Sensitive to table size choice
• Clustering with sequential keys

Best Practices

Choose Prime Table Sizes

Prime numbers help distribute keys more evenly and reduce clustering.

Avoid Powers of 2

Powers of 2 can lead to poor distribution for certain key patterns.

Consider Key Distribution

Analyze your key patterns to choose appropriate table sizes.

Multiplication Method

h(k) = ⌊m(kA mod 1)⌋
where A ≈ 0.618 (golden ratio)

The multiplication method multiplies the key by a constant A (0 < A < 1), extracts the fractional part, and multiplies by the table size.

Key Features:

• Uses the golden ratio (φ - 1 ≈ 0.618) for optimal distribution
• Less sensitive to table size choice
• Good performance with many key patterns
• Fractional part provides randomization

Step-by-Step Example

Step 1: k = 123, A = 0.618

Step 2: k × A = 123 × 0.618 = 76.014

Step 3: Fractional part = 0.014

Step 4: m × 0.014 = 7 × 0.014 = 0.098

Result: ⌊0.098⌋ = 0

Universal Hashing

h(k) = ((ak + b) mod p) mod m
where a, b are random, p is prime

Universal hashing uses a family of hash functions with random coefficients, providing theoretical guarantees against worst-case behavior.

Theoretical Guarantees:

• For any two keys x ≠ y: Pr[h(x) = h(y)] ≤ 1/m
• Expected collisions are minimized
• Resilient against adversarial input patterns
• Performance guarantees regardless of key distribution

Implementation Details

Random Selection

Choose random values for a and b at hash table creation time.

Prime Choice

Select prime p larger than the universe of possible keys.

Collision Handling

Even with collisions, expected performance remains optimal.

Method Comparison

Method	Computation	Distribution	Best Use Case
Division	Fastest	Variable	Simple applications with prime table sizes
Multiplication	Medium	Good	General purpose with flexible table sizes
Universal	Slowest	Guaranteed	Security-critical or adversarial environments

Hash Table Basics

Collision Resolution

Division Method

h(k) = k mod m

The division method is the simplest hash function. It takes the key value and returns the remainder when divided by the table size.

Implementation Steps:

Convert string key to numeric value (sum of ASCII values)
Apply modulo operation with table size
Result is the hash table index

Advantages

• Very fast computation
• Simple to understand
• Memory efficient

Disadvantages

• Poor distribution for certain patterns
• Sensitive to table size choice
• Clustering with sequential keys

Best Practices

Choose Prime Table Sizes

Prime numbers help distribute keys more evenly and reduce clustering.

Avoid Powers of 2

Powers of 2 can lead to poor distribution for certain key patterns.

Consider Key Distribution

Analyze your key patterns to choose appropriate table sizes.

Multiplication Method

h(k) = ⌊m(kA mod 1)⌋
where A ≈ 0.618 (golden ratio)

The multiplication method multiplies the key by a constant A (0 < A < 1), extracts the fractional part, and multiplies by the table size.

Key Features:

• Uses the golden ratio (φ - 1 ≈ 0.618) for optimal distribution
• Less sensitive to table size choice
• Good performance with many key patterns
• Fractional part provides randomization

Step-by-Step Example

Step 1: k = 123, A = 0.618

Step 2: k × A = 123 × 0.618 = 76.014

Step 3: Fractional part = 0.014

Step 4: m × 0.014 = 7 × 0.014 = 0.098

Result: ⌊0.098⌋ = 0

Universal Hashing

h(k) = ((ak + b) mod p) mod m
where a, b are random, p is prime

Universal hashing uses a family of hash functions with random coefficients, providing theoretical guarantees against worst-case behavior.

Theoretical Guarantees:

• For any two keys x ≠ y: Pr[h(x) = h(y)] ≤ 1/m
• Expected collisions are minimized
• Resilient against adversarial input patterns
• Performance guarantees regardless of key distribution

Implementation Details

Random Selection

Choose random values for a and b at hash table creation time.

Prime Choice

Select prime p larger than the universe of possible keys.

Collision Handling

Even with collisions, expected performance remains optimal.

Method

Computation

Distribution

Best Use Case

Division

Fastest

Variable

Simple applications with prime table sizes

Multiplication

Medium

Good

General purpose with flexible table sizes

Universal

Slowest

Guaranteed

Security-critical or adversarial environments