我需要一個滿足這些要求的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