java - 有没有等价于Redis有序集（zset）的Java数据结构

Question

Redis 有一个称为有序集的数据结构。

该接口大致类似于 SortedMap，但按值而非键排序。我几乎可以使用 SortedSet，但它们似乎采用静态排序值。

是否有类似概念的规范 Java 实现？

我的直接用例是在每个元素上构建一个带有 TTL 的集合。地图的价值将是过期时间，我会定期修剪过期的元素。我还可以定期调整到期时间。

Answer 1

所以……有几件事。

首先，决定您将更多地使用哪种访问方式。如果您将执行比访问排序列表更多的 HashMap 操作（获取、放置），那么您最好只使用 HashMap 并在要修剪集合时对值进行排序。

至于修剪集合，听起来您只想删除时间小于某个时间戳的值，而不是删除最早的 n 个项目。如果是这种情况，那么您最好根据值是否满足条件来过滤 HashMap。这可能比尝试先对列表进行排序然后删除旧条目更快。

Answer 2

由于您需要两个单独的条件，一个在键上，另一个在值上，因此非常大量数据的最佳性能可能需要两个数据结构。您可以依赖常规 Set 并分别在按 TTL 排序的 PriorityQueue 中插入相同的对象。可以通过写入包含附加 TTL 的对象字段来实现 TTL 的碰撞；然后，当您删除下一个对象时，检查是否有额外的 TTL，如果有，则使用这个新的 TTL 和额外的 TTL = 0 将其放回 [我建议这样做，因为从 PriorityQueue 中删除的成本是 O( n)]。这将产生 O(log n) 时间来移除下一个对象（+ 由于碰撞 TTL 而产生的成本，这将取决于它发生的频率）和插入，以及 O(1) 或 O(log n) 时间来碰撞一个TTL，

当然，最简洁的方法是设计一个封装所有这些的新类。

此外，如果您的数据集不是很大，那么所有这些都是多余的。

Answer 3

看看ExpiringMap。Guava 的缓存也可能适用于您的用例。

Answer 4

您可以使用两种数据结构的组合来实现它。键到分数的排序映射。以及分数到键的排序反向映射。

在 Java 中，通常这些将使用 TreeMap 实现（如果我们坚持使用标准 Collections Framework）。

Redis 使用 Skip-Lists 来维护排序，但 Skip-Lists 和平衡二叉搜索树（例如 TreeMap）都用于在此处提供平均 O(log(N)) 访问。

对于给定的排序集，我们可以将其实现为一个独立的类，如下所示：

class SortedSet {
  TreeMap<String, Integer>> keyToScore;
  TreeMap<Integer, Set<String>>> scoreToKey

  public SortedSet() {
    keyToScore= new TreeMap<>();
    scoreToKey= new TreeMap<>();
  }

  void addItem(String key, int score) {
    if (keyToScore.contains(key)) {
      // Remove old key and old score
    }
    // Add key and score to both maps 

  }

  List<String> getKeysInRange(int startScore, int endScore) {
     // traverse scoreToKey and retrieve all values
  }

  ....

}