具有索引和哈希访问的集合

我需要一个具有以下两者的集合类：快速索引和哈希访问。现在我有ArrayList。它具有良好的索引访问权限，但他的contains方法不是高性能的。 HashSet具有良好的contains实现，但没有索引访问。哪个集合兼有？可能来自Apache的东西？或者我应该创建我自己的集合类，它同时具有：ArrayList for indexed acces和HashSet for contains check？具有索引和哈希访问的集合

只是为了澄清：我需要同时get(int index)和contains(Object o)

来源

2013-02-22 Sergiy Medvynskyy

你拥有的数据结构，其中包含两个（或一些变化）可能是要走的路。 – Dukeling 2013-02-22 12:09:33

你能解释一下你为什么要这么做吗？ – 2013-02-22 18:02:05

是的，我可以。我有遗留代码，它几乎使用了List对象（ArrayList）的所有方法。我没有机会重写它，但我想提高它的性能。这里的主要问题是contains和indexOf方法，因为它们具有线性性能。 – 2013-02-23 20:34:11

如果您遍历从开始到结束的指标，我认为这可能满足您的需求：如果您需要通过随机访问LinkedHashSet

索引，以及哈希访问，如果没有其他人有更好的建议我想你可以做你自己的收藏这两个。

来源

2013-02-22 12:02:47 vikingsteve

就我所见，索引访问是'O（n）'，这不是特别有效。 – Dukeling 2013-02-22 12:04:57

LinkedHashSet没有方法'get（int index）' – 2013-02-22 12:09:47

@SergiyMedvynskyy是的，但您可以使用迭代器来模拟它。 – Dukeling 2013-02-22 12:11:20

如果索引的访问性能不是问题最接近的匹配是LinkedHashSet其API说，这是

哈希表和Set接口的链接列表实现，具有可预知的迭代顺序。

至少我不认为性能会比LinkedListPerformance差。否则我看不到你的ArrayList + HashTable解决方案

来源

2013-02-22 12:10:04

我不确定它真的更好 – 2013-02-22 12:16:58

这样做;使用哈希技术的组合以及列表得到两全其美:)

class DataStructure<Integer>{ 
    Hash<Integer,Integer> hash = new HashMap<Integer, Integer>(); 
    List<Integer> list = new ArrayList<Integer>(); 

    public void add(Integer i){ 
     hash.add(i,i); 
     list.add(i); 
    } 
    public Integer get(int index){ 
     return list.get(index); 
    } 
    ... 
} //used Integers to make it simpler

的所以对象;你保留在HashMap/HashSet以及ArrayList。

所以，如果你想使用

contains method : call hashed contains method. 

get an object with index: use array to return the value

只要确保你在同步这两个集合。并照顾两个数据结构中的更新/删除。

来源

2013-02-22 13:05:41

这是最后一个漏洞，我会用它，如果我找不到更好的东西 – 2013-02-22 14:05:34

我不知道确切的查找时间，但也许你可以使用一些Map interface的实现。您可以使用map.put(objectHash, obj)存储对象。

然后，你可以验证你有一定的对象：

boolean contained = map.containsValue(obj);

你也可以使用哈希查找地图中的一个对象：

MyObject object = map.get(objectHash);

虽然，唯一的区别就在于你需要知道你在这个查询调用中的哈希，这可能不是你的实现。

来源

2013-02-22 13:53:02

containsValue为HashMap具有与包含列表相同的性能 - 线性。我希望对数（当然如果可能的话）。 – 2013-02-22 14:02:13

@SergiyMedvynskyy啊，我没有意识到这一点。你有没有参考你发现的地方？ – 2013-02-22 14:11:35

只需看看HashMap的实现。方法containsValue遍历所有条目并检查是否与ArrayList的contains方法相同。 – 2013-02-22 14:30:48

具有索引和哈希访问的集合

回答

相关问题