Which data structure is this?

Question

What is the name of the data structure, if one exists, that has the operations below?

• You can insert an element and you are given a key.
• You can retrieve an element by its key.

Answer 1

Memory Allocator

You allocate (insert) an element, and given a key (pointer, reference, etc.) you can retrieve the element (access it) by the pointer reference.

Answer 2

This is (pretty close to) a symbol table, in the Lisp sense (note that the phrase “symbol table” can also designate related but different data structures). A symbol table is an association from keys called symbols to values called bindings (or slots or some other term).

The operation of registering a new key is called gensym. Lisp symbols always have a unique name, which is a string; gensym returns a name that isn't used by any symbol. Lisp also supports looking up a symbol by name: intern returns a symbol given its name, and creates the symbol if not present; some implementations provide intern-soft to avoid creating a symbol if there is none by that name. Given a symbol, you can retrieve the associated value with symbol-value.

If you don't know Lisp, think of symbols as variables; gensym creates a new variable, and symbol-value returns the value of a variable designated by reference. These operations are especially useful when writing macros (metaprogramming), which Lisp supports very well. Modern Lisp implementations have “uninterned” symbols, i.e. symbols that are not in any table, which makes things cleaner. This is irrelevant for the data structure you have in mind (uninterned symbols would be things that are not in your data structure).

A symbol table is easily implemented on top of a map (dictionary) interface (which is usueally implemented with a hash table or a balanced tree). Gensym is find a fresh key, create it and return it. Lookup is the usual map lookup. If all your keys are created by gensym, the key type can remain abstract.