Opslagstabel

Opslagstabel is a data structure that stores pairs of keys and values, allowing fast retrieval of a value by its corresponding key. The term is commonly used in Danish computing to refer to a mapping or dictionary that maps input tokens to associated data.

The most widely used implementation is the hash table. A hash function converts a key into an index in an underlying array, and collisions are handled by strategies such as separate chaining or open addressing. Typical operations are insert, lookup, update and delete, with average time complexities near O(1) for a well-designed hash table. Performance depends on the quality of the hash function, the load factor, and resizing policy; in the worst case, operations can degrade to O(n).

Alternative implementations include balanced search trees (for example red-black trees), which provide O(log n) time for operations, and sorted arrays with binary search, which offer O(log n) lookups but may incur higher costs for inserts or deletions. Static lookup tables or perfect hashing are used when the input space is known in advance, delivering very predictable, constant-time lookups at the cost of extra preprocessing and memory.

A opslagstabel is distinct from a database index, though they share the goal of speeding data retrieval. Keys should be unique, and values can be any data type. In many contexts, a lookupstabel is precomputed to accelerate repetitive calculations or to cache results.

Common use cases include symbol tables in compilers, configuration mappings, translation tables in localization, and fast resource or asset lookups in software systems.