Структура данных в памяти для компактного отображения миллиардов словарных ключей на значения

Question

У меня есть миллиарды записей (ключей / значений), которые я хочу компактно сохранить в памяти, и единственная операция, которую мне нужно поддержать, это поиск значения по его ключу.Ключи и значения являются небольшими строками.Самое главное, насколько сжато структура данных;он должен использовать внутреннюю структуру ключей глубже, чем простой ассоциативный массив.Например, сопоставление ключей «apple», «apply» и «apron» со значениями «1», «2» и «3» должно как-то быть сжато.Какую структуру данных я ищу?

Answer 1

Звучит так, как будто вы хотите trie - он выполняет тот тип сжатия, который вы описываете, сохраняя каждый префикс только один раз.

Я предполагаю, что у вас достаточно памяти для хранения«миллиарды» ключей, и, конечно же, вам нужно быть в 64-битной системе, чтобы иметь возможность обрабатывать даже столько элементов в первую очередь.

Answer 2

Вы можете попробовать Trie .Он формирует древовидную структуру из самих ключевых строк.Там не будет пустых мест (как на хэш-карте).

Answer 3

Даже если данные, с которыми вы работаете, представляют собой небольшие строки, действительно ли вы уверены, что вам нужно так много данных в памяти?Это может легко привести к гигабайту памяти, и большая часть данных, вероятно, не будет запрашиваться так часто.

Точно настроенной базы данных может быть достаточно для ваших нужд.