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

Question

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

Answer 1

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

\n

\n

E first()\n

\n

返回当前集合中的第一个（最低）元素。

\n

E last()\n

\n

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

\n

\n

Java API 文档没有说明它们的 Big-O 性能是什么。可以想象它们的复杂度可能是O (1)。SortedSet是一个接口，所以这取决于你使用的具体实现。

\n

树集

\n

SortedSets 通常是TreeSets，所以实际上它们是O (log n )。

\n

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

\n

请参阅OpenJDK 源代码：

\n

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

\n

实际上，O (log n ) 非常接近O (1)。在具有一百万个元素的排序集中，只需 20 次遍历即可找到第一个/最后一个节点 (log ₂ 1,000,000 \xe2\x89\x88 20)。

\n

堆或优先队列

\n

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

\n

跳过列表

\n

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

\n

\n

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

\n

\n

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

\n

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

\n

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

\n

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

\n