A hash table is a data structure that implements an associative array, mapping keys to values using a hash function to compute an index into an array of buckets or slots.

Key Properties:

• Average O(1) access time - Constant time operations
• Direct indexing - No sequential searching needed
• Dynamic sizing - Can grow and shrink as needed
• Key-value mapping - Associates unique keys with values

Hash Table Structure

Hash Functions

Division Method

Simple modular arithmetic approach

h(k) = k mod m

Example: h(123) = 123 mod 7 = 4

Pros:

• Simple to compute
• Fast execution

Cons:

• Poor performance with certain patterns
• Requires careful choice of m

Good Hash Function Properties

Deterministic

Same key always produces same hash value

Uniform Distribution

Keys spread evenly across hash table

Fast Computation

Efficient to calculate in constant time

Avalanche Effect

Small key changes produce large hash changes

Performance Analysis

Operation	Average Case	Worst Case	Best Case
Search	O(1)	O(n)	O(1)
Insert	O(1)	O(n)	O(1)
Delete	O(1)	O(n)	O(1)

Hash Functions