Which data structure is this?_问答_开发者_运维开发者技术经验分享

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开发者_如何学Go retrieve an element by its key.

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.

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.

I'm not sure what it's called, but it's implemented in version-control systems. For instance, the Git store has this data type: you store a blob in it and get a key, which is its SHA-1 hash. Later on, you can retrieve your blob using that key.

I think some filesystems might also work this way.

I might call it an "anonymous value store."

Sounds like a hash table/dictionary, though the key is known rather than given.

In space of "enterprise storage solutions" (or whatever) this is often called content-addressable storage, assuming that the key itself is derived (by eg. cryptographic hash) from the content you are putting in there, but that is in most case simply an implementation detail.

I think it is Big Table example which will be found on Google Storage. We can retrieve the element from key easy.

Sounds like a growable array to me (std::vector). On insert, return the number of items as the ID, and you are done. Satisfies the requirements and provides simple storage.

Sounds like it qualifies for both Map and Hash.

You have to be a bit more specific on element inserting though to identify it further.

Sounds like a dictionary. In a hashset, the elements tables act as keys, using a hash function from the set of the elements to natural numbers. A dictionary work similarly, by using a hashset for the keys, and each entry in the table points to a value.

I don't know any ADT where one inserts an element and gets back a key though...

It could be an implementation of a hash table.

This could likely fit the definitions and capabilities of a few structures, but most generally refers to a hash table or map.