В каких структурах данных в Java обычно реализуются индексы для быстрого поиска?

В Java индексы для быстрого поиска по ключу чаще всего реализуются с помощью:

1. Хэш-таблиц (HashMap, HashSet, ConcurrentHashMap).

   • Структура: Массив бакетов (Node<K,V>[] table). Каждый бакет содержит связный список или дерево (при коллизиях).
   • Сложность поиска: В среднем O(1), в худшем случае (все ключи в одном бакете) — O(n).
   • Использование: Когда важен быстрый доступ по уникальному ключу, а порядок элементов не важен.

     // Пример индекса email -> User
     Map<String, User> emailIndex = new HashMap<>();
     emailIndex.put("alice@example.com", new User("Alice"));
     User user = emailIndex.get("alice@example.com"); // Быстрый поиск

2. Сбалансированные деревья (TreeMap, TreeSet).

   • Структура: Красно-черное дерево.
   • Сложность поиска: O(log n).
   • Использование: Когда нужен упорядоченный индекс или поиск по диапазону (например, все ключи от A до K).

     // Пример индекса, отсортированного по дате
     TreeMap<LocalDate, Event> eventIndex = new TreeMap<>();
     eventIndex.put(LocalDate.now(), new Event("Meeting"));
     // Поиск всех событий за последнюю неделю (диапазонный запрос)
     Map<LocalDate, Event> lastWeek = eventIndex.subMap(
     LocalDate.now().minusDays(7),
     LocalDate.now()
     );

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