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

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 Code

keys → integers

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

• For deletion: mark cell as AVAILABLE, not empty

Double Hashing - Implementation

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

Performance of Hashing

Average case - O(1)

For all search, insert, delete.

Map Time Complexity

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

Compression Function

maps integers → [0, N-1]

Seperate Chaining

• Has one function

• If collision occurs, store as a list within that cell

Quadratic Probing

When a collision occurs at the initial hash position h(k), apply the formula h(k, i) = (h(k) + i²) mod m for i = 1, 2, 3... until an empty slot is found.