odict

An odict, short for ordered dictionary, is a data structure that combines the key-value semantics of a dictionary with the requirement to preserve the order in which keys were inserted. In an odict, keys are unique as in a normal map, but iteration over the items yields entries in insertion order rather than an arbitrary or undefined order.

Typical implementations use a hash map for fast key lookup and a linked list (or another sequencing mechanism) to remember the order of insertion. This dual structure allows O(1) average-case complexity for common operations, at the cost of higher memory usage compared with plain dictionaries.

In Python, the term is closely associated with collections.OrderedDict, which offers features such as moving an item to the end or to the beginning. Since Python 3.7, the built-in dict preserves insertion order, which has reduced the need for a separate odict in many cases.

Other languages provide similar types, such as LinkedHashMap in Java and Map-like structures in JavaScript that preserve insertion order. Many languages also support ordered dictionaries as libraries for environments lacking built-in support.

Common use cases include preserving key order when serializing to JSON or YAML, maintaining stable configuration file representations, and displaying items in a user interface in the order they were added. See also: ordered map, LinkedHashMap, insertion-ordered dictionary.