Стоимость слияния двух хэш-карт

Скажем, у меня есть два HashMaps, как показано ниже.

HashMap<Character, Integer> map1 = new HashMap<Character, Integer>();
HashMap<Character, Integer> map2 = new HashMap<Character, Integer>();

Теперь я хочу объединить эти два вместе и поместить их в другой HashMap как map3.

что было бы лучшим способом сделать это с точки зрения асимптотической сложности.


java performance asymptotic-complexity
person Ali_IT    schedule 11.03.2014    source источник
comment
Если вы беспокоитесь о производительности, вы можете использовать int[] при условии, что вы можете делать предположения о диапазоне букв, которые вы хотите подсчитать. Это имеет ту же временную сложность, но во много раз быстрее.   -  person Peter Lawrey    schedule 11.03.2014

Ответы (2)


arrow_upward
1
arrow_downward

С точки зрения асимптотической сложности это означает создание новой карты и добавление к ней всех элементов каждой карты. Итак, T(вставка) * (m + n) (я не буду раскрывать ответ, если это домашнее задание!). Хэш-карта Java не более эффективна, чем хэш-карта учебника, поэтому там нет ярлыков. Наконец, если вы можете произвольно изменить одну из двух карт, я бы рекомендовал объединить меньшую карту с большей. Это сэкономит время, затрачиваемое на повторение большой карты, и может сэкономить время, затрачиваемое на выделение памяти.

person Giovanni Botta    schedule 11.03.2014
comment
Вот источник для вашего дальнейшего рассмотрения http://kickjava.com/src/java/util/HashMap.java.htm - person cbayram; 11.03.2014

arrow_upward
0
arrow_downward

Самый простой способ сделать то, что вы хотите:

HashMap<Character, Integer> map3 = new HashMap<Character, Integer>();
map3.putAll(map1);
map3.putAll(map2);

Надеюсь это поможет.

person Sanjeev    schedule 11.03.2014
comment
Можно также использовать конструктор копирования HashMap<Character, Integer> map3 = new HashMap<Character, Integer>(map1);, затем map3.putAll(map2) - person cbayram; 11.03.2014