Нужен эффективный для хранения памяти способ хранения тонн строк (было: реализация HAT-Trie в Java)

Question

Я работаю с большим набором (5-20 миллионов) ключей String (средняя длина 10 символов) , которые мне нужно хранить в структуре данных в памяти, которая поддерживает следующая операция в постоянное или почти постоянное время:

// Returns true if the input is present in the container, false otherwise
public boolean contains(String input)

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

Меня не волнует время вставки / удаления. В моем приложении я буду выполнять только вставки (только во время запуска) и впоследствии буду только запрашивать структуру данных, используя метод contains в течение всего срока службы приложения.

Я прочитал, что структура данных HAT-Trie наиболее близка к моим потребностям. Мне интересно, есть ли библиотека, которая имеет реализацию.

Приветствуются другие предложения с указателями на реализации.

Спасибо.

Answer 1

Это кажется хорошей идеей для ваших ограничений.

Альтернатива «нестандартное мышление»:

Если вы можете позволить себе некоторую вероятность ответа «присутствует» для отсутствующей строки

РЕДАКТИРОВАТЬ: если вы можете позволить себе ложные срабатывания, используйте фильтр Блума , как предложено WizardOfOdds в комментариях.

При k = 1 фильтр Блума похож на хеш-таблицу без ключей: каждое «ведро» является просто логическим значением, которое сообщает, присутствует ли хотя бы один вход с таким же хешем. Если допустим 1% ложных срабатываний, ваша хеш-таблица может составлять примерно 100 * 20 миллионов бит или примерно 200 МБ. Для 1 из 1000 ложных срабатываний, 2 ГБ.

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

Answer 2

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

Answer 3

Аналогично дереву троичного дерева поиска, но у троичного дерева поиска есть преимущество использования меньшего количества памяти. Вы можете прочитать о троичных поисковых деревьях здесь , здесь и здесь . Также одна из основных статей по этому вопросу Джона Бентли и Роберта Седжвика: здесь . В нем также говорится о быстрой сортировке строк, так что не откладывайте на это.

Answer 4

Для эффективности использования пространства, поиска O (log (n)) и простого кода попробуйте бинарный поиск по массиву символов. 20 миллионов ключей средней длины 10 составляют 200 миллионов символов: 400 МБ, если вам нужно 2 байта / символ; 200 МБ, если вы можете обойтись 1. Вдобавок к этому вам нужно как-то представить границы между ключами в массиве. Если вы можете зарезервировать символ-разделитель, это один из способов; в противном случае вы можете использовать параллельный массив смещений int.

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