java - 比 Java 中的 O(log N) int set 实现更快？

Question

Fastutil 有很好的类 IntAVLTreeSet ，它有我需要的方法#firstInt()。#lastInt()

不幸的是，AVL 树是 O(log N)。

是否有 O(1) 的实现？有可能吗？

更新

我想要 O(1) 查找。寻找边距可能会更慢。

Answer 1

你提到的类：根据它的源代码，已经是. 该类缓存树中的第一个和最后一个条目。firstInt()lastInt()O(1)

如果您想对任何键进行更一般的查找，则O(1)需要不同的数据结构。