Какая структура данных это?

Question

Как называется структура данных, если таковая существует, с операциями, перечисленными ниже?

• Вы можете вставить элемент и получить ключ.
• Выможет получить элемент по его ключу.

Answer 1

Распределитель памяти

Вы выделяете (вставляете) элемент, и по ключу (указателю, ссылке и т. Д.) Вы можете извлечь элемент (получить к нему доступ) по ссылке на указатель.

Answer 2

Это (очень близко к) таблица символов в смысле Lisp (обратите внимание, что фраза «таблица символов» также может обозначать связанные, но разные структуры данных). Таблица символов представляет собой связь между ключами, называемыми символами, и значениями, называемыми связываниями (или слотами, или каким-либо другим термином).

Операция регистрации нового ключа называется gensym. Символы Лиспа всегда имеют уникальное имя, которое является строкой; gensym возвращает имя, которое не используется ни одним символом. Lisp также поддерживает поиск символа по имени: intern возвращает символ по имени и создает символ, если его нет; некоторые реализации предоставляют intern-soft, чтобы избежать создания символа, если его нет с таким именем. По заданному символу вы можете получить соответствующее значение с помощью symbol-value.

Если вы не знаете Лисп, думайте о символах как о переменных; gensym создает новую переменную, а symbol-value возвращает значение переменной, обозначенной ссылкой. Эти операции особенно полезны при написании макросов (метапрограммирование), которые Lisp поддерживает очень хорошо. В современных реализациях Lisp есть «неинтернизированные» символы, то есть символы, которых нет ни в одной таблице, что делает вещи чище. Это не имеет значения для структуры данных, которую вы имеете в виду (непостоянные символы - это вещи, которых нет в вашей структуре данных).

Таблица символов легко реализуется поверх интерфейса карты (словаря) (который обычно реализуется с помощью хеш-таблицы или сбалансированного дерева). Gensym - найти свежий ключ, создать его и вернуть. Поиск - это обычный поиск по карте. Если все ваши ключи созданы gensym, тип ключа может оставаться абстрактным.

Answer 3

Я не уверен, как это называется, но это реализовано в системах контроля версий. Например, хранилище Git имеет такой тип данных: вы храните в нем большой двоичный объект и получаете ключ, который является его хешем SHA-1. Позже вы можете получить свой блоб, используя этот ключ.

Я думаю, что некоторые файловые системы также могут работать таким образом.

Я мог бы назвать это «хранилищем анонимных значений».

Answer 4

Звучит как хеш-таблица / словарь, хотя ключ известен, а не задан.

Answer 5

В пространстве «корпоративных решений для хранения данных» (или чего-либо еще) это часто называют адресно-ориентированным хранилищем, если предположить, что сам ключ получен (например, с помощью криптографического хэша) из содержимого, которое вы туда помещаете, но это в большинстве случаев это просто детали реализации.

Answer 6

Для меня звучит как растущий массив (std :: vector). При вставке верните количество элементов в качестве идентификатора, и все готово. Удовлетворяет требованиям и обеспечивает простое хранение.

Answer 7

Я думаю, что это пример Big Table, который можно найти в Google Storage.Мы можем легко извлечь элемент из ключа.

Answer 8

Это, вероятно, может соответствовать определениям и возможностям нескольких структур, но чаще всего относится к хеш-таблице или карте.

Answer 9

Это может быть реализация хеш-таблицы.

Answer 10

Звучит как словарь.В хэш-наборе таблицы элементов действуют как ключи, используя хэш-функцию от набора элементов до натуральных чисел.Словарь работает аналогично, используя хэш-набор для ключей, и каждая запись в таблице указывает на значение.

Я не знаю ни одного ADT, в который вставляется элемент и возвращается ключ ....