具有对数读取复杂性的基于时间戳的分类数据结构

Question

我正在寻找Java中的良好排序数据结构。经过一些研究，有关使用Treeet/Treemap的提示很少。但是这些组件缺乏一件事：随机访问集合中的元素。例如，我想访问排序集中的nth元素，但是使用Treeet，我必须在到达那里之前对其他N-1元素进行迭代。这将是浪费

用例就像以下

9:20 AM what is this object? edited by user1
9:30 AM what is this book ? edited by user2
9:40 PM what is this red book? edited by user1

我总是想显示该用户最新的编辑标题。我知道最新的时间戳将是最大的时间戳。为此，我发现ConcurrentSkipListSet/Maps很好。但是，我想知道是否有任何更好的方法来实施此功能。

Answer 1

假设您应该对数据进行排序，最好的选择是TreeMap。没有银色子弹，它是一个分类的集合，也可以执行O(1)随机访问。在有序集合中，您可以直接访问带有索引的元素，但是如果需要排序您的集合，则无法从基于索引的访问中受益。

如果您需要并发，则ConcurrentSkipListMap很好。它适用于大规模同时访问数据。但是，就性能而言，我们基于红黑树的PAL TreeMap是不匹配的。因此，如果您不需要并发，请忘记ConcurrentSkipListMap并坚持使用TreeMap。

TreeMap优雅，满足您的需求。尽管如此，实际上，在需要时使用HashMap并对数据进行分类可能会更好。尝试两者，找出哪一个在您的情况下更好。