Maps

Map - Definition

• Searchable collection of key-value pairs

• Duplicate keys not allowed

Map - Operations

• get(k)

• put(k, v)

• remove(k)

• size()

• isEmpty()

• entrySet(), keySet(), values() Return collections of x

Map - Implementation Options

• Unsorted list

• Hash table

Maps - List Implementation

• Stores entries in unsorted list

• get(k), put(k, v), remove(k) - O(n)

Maps - Hash Table Implementation

• Bucket Array: Array of size N, each cell stores key-value pairs

• Hash Function: Maps keys to integers in range [0, N-1]

Hash Function Components

Hash Code: maps keys → integers

Compression Function: maps integers → [0, N-1]

Types of Hash Codes

Memory Address: Uses object's memory address (default in Java)

Integer Cast: Reinterprets key bits as integer

Component Sum: Partitions key bits into fixed-length components and sums them

Types of Compression Functions

Division: h₂(y) = y mod N (N typically prime)

MAD (Multiply, Add, Divide): h₂(y) = [(ay + b) mod p] mod N

• p is prime > N; a,b are random integers in [0,p-1] with a > 0

Types of Collision Handling

1. Seperate chaining

2. Open addressing

   • Linear probing

   • Double hashing

   • Quadratic probing

Open Addressing - Implementation

• All entries stored directly in bucket array

• When collision occurs, use probing to find alternative cell

Linear Probing - Implementation

• Try cells sequentially: (i+1) mod N, (i+2) mod N, etc.

• Causes clustering (groups of occupied cells)

• For deletion: mark cell as AVAILABLE, not empty

Double Hashing - Implementation

• Uses secondary hash function h'(k) to determine step size

• Reduces clustering

Performance of Hashing

Worst case: O(n) when all keys collide

Expected: O(1) if load factor α = n/N is not close to 1

Expected probes for insertion with open addressing: 1/(1-α)

Use rehashing when load factor becomes too large (α > 0.5)

• Create new bucket array ~2× the size

• Reinsert all elements using new hash function