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.

language-agnosticdata-structures

dan_waterworth

Reputation: 6481

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 retrieve an element by its key.

Upvotes: 38

Answers (11)

mrmaclean89

Reputation: 586

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

Upvotes: 0

Brendan Lesniak

Reputation: 2321

It could be an implementation of a hash table.

Upvotes: 0

malkia

Reputation: 1387

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.

Upvotes: 62

Anteru

Reputation: 19424

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.

Upvotes: 1

Vineet1982

Reputation: 7918

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

Upvotes: 1

Ales Hakl

Reputation: 369

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.

Upvotes: 3

Noah Lavine

Reputation: 793

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."

Upvotes: 5

Gilles 'SO- stop being evil'

Reputation: 107849

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.

Upvotes: 9

Gal

Reputation: 5426

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...

Upvotes: 0