Associative array

A computer can use a smart list.

It links a name to a thing. This is like a library. A book name is the key. The person who took it is the value.

You can add a new pair to the list. You can also take a pair away. If you look for a name, the list finds the thing. This is very fast.

Some lists keep things in order. This helps the computer find things. It is a very helpful tool for computers.

Computers use a special way to store information. It is called an associative array. You might also hear it called a dictionary or a map.

This tool links a key to a value. A key is like a label. The value is the thing the label belongs to. Imagine a library. A book title is the key. The person who borrowed it is the value.

There are three main things you can do with a dictionary. First, you can insert a new pair. This adds a key and a value together. Second, you can remove a pair. This takes a key and its value away. Third, you can perform a lookup. This means you use a key to find its value.

Computers use different ways to build these arrays. One way is a hash table. A hash table uses a math rule to put keys into buckets. This makes finding things very fast. Another way uses search trees. These trees keep the keys in a specific order. This helps the computer find a range of items. Some languages have these tools built right in. They help programmers manage data easily.

Computers use many ways to organize information. One very important tool is the associative array. You might also hear it called a map, a dictionary, or a key-value store.

This tool works by linking a unique key to a specific value. Think of a library where book titles are the keys. The person who borrowed the book is the value. Each key can only appear once in the collection. This makes it a very organized way to manage data.

There are three main actions you can perform with an associative array. The first is called an insert or a put operation. This adds a new key and value pair to the group. If the key already exists, the old value is simply overwritten. The second action is to remove or delete a pair. You provide the key, and the computer unmaps it from its value. The third action is a lookup, also called a find or a get. You give the computer a key, and it returns the value bound to it.

Computer scientists have spent a long time solving the dictionary problem. This is the hard job of making these arrays work very quickly. Many people have studied how to build the best structures for this. For example, researchers M. Dietzfelbinger and others wrote about perfect hashing in 1994. They looked at how to make these systems work well.

Different methods exist depending on how many items you need to store. Some methods are simple but slow, while others are complex and fast.

There are two major ways to build these arrays. The most common way is using a hash table. A hash table uses a math rule called a hash function. This rule puts each key into a separate bucket in an array. This makes finding items very fast, usually in constant time.

Another way is to use a self-balancing binary search tree. These trees, like red-black trees, keep all the keys in a specific order. This allows you to find a range of values easily. While hash tables are often faster on average, trees are better in a worst-case scenario.

Associative arrays are used in almost every programming language today. Some languages include them as a basic part of the system. Others provide them through software libraries.

The first language to have built-in support was SNOBOL4 in 1969. It called this feature a "table." You can think of these arrays like a digital filing cabinet. Just as you use a label to find a folder, a computer uses a key to find data. This simple idea helps computers handle huge amounts of information every second.

An associative array is an abstract data type used to store collections of key-value pairs. In computer science, these structures are also known as maps, dictionaries, symbol tables, or key-value stores. The fundamental rule is that each possible key can appear at most once in the collection. Mathematically, an associative array can be viewed as a function with a finite domain. These structures are vital because they allow computers to organize and retrieve specific pieces of information very quickly.

To manage these collections, programmers use three primary operations: insert, remove, and lookup. An insert or "put" operation adds a new pair to the collection by mapping a key to a specific value. If the key already exists, the new value overwrites the old one. A remove or "delete" operation unmaps a given key from its value, removing the pair entirely. Finally, a lookup, often called "find" or "get," uses a key to retrieve its bound value. If the key is not found, the system might return a default value like zero or null, or it might raise an exception.

There are several ways to implement these arrays, ranging from simple to highly complex. For very small collections, an association list—which is a linked list of mappings—is easy to build. However, finding an item in a list takes linear time, meaning it gets slower as the list grows. Another method is direct addressing, where a value is stored at a specific index in an array. This is extremely fast, providing constant time for operations, but it is impractical if the range of possible keys is very large. This is because the system must set aside space for every possible key, even if they are not used.

Most general-purpose associative arrays use a hash table. A hash table combines an array with a mathematical process called a hash function. This function takes a key and assigns it to a specific "bucket" within the array. Because accessing an array index is a constant-time operation, hash tables usually perform with an average time complexity of O(1). However, hash tables must handle collisions, which happen when two different keys map to the same bucket. To solve this, developers use separate chaining, where each bucket holds a list of all matching values, or open addressing, where the system searches for the next empty spot in the array.

Another major implementation method uses self-balancing binary search trees. Common examples include AVL trees and red-black trees. Unlike hash tables, these trees keep all elements in a sorted order. This allows for range queries, which are searches for all values between two specific bounds. While hash tables are faster on average, their worst-case performance can drop to O(n) if many keys collide in one bucket. In contrast, self-balancing trees guarantee a much better worst-case performance of O(log n). This makes them more predictable for certain types of complex data management.

History shows that the need for these structures has been present since the early days of computing. Built-in syntactic support for associative arrays was first introduced in 1969 by the language SNOBOL4, which called them "tables." Later, the language TMG provided tables using string keys, and MUMPS introduced multi-dimensional associative arrays. Today, most programming languages include these as primitive data types or provide them through extensive software libraries. They are essential for advanced programming patterns like memoization, which helps speed up calculations by storing previous results.

Associative arrays also have specialized variations to meet specific needs. A multimap is a generalization that allows a single key to be associated with multiple different values. A bidirectional map is a related structure that allows lookups to work in both directions. In a bidirectional map, every value is linked to a unique key, so you can use a value to find its corresponding key just as easily as using a key to find a value. These variations allow developers to choose the exact tool needed for the specific way their data must flow.