Какая структура данных подходит для этой ситуации?

Question

Я пытаюсь решить, какую структуру данных использовать для хранения пар ключ-значение, когда необходимы только функции

• вставка
• поиск

В частности, мне не нужно иметь возможность удалять пары или перебирать ключи / значения / пары.

Ключи - это целочисленные кортежи, значения - указатели (ссылки, что угодно). Я храню только пару миллионов пар, разбросанных по (многим) объектам.

В настоящее время я рассматриваю возможность использования

• хеш-таблица
• кд-дерево
• б-дерево

Я склоняюсь к хеш-таблице (на время вставки / поиска O(1)), но я хотел подтвердить свои склонности.

Какую структуру (из вышеперечисленных или другую) вы бы порекомендовали и почему? Если вы порекомендуете хеш-таблицу, мне следует создать отдельную таблицу для каждого объекта или просто создать одну таблицу и использовать идентификатор объекта в качестве части кортежа ключей?

Answer 1

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

Answer 2

Хеш-таблицы были бы здесь полезны, и я не вижу причин иметь более одной таблицы.

Answer 3

Я большой поклонник хеш-таблиц, поскольку они просты и есть реализации, доступные практически для всех основных языков. Вставка / поиск O (1) - это особенно полезная функция.

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

Answer 4

У большинства деревьев есть время поиска O (n ln n), но у хеш-таблиц есть время поиска O (1), так что это то, что вы хотите использовать. Это также очень распространено, и часто реализация высоко оптимизирована для загрузки.