Что не так с Map <Object, Collection <Object>>?

Question

Я пытаюсь построить структуру данных на Java, где я буду вставлять около 200 000 ключей строк, каждый со значением «в среднем» из 1000 целых чисел Map<String, Arraylist<Integer>>. В итоге карта будет иметь около 200 миллионов значений.

Проблема заключается в том, что при вставке я должен сначала проверить, существует ли ключ на карте, если true, получить все значения, хранящиеся в коллекции temp, затем добавить новое целое в коллекцию и вернуть их обратно на карту , или создать новую коллекцию с новым целым числом.

Это так медленно, когда я добираюсь до точки, где коллекция содержит около 50000 целых чисел. Обычно я получаю java из-за ошибки в куче.

Есть ли способ избавиться от процесса получения? где я проверяю только существование ключа, а затем сразу добавляю значение к существующей коллекции, что-то вроде posh в стек, особенно в том, что карта находится в памяти, или это то, что делает разницу между Java и C++, где в C++ Я могу извлечь выгоду из использования указателей?

Сохраняя тот факт, что я не предпочитаю увеличивать размер карты, используя такие вещи, как multimaps, поскольку структура кажется почти простой.

Большое спасибо заранее.

Answer 1

Если ваш код действительно делает то, что предлагает ваш вопрос, вы работаете слишком усердно. Как только вы получите свой ключ, связанный с ArrayList. Просто вытащите ArrayList из карты и добавьте новое целое число в этот список. Вам не нужно «возвращать». Ссылка на Список - это все, что вам нужно, чтобы изменить Список.

Map<String, ArrayList<Integer>> m = new HashMap<String, ArrayList<Integer>>(); 
    for (int i = 0; i < 5; i++) { 
     String key = (i % 2 == 0) ? "Bob" : "Robert"; 
     ArrayList<Integer> l = m.get(key); 
     if (l == null) { 
      l = new ArrayList<Integer>(); 
      m.put(key, l); 
     } 
     l.add(i); 
    } 
    System.out.println("m is " + m); 

На мой взгляд, хотя, гуавы Multimap является гораздо лучшим решением этой проблемы: http://guava-libraries.googlecode.com/svn/tags/release03/javadoc/com/google/common/collect/Multimap.html

Answer 2

1. Существует огромный накладные расходы производительности, связанные с HashMap изменения размера. Когда вы создаете новый HashMap с конструктором no-arg, его размер по умолчанию 16. Вы помещаете в него все больше элементов, поэтому в любое время, когда вы превышаете доступное пространство, его необходимо изменить. Изменение размера включает вычисление хэш-кодов для каждой клавиши и перемещение ключей между хеш-таблицами. Это очень дорого.

Если вы знаете, что ваш HashMap будет хранить много ключей, вы можете создать его с размером, например, 200 000.

2. ArrayList имеет десятичную емкость по умолчанию. Если вы поместите больше элементов, необходимо изменить размер. Это предполагает создание нового массива (в котором ArrayList внутренне хранит элементы) и копирует элементы из старого массива в новый. Это также может быть очень дорогостоящим на больших ArrayLists.

Вместо этого я бы предложил использовать LinkedList. Добавление к нему новых элементов действительно дешево, поскольку элементы хранятся как независимые узлы. Однако есть некоторые недостатки. Подробности см. В разделе this question.

3. Вы должны иметь возможность зарезервировать достаточно памяти для 200 000 000 объектов. Как предложил Том Хотин, может потребоваться увеличение максимального пространства кучи, используемого JVM. Java не является C++, вы не можете просто использовать все больше и больше памяти.