一套具有複合值和快速搜索價值元素

我正在尋找一個數據結構，它類似於一組存儲由4個整數組成的複合值：i1，i2,i3,i4。這個數據結構應該有快速的查找時間，但它也應該允許用特定的i3和i4快速刪除成員。所以delete_a(x)應刪除所有成員i3 = x和delete_b(x)應該刪除所有與i4 = x成員。最關鍵的是成員查找操作，所以我希望它是O（1）如果可能的話。 i1,i2,i3和i4的值相當大，所以我不能使用4維數組，因爲它會佔用太多的內存。我認爲也許哈希表和輔助列表的組合可以解決這個問題。一套具有複合值和快速搜索價值元素

來源

2013-05-03 Max

如果你想絕對速度，同時維持一定的內存使用效率，我會做這樣的：

HashMap_a: 
    Key: i3 
    Value: List of Hash(i1,i2,i3,i4) 
HashMap_b: 
    Key: i4 
    Value: List of Hash(i1,i2,i3,i4) 
HashMap: 
    Key: Hash(i1,i2,i3,i4) 
    Value: (i1,i2,i3,i4)

delete_a是簡單地從HashMap_a獲取列表，並從HashMap中移除它的鍵是該列表中的元素的問題。同樣對於delete_b
查找是O（1）HashMap

來源

2013-05-03 18:41:03

一套具有複合值和快速搜索價值元素

回答

相關問題