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

Ответ 1

Ассистент памяти

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

Ответ 7

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

Ответ 8

Похоже, что он подходит как для карты, так и для хэша.

Вы должны быть немного более конкретными при вставке элементов, хотя для дальнейшего определения.

Ответ 9

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

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

Ответ 10

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

Ответ 11

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