java - `ArrayList of HashMap` 或 `LinkedHashMap` 按索引获取项目

Question

我需要以键值形式存储大量数据。另外，我有两个要求

1. 通过索引查询数据，就像从数组中一样。
2. 因此必须保留数据结构中的顺序。

对于要求 2 - 我可以使用LinkedHashMap。

对于要求 1 - 我有两个选择：

• 1.1 | 实现HashMap 的 ArrayList。[ ArrayList<HashMap<String,String>>]
• 1.2 | 实现LinkedHashMap并使用类似的方法按索引查询项目
  • ->new ArrayList(hashMapObject.entrySet()).get(0);

问题是1.1或中哪个更好1.2？

更好，我的意思是 -在内存和空间方面有效。

假设数据量大约为 50 到 100 个键值对，平均大小的字符串 - 假设每个键是 10-30 个字符，值是 30-50 个字符。

Answer 1

尝试使用 SortedMap。

例如：

SortedMap<Key, Value> map = new TreeMap<Key, Value>();

这样您可以获得快速查找时间（通过键），但它们也保持有序。

然后，您可以像这样遍历数据：

for(Key k : map.keySet()) { 
    process(map.get(k)); 
}

我最近用它们分析了 10 百万条推文，其中键是日期，值是计数器。我想保持日期的顺序。

更新如果您只需遍历数据就可以解决问题，那么我的方法就足够了。也许你可以提供一个小例子？如果绝对要求您也可以按索引引用数据，那么您似乎只想维护两个数据结构，如提到的@Jim。我以前不得不这样做。

Answer 2

请记住，集合不包含对象，仅包含对对象的引用。

使用两个集合：

1. 存储引用以ArrayList供索引访问
2. AHashMap存储引用以通过密钥访问

例如：

List<MyValue> list = new ArrayList<MyValue>(100000);
Map<MyKey,MyValue> map = new HashMap<MyKey,MyValue>(100000);

while(moreItems) {
    // read input
    MyKey key = ...
    MyValue value = ...
    list.add(value);
    map.put(key,value);
}

// lookup by index
MyValue v1 = list.get(11241);
// lookup by key
MyValue v2 = map.get(someKey);

如果你需要交叉引用（即给定一个值对象，找到它的索引或它的键）你有一些选择：

1. 将索引和键保存在值对象本身中
2. 将值包装在包含键和索引的“句柄”中。

例如

class Wrapper {
    MyKey   key;
    MyValue value;
    int     index;
    // constructor, getters and setters
}

int index=0;
while(moreItems) {
    // read input
    MyKey key = ...
    MyValue value = ...
    Wrapper w = new Wrapper(key,value,index++);
    list.add(w);
    map.put(key,w);
}
...
Wrapper w = list.get(23410);
MyKey k = w.getKey();
MyValue v = w.getValue();
int i = w.getIndex();
...

Answer 3

我认为 LinkedHashMap 是最好的解决方案，但是要获取项目，您可以使用

hashMapObject.values().toArray()[index]

但是，对于大量数据，toArray 方法会很慢。但这是你必须测试的东西。

如果速度真的是个问题，你可以维护一个 HashMap和一个 ArrayList。

Answer 4

我自己去实验了。事实证明，使用 1000 个元素创建HashMap 的 ArrayList 的方法大约快 40 倍。

public class HashMapVsArrayOfHashMap {

    public static void main(String[] args){
        ArrayList<HashMap<String, String>> listOfMaps=new ArrayList<HashMap<String,String>>();
        for( int i=0;i<1000;i++){
            final int finalI=i;
        listOfMaps.add(new HashMap<String, String>(){{put("asdfasdfasdfasdfadsf"+finalI,"asdfsdafasdfsadfasdf"+finalI);}});
        }
        LinkedHashMap<String, String> map=new LinkedHashMap<String, String>();
        for(int i=0;i<1000;i++)
            map.put("asdfasdfasdfasdfadsf"+i,"asdfsdafasdfsadfasdf"+i);     
        int position=700;
        testArrayList("Method1:ArrayListOfHashMaps",position,listOfMaps);
        testHashMap("Method2:LinkedHashMap",position,map);
    }

    private static void testArrayList(String string, int position,
            ArrayList<HashMap<String, String>> listOfMaps) {
        long start, end;
        start=System.nanoTime();
        listOfMaps.get(position).get("asdfasdfasdfasdfadsf"+position);
        end=System.nanoTime();
        System.out.println(string+"|Difference = "+(end-start));        
    }
    private static void testHashMap(String string, int position,
            LinkedHashMap<String, String> map) {
        long start, end;
        start=System.nanoTime();

        String s= new ArrayList<String>(map.keySet()).get(position);

        end=System.nanoTime();
        System.out.println(string+"|Difference = "+(end-start));        
    }
}

当您将大小增加到 30,000 个元素时 - 差异是巨大的。