我需要一个满足这些要求的java数据结构/解决方案。什么最适合这些?什么Java数据结构/解决方案最适合这些要求?
1)对象的插入顺序必须保持
2)对象的必须是唯一的(这些是唯一地由一个UUID识别数据库对象)。
3)如果添加具有相同ID的较新对象时,对象的旧版本应该盖写/删除
4)溶液应是可访问的多个线程。
5)当第一个对象添加到结构的读/使用,应当从数据结构
我需要一个满足这些要求的java数据结构/解决方案。什么最适合这些?什么Java数据结构/解决方案最适合这些要求?
1)对象的插入顺序必须保持
2)对象的必须是唯一的(这些是唯一地由一个UUID识别数据库对象)。
3)如果添加具有相同ID的较新对象时,对象的旧版本应该盖写/删除
4)溶液应是可访问的多个线程。
5)当第一个对象添加到结构的读/使用,应当从数据结构
这里有几种可能性。最简单的可能是从LinkedHashSet开始。这将为您提供您所需的唯一性和可预测的订购。然后,你可以换所得到的设定,使其线程安全:
Set<T> s = Collections.synchronizedSet(new LinkedHashSet<T>(...));
注:由于设置并没有真正定义,用于从它的项目的方法,你的代码将不得不手动调用Set.remove (目的)。
或者,你可以换一个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<K, V> m = Collections.synchronizedMap(new DeleteOnReadMap<K, V>(...));
为了让线程safe-你可以这样做 集合S = Collections.synchronizedSet(新LinkedHashSet(...)); – 2009-04-20 03:18:32
听起来像是你必须创建自己的数据结构中删除,但它听起来像是一个非常简单的类分配。
基本上,你从数组或堆栈的任何东西开始,但是你必须对其余的功能进行扩展。
您可以查看'Contains'方法,因为您将需要该方法。
我的想法是类似如下:通过使用remove()
方法而不是get()
Collections.synchronizedMap(new LinkedHashMap<K, V>());
我认为,照顾一切,除了要求5,但你可以做。
这不会像ConcurrentMap
那样高效 - 同步锁定每次访问时的整个地图,但我认为ConncurrentMap
实现可以使用读写锁和仅对部分地图进行选择性锁定以允许多个不冲突的访问可以同时进行。如果你愿意,你可以通过编写你自己的一些现有Map
实现的子类来获得更好的性能。
1)对象的插入顺序必须 保持
这是任何“正常”数据结构 - 数组,arrayList,树。因此,避免自我平衡或自我排序的数据结构:(伸展树,例如)堆,哈希表,或者移动到前面的树木话又说回来,你能使用这些结构的一个,但你必须保持追踪每个节点中的插入顺序。
2)对象的必须是唯一的(这些是唯一 由UUID标识) 数据库对象。
保持与每个对象相关联的唯一标识符。如果这是一个C程序,那么指向该节点的指针是唯一的(我想这也适用于Java)。如果节点的指针不足以维持“唯一性”,那么您需要为每个节点添加一个字段你保证有一个独特的价值。
3)如果添加具有相同ID 一个新对象,该对象 的旧版本应该被覆盖/删除
你在哪里要放置节点?你想替换现有的节点吗?或者是否要删除旧节点,然后将新节点添加到最后?这很重要,因为它与您的要求#1有关,必须保留插入顺序。
4)解决方案应该可以被许多线程访问 。
我能想到的唯一方法就是实现某种锁定。 Java允许您在区块中封装结构和代码。
5)当所述第一对象添加到 结构是读/使用,应当 从数据结构
除去有点像一个“出列”操作。
看起来像一个ArrayList是这个一个相当不错的选择:仅仅是因为#5。唯一的问题是搜索是线性的。但是,如果您的数据量相对较少,那么这并不是什么大问题。
否则,像其他人所说:某种类型的HashMap的,甚至是树会工作 - 但是这将取决于访问的频率。 (例如,如果在“最近”元素是最有可能被访问,我会使用一个线性结构。但是,如果访问将是“随机”的元素,我会用一个HashMap或树去。)
谈论LinkedHashSet的解决方案将是一个很好的起点。
但是,你将不得不覆盖在对象上的equals和hashCode方法,你会在一组进行投入,以满足您的需求数量3
是为了访问的对象?或随机?与3)你想要的对象位置移动最近插入的对象? – Cogsy 2009-04-20 02:20:54