Multi Key Hashmap

Question

Recently I had an interview to save the huge count of employee details in DS.

I gave the solution as Hashmap with emp Id as key.

The follow up question was if the user wants to search based on name how to implement it. I suggested to use emp name as key and save all the employees with same name as Arraylist.

The next follow up question was tricky, need to create ONE map where user can search based on emp Id or emp name. How to implement this in map?

Implement it in memory efficient way.

Answer 1

This is a dirty solution (yes--very dirty, never do it on production!), but it will work if keys are of different types and one is not subtype of another (e.g. long and String). Put every employee by both keys, and get by provided key, either id or name:

Map<?, List<Employee>> map = new HashMap<>();

public void putEmployee(Employee e) {
    map.put(e.id, Arrays.asList(e));    // put by id
    if (!map.containsKey(e.name)) {
        map.put(e.name, new ArrayList<>());
    }
    map.get(e.name).add(e);             // put by name
}

public Employee getById(long id) {
    return map.containsKey(id) ? map.get(id).get(0) : null;
}

public List<Employee> getByName(String name) {
    return map.containsKey(name) ? map.get(name) : Collections.emptyList();
}

In production code, I'd use two separate maps or custom dictionary class.

Answer 2

This is a pretty easy question to answer: Just convert the IDs to Strings and store employees twice - once under the name and again under the id-as-string.

Your idea of using a List as the value is fine - for IDs, the list would be of size 1.

Note that it would be better to use two maps, because you only ever have one employee per ID and you wouldn't have to deal with a list of size 1 as a degenerate case, so:

Map<Integer, Employee> employeesById;
Map<String, Set<Employee>> employeesByName;

Especially note that you wouldn't use less memory by using just one map. In fact, you would use more memory than storing employees in separate maps for ID keys and name keys.

Answer 3

I have come up with a solution. Please post your suggestions.

Step 1: Form the hashmap with emp id as key and emp object as value.

Step 2: For the same name create a list of emp id who matches the name Ex: name = 'XYZ' id={101,102,103,...}

Step 3: Insert this name as key and arraylist as value to the same map

Here we are not storing complete employee detail twice. Just trying to maintain a relationship between name and id. So comparatively it could be memory efficient.

Answer 4

One way to do this would be to create a Key object that can be searched by either the name or the id:

public enum KeyType {
    ID, NAME;
}

public class SearchKey {
    private KeyType keyType;
    private String value;

    // constructor and getters snipped for brevity's sake

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }

        SearchKey searchKey = (SearchKey) o;

        return keyType == searchKey.keyType && value.equals(searchKey.value);

    }

    @Override
    public int hashCode() {
        int result = keyType.hashCode();
        result = 31 * result + value.hashCode();
        return result;
    }

public class Directory {
    private Map<SearchKey, Set<Employee>> directory = new HashMap<>();

    public void addEmployee(Employee e) {
        // Add search by id
        directory.put
            (new SearchKey(KeyType.ID, e.getId()), Collections.singleton(e));

        // Add search by name
        SearchKey searchByName = new SearchKey(KeyType.NAME, e.getName());
        Set<Employee> employees = directory.get(searchByName);
        if (employees == null) {
            employees = new HashSet<>();
            directory.put(searchByName, employees);
        }
        employees.add(e);
    }

    public Employee getById (String id) {
        // Assume that the ID is unique
        return directory.get(new SearchKey(KeyType.ID, id)).iterator().next();
    }

    public Set<Employee> getByName (String name) {
        return directory.get(new SearchKey(KeyType.NAME, name));
    }
}