Нужна карта для быстрого поиска по ключу и для получения списка записей с ключами в некотором диапазоне

Question

Мне нужен Map<Integer,String> с основной необходимостью быстрого поиска значений на key. Однако мне также нужно извлечь List всех записей (key, value пар), чьи ключи находятся в диапазоне (от n1 до n2). Однако сортировка в списке не требуется. Карта будет содержать не менее 10 000 таких записей.

Сначала я думал об использовании TreeMap, но это не помогает с более быстрым поиском (O (log n) для операций get ()). Можно ли получить список записей из HashMap, ключи которых находятся в диапазоне от n1 до n2?

Какая моя лучшая ставка?

Answer 1

Две реализации NavigableMap (которые позволяют извлекать подкарты или подмножества на основе ключевых диапазонов): TreeMap и ConcurrentSkipListMap, обе из которых предлагают время доступа O (log n).

Предполагая, что вам требуется O (1) время доступа в соответствии с обычным HashMap, я предлагаю реализовать ваши собственные (неэффективные) методы "диапазона ключей".Другими словами, пожертвуйте производительностью операции с диапазоном клавиш для улучшенного времени доступа, которое вы достигнете с обычной HashMap.На самом деле другого пути для этого нет: NavigableMap методы по своей природе зависят от данных, хранящихся в отсортированном виде, что означает, что вы никогда не сможете достичь O (1) времени доступа.

Answer 2

Насколько близко распределены ключи? Для 10000 элементов, равномерно распределенных по 20 000 возможностей, таких как от 0 до 19999, я мог бы представить, что поиск элементов от 4 до 14 может быть подходящим. Вы бы пропустили со скоростью 50%.

Интересно, почему TreeMap не помогает с более быстрым поиском (O (log n) для операций get ())?

Если у вас есть дерево с меньшими значениями слева и большими справа, вы можете вернуть большие части поддеревьев. Это должно быть Карта и Список?