Home > Associative array

The operations that are usually defined for an associative array are:

• Add: Bind a new key to a new value
• Reassign: Bind an old key to a new value
• Remove: Unbind a key from a value and remove it from the key set
• Lookup: Find the value (if any) that is bound to a key

1 Examples

One can think of a telephone book as an example of an associative array, where names are the keys and phone numbers are the values. Another example would be a dictionary where words are the keys and definitions are the values. A database is a sort of generalized associative array.

Need more examples

2 Data structures for associative arrays

Associative arrays are usually used when lookup is the most frequent operation. For this reason, implementations are usually designed to allow speedy lookup, at the expense of slower insertion and a larger storage footprint than other data structures (such as association lists).

2.1 Efficient representations

There are two main efficient data structures used to represent associative arrays, the hash table and the self-balancing binary search tree. Skip lists are also an alternative, though relatively new and not as widely used. Relative advantages and disadvantages include:

• Hash tables have faster average lookup and insertion time (O(1)), while balanced binary trees have faster worst-case lookup and insertion time (O(log n) instead of O(n)). These make trees more useful in real-time and interactive systems, or high-security systems where untrusted users may supply information that triggers worst-case performance in a hash table, while making hash tables more useful for very large arrays. Skip lists have worst-case operation time of O(n), but average-case of O(logn), with much less insertion and deletion overhead than balanced binary trees.
• Hash tables have more compact storage for small value types, especially when the values are bits.
• There are simple persistent versions of balanced binary trees, which are especially prominent in functional languages.
• Building a hash table requires a good hash function for the key type, which can be difficult to write, while balanced binary trees and skip lists only require a less-than operator on the keys.
• Balanced binary trees and skip lists allow one to efficiently iterate over the keys in order, a highly expensive feat for a hash table.
• Balanced binary trees can be easily adapted to efficiently assign a single value to a large ordered range of keys.

2.2 Association lists

A simple but generally inefficient type of associative array is an association list, often called an alist for short, which simply stores a linked list of key-value pairs. Each lookup does a linear search through the list looking for a key match.

Strong advantages of association lists include:

• No knowledge is needed about the keys, such as an order or a hash function.
• For small associative arrays, common in some applications, association lists can take less time and space than other data structures.
• Insertions are done in constant time by consing the new association to the head of the list.