Компактные альтернативы Java ArrayList <String>

Мне нужно хранить большой словарь слов естественного языка – до 120 000, в зависимости от языка. Они должны храниться в памяти, поскольку профилирование показало, что алгоритм, который использует массив, является узким местом в системе. (Это, по сути, алгоритм проверки орфографии / автокоррекции, хотя детали не имеют значения.) На устройствах Android с памятью 16 МБ накладные расходы памяти, связанные с Java String s, вызывают у нас нехватку места. Обратите внимание: каждая String имеет связанный с ней 38 байт, что дает до 5 МБ служебных данных.

На первый взгляд, один из вариантов заключается в замене char[] на String . (Или даже byte[] , поскольку UTF-8 в этом случае является более компактным.) Но опять-таки проблема с памятью является проблемой: каждый массив Java имеет 32 байта накладных расходов .

Одной из альтернатив ArrayList<String> и т. Д. Является создание класса с тем же интерфейсом, который внутренне объединяет все строки в одну гигантскую строку, например, представленную как один byte[] , а затем сохраняет смещения в эту огромную строку. Каждое смещение занимает 4 байта, что дает гораздо более эффективное пространство.

Мои вопросы: а) есть ли какие-либо другие решения проблемы с такими же низкими накладными расходами * и b) любое решение, доступное готовым? Поиск в библиотеках коллекций Guava , trove и PCJ ничего не дает.

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

NB. Поддержка сжатия сжатых строк в JSM HotSpot? Что опция JVM -XX:+UseCompressedStrings здесь не поможет.

Solutions Collecting From Web of "Компактные альтернативы Java ArrayList <String>"

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

Вот некоторые ресурсы, которые могут быть полезны.

https://en.wikipedia.org/wiki/Trie

https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/