ALGORITHMS AND DATA STRUCTURES

Associative Arrays

Article by:
Date Published:
Last Modified:

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

Geoffrey Hunter

Dude making stuff.

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

Related Content:

Tags

comments powered by Disqus
Page contents: