Faster than O(log N) int set implementation in Java?

Question

Fastutil has nice class IntAVLTreeSet which has #firstInt() and #lastInt() method, that I require.

Unfortunately, AVL Tree is O(log N).

Are there O(1) implementations of this? Is it possible at all?

UPDATE

I want O(1) lookups. Finding margins may be slower.

Answer 1

The class you mention: according to its source code, firstInt() and lastInt() are already O(1). The class caches the first and last entries in the tree.

If you want a more general lookup of any key to be O(1), you'll need a different data structure.