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 .