Java SortedSet实现，它允许您获得O(1)中最小/最大的元素

Question

是否有一个排序集实现允许获得O(1(中的第一个元素？C++的std:：set可以做到这一点，所以我不明白为什么我们不能在Java中做到这一步。谢谢

Answer 1

我想您已经看到了first和last方法：

E first()

返回当前在此集合中的第一个(最低的(元素。

E last()

返回当前此集合中的最后一个(最高(元素。

Java API文档没有说明他们的Big-O性能是什么。他们可能是O(1(。SortedSet是一个接口，因此它取决于您使用的具体实现。

树集

SortedSets通常是TreeSets，因此在实践中它们是O(logn(。

TreeSet利用TreeMap，而TreeMap不缓存第一个和最后一个节点。当您调用first或last或创建迭代器时，它从根开始，并向下和向左(或向下和向右(遍历以找到目标节点。这需要O(logn(时间。

请参阅OpenJDK源代码：

/**
* Returns the first Entry in the TreeMap (according to the TreeMap's
* key-sort function).  Returns null if the TreeMap is empty.
*/
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
/**
* Returns the last Entry in the TreeMap (according to the TreeMap's
* key-sort function).  Returns null if the TreeMap is empty.
*/
final Entry<K,V> getLastEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.right != null)
p = p.right;
return p;
}

实际上，O(logn(与O非常接近(1(。在一个有一百万个元素的排序集中，只需要20次遍历就可以找到第一个/最后一个节点(log₂1000000≈20(。

堆或优先级队列

如果您想要真正的O(1(性能，那么堆(即PriorityQueue(是比树更好的数据结构。堆不会按排序顺序维护整个元素集。然而，您总是可以在O(1(时间内获得head元素。移除磁头需要O(logn(时间，之后新磁头可用于即时查找。

跳过列表

还有一个使用较少的ConcurrentSkipListSet类。根据维基百科：

跳过列表是一种概率数据结构，它允许O(logn(搜索复杂性以及O在n元素的有序序列中插入复杂性。因此，它可以获得排序数组的最佳功能(用于搜索(，同时保持类似链表的结构，允许插入，这在静态数组中是不可能的。

查找第一个元素是O(1(。有一个循环，但如果需要清理已标记为删除的节点，它只会循环不止一次。当它没有任何要处理的删除时，它会立即返回。请参阅OpenJDK源代码：

/**
* Gets first valid node, unlinking deleted nodes if encountered.
* @return first node or null if empty
*/
final Node<K,V> findFirst() {
Node<K,V> b, n;
if ((b = baseHead()) != null) {
while ((n = b.next) != null) {
if (n.val == null)
unlinkNode(b, n);
else
return n;
}
}
return null;
}

另一方面，找到最后一个元素是…嗯…不是O(1(。

/**
* Specialized version of find to get last valid node.
* @return last node or null if empty
*/
final Node<K,V> findLast() {
outer: for (;;) {
Index<K,V> q; Node<K,V> b;
VarHandle.acquireFence();
if ((q = head) == null)
break;
for (Index<K,V> r, d;;) {
while ((r = q.right) != null) {
Node<K,V> p;
if ((p = r.node) == null || p.val == null)
RIGHT.compareAndSet(q, r, r.right);
else
q = r;
}
if ((d = q.down) != null)
q = d;
else {
b = q.node;
break;
}
}
if (b != null) {
for (;;) {
Node<K,V> n;
if ((n = b.next) == null) {
if (b.key == null) // empty
break outer;
else
return b;
}
else if (n.key == null)
break;
else if (n.val == null)
unlinkNode(b, n);
else
b = n;
}
}
}
return null;
}