JAVA : Best performance-wise method to find an object stored in hashMap

Question

I have a bunch of objects stored in hashMap<Long,Person> i need to find the person object with a specific attribute without knowing its ID.

for example the person class:

public person{
    long id;
    String firstName;
    String lastName;
    String userName;
    String password;
    String address;
    ..
   (around 7-10 attributes in total)
    }

lets say i want to find the object with username = "mike". Is there any method to find it without actually iterating on the whole hash map like this :

for (Map.Entry<Long,Person> entry : map.entrySet()) {
        if(entry.getValue().getUserName().equalsIgnoreCase("mike"));

the answers i found here was pretty old.

Answer 1

If you want speed and are always looking for one specific attribute, your best bet is to create another 'cache' hash-map keyed with that attribute.

The memory taken up will be insignificant for less than a million entries and the hash-map lookup will be much much faster than any other solution.

Alternatively you could put all search attributes into a single map (ie. names, and ids). Prefix the keys with something unique if you're concerned with collisions. Something like:

String ID_PREFIX = "^!^ID^!^";
String USERNAME_PREFIX = "^!^USERNAME^!^";
String FIRSTNAME_PREFIX = "^!^FIRSTNAME^!^";
Map<String,Person> personMap = new HashMap<String,Person>();

//add a person
void addPersonToMap(Person person)
{
    personMap.put(ID_PREFIX+person.id, person);
    personMap.put(USERNAME_PREFIX+person.username, person);
    personMap.put(FIRSTNAME_PREFIX+person.firstname, person);
}

//search person
Person findPersonByID(long id)
{
    return personMap.get(ID_PREFIX+id);
}

Person findPersonByUsername(String username)
{
    return personMap.get(USERNAME_PREFIX+username);
}

//or a more generic version:
//Person foundPerson = findPersonByAttribute(FIRSTNAME_PREFIX, "mike");
Person findPersonByAttribute(String attr, String attr_value)
{
    return personMap.get(attr+attr_value);
}

The above assumes that each attribute is unique amongst all the Persons. This might be true for ID and username, but the question specifies firstname=mike which is unlikely to be unique.

In that case you want to abstract with a list, so it would be more like this:

Map<String,List<Person>> personMap = new HashMap<String,List<Person>>();

//add a person
void addPersonToMap(Person person)
{
    insertPersonIntoMap(ID_PREFIX+person.id, person);
    insertPersonIntoMap(USERNAME_PREFIX+person.username, person);
    insertPersonIntoMap(FIRSTNAME_PREFIX+person.firstname, person);
}

//note that List contains no duplicates, so can be called multiple times for the same person.
void insertPersonIntoMap(String key, Person person)
{
    List<Person> personsList = personMap.get(key);
    if(personsList==null)
        personsList = new ArrayList<Person>();
    personsList.add(person);
    personMap.put(key,personsList);
}

//we know id is unique, so we can just get the only person in the list
Person findPersonByID(long id)
{
    List<Person> personList = personMap.get(ID_PREFIX+id);
    if(personList!=null)
        return personList.get(0);

    return null;
}

//get list of persons with firstname
List<Person> findPersonsByFirstName(String firstname)
{
    return personMap.get(FIRSTNAME_PREFIX+firstname);
} 

At that point you're really getting into a grab-bag design but still very efficient if you're not expecting millions of entries.

Answer 2

The best performance-wise method I can think of is to have another HashMap, with the key being the attribute you want to search for, and the value being a list of objects.

For your example this would be HashMap<String, List<Person>>, with the key being the username. The downside is that you have to maintain two maps.

Note: I've used a List<Person> as the value because we cannot guarantee that username is unique among all users. The same applies for any other field.

For example, to add a Person to this new map you could do:

Map<String, List<Person>> peopleByUsername = new HashMap<>();

// ...

Person p = ...;

peopleByUsername.computeIfAbsent(
        p.getUsername(), 
        k -> new ArrayList<>())
    .add(p);

Then, to return all people whose username is i.e. joesmith:

List<Person> matching = peopleByUsername.get("joesmith");