什么Java数据结构/解决方案最适合满足这些要求？

Question

我需要一个符合以下要求的Java数据结构/解决方案，哪种最适合呢？

1) 对象的插入顺序必须保持不变。

2) 对象必须是唯一的（这些是由UUID唯一标识的数据库对象）。

3) 如果添加了具有相同ID的新对象，则应覆盖/删除旧版本的对象。

4) 解决方案应该可以被多个线程访问。

5) 当从数据结构中读取/使用第一个添加的对象时，它应该从数据结构中删除。

- mainstringargs

---

这些对象是按顺序访问还是随机访问的？使用第三个选项，您希望对象的位置移动到最近插入的对象？ - Cogsy

Answer 1

这里有几种可能性。最简单的方法可能是从LinkedHashSet开始。这将为您提供所需的唯一性和可预测的排序。然后，您可以将结果集包装起来，使其线程安全：

Set<T> s = Collections.synchronizedSet(new LinkedHashSet<T>(...));

注意：由于Set并没有定义一种从中检索项的方法，因此您的代码必须手动调用Set.remove(Object)。

或者，您可以包装一个LinkedHashMap，它提供了您所需的读时删除语义的钩子。

class DeleteOnReadMap<K, V> implements Map<K, V> {

    private Map<K, V> m = new LinkedHashMap<K, V>();

    // implement Map "read" methods Map with delete-on-read semantics
    public V get(K key) {
        // ...
    }
    // (other read methods here)

    // implement remaining Map methods by forwarding to inner Map
    public V put(K key, V value) {
        return m.put(key, value);
    }
    // (remaining Map methods here)
}

最后，将您自定义的 Map 实例包装起来，使其线程安全：

Map<K, V> m = Collections.synchronizedMap(new DeleteOnReadMap<K, V>(...));

- harto

---

为使其线程安全，你可以这样做：使用代码Set s = Collections.synchronizedSet(new LinkedHashSet(...))。 - RN.

为了使其线程安全，删除读取语义必须在同步代码内部，否则两次读取可能会暴露出竞争条件。 - Peter Lawrey

@Peter 很好的观点，但是我刚意识到 Set 没有 get() 的等效方法 - 所以删除操作无论如何都必须在 Set 外部进行。我已经添加了一个更有用的 Map 示例到我的答案中。如果客户端通过某些 UUID 引用对象，这可能更有意义。 - harto

Answer 2

我的想法大致如下：

 Collections.synchronizedMap(new LinkedHashMap<K, V>());

我认为除了第5个需求之外，其他都已经解决，但是你可以使用remove()方法而不是get()来实现。

这种方式可能没有ConcurrentMap那么高效 - 在每次访问时同步锁定整个映射，但是我认为ConncurrentMap的实现可以使用读写锁和选择性地锁定部分映射，以允许多个非冲突访问同时进行。如果需要，你可以通过编写现有Map实现的子类来获得更好的性能。

- David Z

Answer 3

1) 对象的插入顺序必须保持不变。

这是任何“正常”的数据结构 - 数组，ArrayList，树。因此，避免使用自平衡或自排序的数据结构：堆，哈希表或移动到前面的树（例如伸展树）。然而，您可以使用其中之一，但是您必须在每个节点中跟踪其插入顺序。

2) 对象必须是唯一的（这些是由UUID唯一标识的数据库对象）。

为每个对象保留唯一标识符。如果这是C程序，则该节点的指针是唯一的（我想这也适用于Java）。如果节点的指针不足以维护“唯一性”，则需要向每个节点添加一个字段，您保证具有唯一值。

3) 如果添加了具有相同ID的新对象，则应覆盖/删除旧版本的对象。

您想把节点放在哪里？您想要替换现有的节点吗？还是您想删除旧节点，然后将新节点添加到末尾？这很重要，因为它与您的需求＃1相关，其中必须保留插入顺序。

4）解决方案应该可以被多个线程访问。

我能想到的唯一方法是实现某种形式的锁定。Java允许您在synchronized块中包装结构和代码。

5）当第一个添加到结构中的对象被读取/使用时，它应该从数据结构中删除。

有点像“dequeue”操作。

似乎ArrayList对于此非常好：仅因为＃5。唯一的问题是搜索是线性的。但是，如果您有相对较少的数据，则这并不是太大的问题。

否则，就像其他人所说的那样：HashMap或者某种树都可以使用 - 但这将取决于访问的频率。（例如，如果“最近”的元素最有可能被访问，我会使用线性结构。但如果访问是“随机”元素，我会选择HashMap或Tree。）

- poundifdef

Answer 4

关于LinkedHashSet的解决方案可能是一个很好的起点。

然而，您必须覆盖要放入集合中的对象的equals和hashcode方法，以满足您的第三个要求。

- A_M

Answer 5

听起来你必须创建自己的数据结构，但这似乎是一个相当简单的课程作业。

基本上你可以从任何东西开始，比如一个数组或栈，但之后你必须扩展其余的功能。

你需要查看“包含”方法，因为你将需要它。

- James Black