Abstract Data Types: Associative Arrays

What is an associative array?

An associative-array (or map) is a sequential abstract data type in which entries are key-value pairs (instead of being just values) where following rules have to be obeyed:

What are the operations an associative array requires?

Although, as an abstract data type, associative array comes with no implementation, it requires from data structures that implement it to provide support for a minimal set of operations:

Operation Arguments Returns Description
clear   void Clears map of all values.
containsKey KEY bool Checks if key exists in map.
containsValue VALUE, COMPARATOR bool Checks if value exists in map.
get KEY VALUE Gets value by key.
set KEY, VALUE void Sets value by key.
removeKey KEY void Removes element by key.
removeValue VALUE, COMPARATOR void Removes all elements that match value.
isEmpty   void Checks if map is empty
size   ULONG Gets map size

What are the data structures that implement associative array?

Most common implementations of associative array are:

This time complexity table using Big O Notation shows advantages and disadvantages of each data structure chosen for each associative array operation:

Operation Hash Table Linked Hash Table Red Black Tree
clear O(N) O(N) O(N)
containsKey O(1) O(1) O(log(N))
containsValue O(N) O(N) O(N)
get O(1) O(1) O(log(N))
set O(1) O(1) O(log(N))
removeKey O(1) O(1) O(log(N))
removeValue O(N) O(N) O(N)
isEmpty O(1) O(1) O(1)
size O(1) O(1) O(1)

Conclusion: Hash Table, with its speed/memory efficiency advantages, should be solution of choice unless one specifically desires structure to be predictably iterated or self-ordered!


Share