Быстрее, чем реализация O(log N) int в Java?

Question

Fastutil имеет хороший класс IntAVLTreeSet, который имеет #firstInt() а также #lastInt() метод, который мне нужен.

К сожалению, AVL Tree - это O(log N).

Есть ли O(1) реализации этого? Это вообще возможно?

ОБНОВИТЬ

Я хочу O(1) поисков. Поиск полей может быть медленнее.

Answer 1

Класс, который вы упоминаете: в соответствии с его исходным кодом, firstInt() а также lastInt() уже O(1), Класс кэширует первую и последнюю записи в дереве.

Если вы хотите более общий поиск любого ключа, O(1)вам понадобится другая структура данных.