CODEWITHSUNDEEP
javaperformancehashmap
Javier Ferrero
Javier Ferrero

Reputation: 8811

Union of two or more (hash)maps

I have two Maps that contain the same type of Objects:

Map<String, TaskJSO> a = new HashMap<String, TaskJSO>();
Map<String, TaskJSO> b = new HashMap<String, TaskJSO>();

public class TaskJSO { String id; }

The map keys are the "id" properties.

a.put(taskJSO.getId(), taskJSO);

I want to obtain a list with: all values in "Map b" + all values in "Map a" that are not in "Map b".

What is the fastest way of doing this operation?

Thanks

EDIT: The comparaison is done by id. So, two TaskJSOs are considered as equal if they have the same id (equals method is overrided).

My intention is to know which is the fastest way of doing this operation from a performance point of view. For instance, is there any difference if I do the "comparaison" in a map (as suggested by Peter):

Map<String, TaskJSO> ab = new HashMap<String, TaskJSO>(a);
ab.putAll(b);
ab.values()

or if instead I use a set (as suggested by Nishant):

Set s = new Hashset();
s.addAll(a.values());
s.addAll(b.values());

Upvotes: 14

Views: 28434

Answers (3)

Nishant
Nishant

Reputation: 55866

Method 1:

 Set s = new HashSet();
 s.addAll(a.values());
 s.addAll(b.values());

Set is collection of unique objects. Refer: http://download.oracle.com/javase/1.4.2/docs/api/java/util/HashSet.html

Method 2:

This will compare keys, and if same keys are found -- the value will be overwritten by the later Map's value.

Map<String, TaskJSO> ab = new HashMap<String, TaskJSO>(a);
ab.putAll(b);
ab.values()

Now, no matter what's the case... the comparison will take place using equals. So, Method-1 will call equals on all the values and Method2 will call it on all the keys. Depending on how complex the comparison is the performance will vary.

In method 1, you need to create a new Set but it ensures that different values with same keys are not overwitten. But Method-2 is smart, if you have unique IDs.

Edit#1 updates as the question was updated

Upvotes: 15

Peter Lawrey
Peter Lawrey

Reputation: 533492

If you want all the key/values from b plus all the values in a, not in b.

Map<String, TaskJSO> ab = new HashMap<String, TaskJSO>(a);
ab.putAll(b);

Starts with a copy of a and replaces or adds all the key/values from b.

Upvotes: 10

templatetypedef
templatetypedef

Reputation: 372784

I think you can do this in linear time as follows. Let n and m be the number of elements in a and b, respectively.

  1. Create a new HashSet containing all the values from b. Time is O(m).

  2. Add all of the values from b to a new list. Time is O(m).

  3. For each value in a, check whether the HashSet of values in b contains that element. If so, do nothing. Otherwise, add it to the list. Time is O(n).

This ends up using no more than O(n + m) time, which is linear.

Upvotes: 2

Related Questions