Associative Arrays

Overview

An associative array can also be known as a map, symbol table or dictionary.

Hash Tables

A hash table is a type of associative array where a hash is calculated from a given key, and the key’s value is stored at the memory address pointed to by the key’s hash.

Complexity

The table below shows the time complexity of common hash table operations. The worst case occurs when all keys hash to the same bucket, degrading lookups to a linear scan.

Operation	Average Case	Worst Case
Lookup	$\mathcal{O}(1)$	$\mathcal{O}(n)$
Insertion	$\mathcal{O}(1)$	$\mathcal{O}(n)$
Deletion	$\mathcal{O}(1)$	$\mathcal{O}(n)$