`ArrayList of HashMap` или` LinkedHashMap`, чтобы получить товар по индексу

Question

Мне нужно хранить огромное количество данных в форме ключа. Кроме того, у меня есть два требования:

1. данные запроса через индекс, как из массива.
2. Следовательно, порядок в структуре данных должен быть сохранен.

Для Требований 2 - я могу использовать LinkedHashMap.

Для Требованию 1 - У меня есть два варианта:

• 1.1 | Для реализации ArrayList Of HashMap. [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

Я пошел с experimentating сам. Оказывается, метод создания массива ArrayList из HashMaps составляет около 40 раз быстрее с 1000 элементами.

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 элементов - разница огромна.

Answer 2

Попробуйте использовать SortedMap.

Например:

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

Таким образом, вы получите быстрое время поиска (с помощью ключа), но они также остаются прописали.

Вы можете перебрать данные следующим образом:

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

Я использовал их в последнее время для анализа 10s миллионов твитов, где ключ был датой, а значение было встречное. Я хотел сохранить порядок дат.

обновление Если вы можете обойтись только с использованием этих данных, то моего метода будет достаточно. Возможно, вы могли бы привести небольшой пример? Если вам абсолютно необходимо, чтобы вы могли ссылаться на данные по индексу, похоже, вы просто хотели бы поддерживать две структуры данных, такие как @Jim. Я должен был это сделать раньше.

Answer 3

Я думаю, что LinkedHashMap является лучшим решением, но для того чтобы получить деталь, то вы можете использовать

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

Однако метод ToArray будет медленным для больших объемов данных. Но это то, что вам нужно будет испытать.

Если скорость действительно проблема, вы можете поддерживать HashMap и ArrayList.

Answer 4

Помните, что коллекции не содержат объектов, только ссылок на объекты.

Используйте две коллекции:

1. ArrayList для хранения ссылок для доступа по индексу
2. А HashMap хранить ссылки для доступа по ключу

Например:

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. Wrap значение в «ручке», который содержит ключ и индекс.

Например

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(); 
...