Рекомендовано хэш-карта с низким объемом памяти для реализации на Java

Question

В настоящее время я работаю над проблемой, связанной с программированием, в которой я пытаюсь создать массивную хэш-карту данных. Ключом для данных является пользовательская реализация CharSequence с малым объемом памяти, которая реализует hashCode () и equals (...), а значением является объект Integer.

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

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

В идеале я хотел бы иметь возможность хранить миллион записей на карте на 50 МБ пространства кучи (один байтовый массив из 25 байтов в ключе и объект Integer в части значения).

Есть ли у кого-нибудь опыт работы с Картами с файловой системой с малым объемом памяти, оптимизированными для уменьшения площади клавиш?

Спасибо

Chris

Answer 1

Вы можете использовать хэш-карту Java и написать класс FileKey, который принимает RandomAccessFile, смещение и длину, предварительно вычисляет хеш при построении и реализует Comparable, считывая данные из файла только для сравнения.

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

Answer 2

Как насчет Berkeley DB Java Edition ?Класс StoredMap выглядит так, как вы ищете.

Answer 3

Я думаю, что значение по умолчанию HashSet - неплохой способ - создайте пару ключ-значение самостоятельно (чтобы вам не приходилось оборачивать их в дополнительный объект). Это довольно эффективно для памяти; на самом деле требуется только около (1 / loadFactor) ^ (3/2) * на 4 байта больше памяти поверх ключевого объекта + 4 байта для значения. На практике это должно добавить примерно 8 байтов служебной информации на каждую запись. (Вы можете уменьшить это значение, если заранее знаете, сколько ключей вы собираетесь хранить.)