ALGORITHMS AND DATA STRUCTURES

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

LookupAverage CaseWorst Case
Lookup$$\mathcal{O}(1)$$$$\mathcal{O}(n)$$
Insertion$$\mathcal{O}(1)$$$$\mathcal{O}(n)$$
Deletion$$\mathcal{O}(1)$$$$\mathcal{O}(n)$$