Какие структуры данных использовать для хранения справочника в памяти

Что проверяют

Умеете ли вы выбрать структуру под профиль доступа: справочник читают часто, меняют редко и из многих потоков сразу. Следом спрашивают, как обновить справочник на лету, не останавливая чтение, и сколько он займёт памяти.

Как отвечать

Сначала уточните сценарий: поиск по ключу, по диапазону или по префиксу, объём, частота обновлений. Потом варианты:

• HashMap: поиск за O(1) в среднем. С Java 8 переполненная корзина превращается в дерево, и худший случай O(log n), если ключи реализуют Comparable. Не потокобезопасен;
• неизменяемый снимок: Map.copyOf или ImmutableMap из Guava, ссылка на него в volatile-поле или AtomicReference. Обновление собирает новую карту и подменяет ссылку одним присваиванием, читатели работают без блокировок;
• ConcurrentHashMap: если записи идут точечно и постоянно, а не пачкой раз в час;
• TreeMap и ConcurrentSkipListMap: O(log n), зато есть subMap, floorKey, ceilingKey для поиска по диапазону и ближайшему значению;
• EnumMap: ключ перечисление, внутри компактный массив;
• Caffeine: если справочник большой и целиком не нужен, с вытеснением и refreshAfterWrite для фонового обновления.

Про память скажите отдельно: каждая запись HashMap это объект узла плюс упакованные ключ и значение, на миллионах записей набегают сотни мегабайт. Для примитивных ключей берут fastutil или Eclipse Collections, а для поиска по нескольким полям держат несколько карт над одними и теми же объектами.

Где спотыкаются

Берут обычный HashMap и обновляют его из фонового потока, пока другие читают. Это гонка: читатель может увидеть недостроенное состояние или потерять запись.

Кладут в ключ изменяемый объект. Поменялось поле, участвующее в hashCode, и запись больше не находится.

Предлагают ArrayList с перебором для справочника на тысячи позиций. Сортированный список с Collections.binarySearch ещё допустим, линейный поиск на каждый запрос нет.