ALGORITHMS AND DATA STRUCTURES

Associative Arrays

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

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

Like this page? Upvote with shurikens!

Related Content:

Tags:

comments powered by Disqus