Seek for an efficient way to generate my HashMap instance

Question

I have a Person class:

public class Person{
    private String name;
    //pleaese think this 'id' simply as an attribute of Person, same as e.g. age, height
    private long  id; 
    public Person(String name, long id){
         this.name = name;
         this.id = id;
     }
    public String getName(){
        return name;
    }
    public long getId(){
        return id;
    }
}

Then, I have a HashMap instance which holds several Persons get from server:

//key is String type, it is a unique name-like string assigned to each Person 
//value is a Person object.
HashMap<String, Person> personsMap = GET_PERSONS_FROM_SERVER();

Then, I have an array of person IDs:

long[] ids = new long[]{1,2,3,4,5, …}

What I need is to generate another HashMap which only contains persons whose id is listed in the ids array:

// Only the person whose id is listed in ids array will be in the following Map
Map<String, Person> personNeeded = … ;

How to get personNeeded in an efficient way?

What do you use as map keys? Can you make the ID the map key? — Joni, Oct 29 '13 at 15:38
NO, ID is ID, the key is another unique name assigned to the Person — Mellon, Oct 29 '13 at 15:39
Oskar, id is just an attribute, don't think it as an id in DB, it could be anything, e.g. age, height... it is really just an attribute of the Person. it is not odd if think in this way. — Mellon, Oct 29 '13 at 15:42
Depends... Is there any scope in GET_PERSONS_FROM_SERVER() to return only ids matching your array? Otherwise, crack open a loop, my friend! — Bob Flannigon, Oct 29 '13 at 15:43
Bob, there is no scope to get ids matching the array from server, I have to handle it in client side, that's why I post this question. Otherwise why I ask here? I am seeking for an efficient way to do this in client. — Mellon, Oct 29 '13 at 15:50
@Mellon you really should consider the impact of rehashing on performance, see this [answer](http://stackoverflow.com/a/12128430/1113392) and my answer for how to instantiate the map, also you might consider overriding the `hashCode()` method of your object see this [question](http://stackoverflow.com/q/1757363/1113392) and the answers on, especially the one accepted. — A4L, Oct 29 '13 at 19:30

score 0 · Answer 1 · answered Oct 29 '13 at 15:44

0

You would have to loop through all the Person objects and look for id matches. When you find them you would have to add them to your second HashMap.

As long as the id is just an attribute on the Person object you will have to loop through all the values until you find the ones you are looking for.

answered Oct 29 '13 at 15:44

jzd

23,473
9
54
76

Thanks, your words is also my plan, if there is no efficient way than this one, I will do in this way. – Mellon Oct 29 '13 at 15:53

score 0 · Answer 2 · answered Oct 29 '13 at 15:50

You would either have to do a linear search through personsMap.values() or create a second Map that is keyed by the attribute you're searching on.

Wether a search Map or a linear search is faster depends on your use case. Maps can be slow to build, but they can be re-used and offer really fast look up. If you need to do multiple (several, really) searches, go for the search Map route. If you're searching personMap only once and only need to get a very small subset, then do the linear search.

Joni · Accepted Answer · 2013-10-29T16:28:53.657

If the map keys are not related in any way to the IDs, there is no better way to find the persons with the keys better than a linear iteration over the map entries.

First construct a set data structure of the IDs so you can check if the ID of a person is in the list in constant time:

Set<Long> idSet = new HashSet<>();
for (long id: ids) idSet.add(id);

Then just iterate over the entries:

HashMap<String, Person> personsById = new HashMap<>();
for (Map.Entry<String,Person> e : personsMap.entrySet()) {
    String key = e.getKey();
    Person val = e.getValue();
    if (idSet.contains(val.getId()) personsById.put(key, val);
}

score 0 · Answer 4 · answered Oct 29 '13 at 15:57

Do like this

Long[] ids = new Long[]{1l,2l,3l,4l,5l};        
ArrayList<Long> idList = new ArrayList<Long>(Arrays.asList(ids));       
HashMap<String, Person> personsMap = new HashMap<String, Person>();
HashMap<String, Person> newMap = new HashMap<String, Person>();

for (Map.Entry<String, Person> entry :personsMap.entrySet()) {
      if(idList.contains(entry.getValue().getId())){
             newMap.put(entry.getKey(), entry.getValue());
      }
}

A4L · Answer 5 · 2013-10-29T19:17:07.123

You could try something liek this:

1 - Turn your array into a Set for fast lookup

2 - Allocate a Map large enough to avoid rehash (for the default load factor 0.75, allocate 4/3 of the actual map size for the worstcase that the ids of all the elements are in the set)

public void subMap(Map<String, Person> personMap, Long[] idArray) {
    Set<Long> idSet = new HashSet<Long>(Arrays.asList(idArray));
    Map<String, Person> personSubMap = 
            new HashMap<String, Person>((personMap.size() *  4 / 3) + 1);
    for(Entry<String, Person> e : personMap.entrySet()) {
        if(idSet.contains(e.getValue().getId())) {
            personSubMap.put(e.getKey(), e.getValue());
        }
    }
}

Seek for an efficient way to generate my HashMap instance

5 Answers5