ALGORITHMS AND DATA STRUCTURES
Associative Arrays
Article by:Geoffrey Hunter
Date Published: | |
Last Modified: |
Contents
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
Lookup | 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) \) |
Authors

This work is licensed under a Creative Commons Attribution 4.0 International License .