Не, trie не подойдут, я о них думал. Скорость хорошая, но память расходуется слишком сильно - одна буква и две ссылки на узел в дереве. Тут такое дело, что чем меньше расходовать памяти, тем больше влезет в кэш, а значит меньше I/O.
Из-за этого же не могу воспользоваться ХэшМеп напрямую - там десяток референсов хранится на внутренние transient структуры типа EntrySet, которые мне не нужны. Тут такое дело, что при 20 парах уже даже прямой перебор в массиве всего 80% проигрывает хэшмепу (миллион чтений из HM занимает секунду, а перебором из массива пар - 1.8 сек). А память экономится в 2 раза. У меня сейчас есть идея одна, если выгорит, напишу результаты.