Associative array

Using notation from Python or JSON, the data structure would be: A lookup operation on the key "Great Expectations" would return "John".

If John returns his book, that would cause a deletion operation, and if Pat checks out a book, that would cause an insertion operation, leading to a different state: For dictionaries with very few mappings, it may make sense to implement the dictionary using an association list, which is a linked list of mappings.

[3][10] Another very simple implementation technique, usable when the keys are restricted to a narrow range, is direct addressing into an array: the value for a given key k is stored at the array cell A[k], or if there is no mapping for k then the cell stores a special sentinel value that indicates the lack of a mapping.

The basic idea behind a hash table is that accessing an element of an array via its index is a simple, constant-time operation.

The worst-case performance of self-balancing binary search trees is significantly better than that of a hash table, with a time complexity in big O notation of O(log n).

This is in contrast to hash tables, whose worst-case performance involves all elements sharing a single bucket, resulting in O(n) time complexity.

However, this introduces extra complexity into the implementation and may cause even worse performance for smaller hash tables, where the time spent inserting into and balancing the tree is greater than the time needed to perform a linear search on all elements of a linked list or similar data structure.

For instance, Judy trees have been found to perform less efficiently than hash tables, while carefully selected hash tables generally perform more efficiently than adaptive radix trees, with potentially greater restrictions on the data types they can handle.

A common solution to this problem is a generalized concept known as archiving or serialization, which produces a text or binary representation of the original objects that can be written directly to a file.

This is most commonly implemented in the underlying object model, like .Net or Cocoa, which includes standard functions that convert the internal data into text.

The program can create a complete text representation of any group of objects by calling these methods, which are almost always already implemented in the base associative array class.

[23] For programs that use very large data sets, this sort of individual file storage is not appropriate, and a database management system (DB) is required.

These key–value stores have been used for many years and have a history as long as that of the more common relational database (RDBs), but a lack of standardization, among other reasons, limited their use to certain niche roles.

RDBs were used for these roles in most cases, although saving objects to a RDB can be complicated, a problem known as object-relational impedance mismatch.

After approximately 2010, the need for high-performance databases suitable for cloud computing and more closely matching the internal structure of the programs using them led to a renaissance in the key–value store market.

These systems can store and retrieve associative arrays in a native fashion, which can greatly improve performance in common web-related workflows.