creating a map with duplicate keys

Question

Consider the following question on storing values with duplicate keys:

Suppose there is a class Employee with name, sal and dob as attributes. I want to store the objects of Employee in a Map and the key would be the Employee name. The name can be duplicate.
Also after adding 10 objects in the Map. I want to retrieve the 8th object that was entered.

This is one solution to add objects with duplicate keys but for the 2nd part of the question, this would not work since on displaying the map, all values with the same key will be displayed together.

How would we maintain the order in which the objects were added in this situation? Can we modify equals and hashcode methods to somehow add the elements and then later retrieve them in the order in which they were inserted?

Are you interested in the insertion order of all your entries/employees or only the ones with conflicting keys/names? — Marsellus Wallace, Sep 10 '11 at 16:12
2 scenarios: 1] suppose I add 10 employees all with same key and different sal and dob. 2] 10 employees some of them having duplicate keys. How would you get the nth record from the map in both these scenarios? — neeraj narang, Sep 10 '11 at 16:32
Possible duplicate of http://stackoverflow.com/questions/1062960/map-implementation-with-duplicate-keys — Steve Chambers, Dec 16 '13 at 12:28

score 2 · Answer 1 · answered Sep 10 '11 at 15:40

2

I think a LinkedHashMultimap (from Guava) should work for this. You wouldn't be able to get the 8th entry by index directly, but you could use something like Iterables.get(Iterable iterable, int position) to get it.

answered Sep 10 '11 at 15:40

ColinD

108,630
30
201
202

Can't this be implemented using java collections? The interviewee had said something about changing the equals and hashcode methods but i'm not sure how to implement it... – neeraj narang Sep 10 '11 at 15:55
@neeraj: Well, `LinkedHashMultimap` is (internally) basically a `LinkedHashMap>` plus a `LinkedHashSet>` for storing entries in the order they were added. So yes, you can achieve the same effect using JDK classes only. – ColinD Sep 10 '11 at 18:40

score 1 · Answer 2 · edited May 23 '17 at 12:31

1

Why not just have two containers? One for mapping name to employee (like the one in the stackoverflow question you mentioned), another for mapping number to employee. You can make an "outer" container aggregating multimap and arraylist.

edited May 23 '17 at 12:31

Community

1
1

answered Sep 10 '11 at 15:33

Vlad

35,022
6
77
199

Wouldn't it be too much use of memory? The interviewee said that it can be implemented by modifying the equals and hashcode methods but i'm not sure how... – neeraj narang Sep 10 '11 at 16:02
@neeraj: well, it could be done with hashcode, but I would say it would be an ugly hack. For example: include a field "hashcode" into Empolyee, initialize to -1, set to the hashtable.size() before inserting into hashtable. Modify `Equals` so that any two employees are different if they are not the same object. This should do, but it's dirty and will definitely make some problems in other parts of code. – Vlad Sep 10 '11 at 16:15

score 1 · Answer 3 · answered Sep 10 '11 at 15:37

1

What you intend to do can be easily implemented using an ArrayList. This is the data structure that you should use.

answered Sep 10 '11 at 15:37

Marcelo

11,218
1
37
51

could you please elaborate...because the example that I've mentioned uses ArrayList but on displaying, it will display the objects with the same key together and not in the order in which they were inserted in the **Map** – neeraj narang Sep 10 '11 at 15:54
@neeraj What I am saying is that maybe you don't need a map for your needs, just add your Employees to an ArrayList. This will maintain the order in which you add them to the list. Why question to you would be, Why do you need a map for this case? – Marcelo Sep 10 '11 at 16:14
I don't need it, this was asked in an interview. It's just a scenario...There could be a need to store values in a Map having duplicate keys... – neeraj narang Sep 10 '11 at 16:31

score 0 · Accepted Answer · answered Sep 10 '11 at 22:15

The requirements are somehow contradictory. At one side several values should be possible for one key, at the other side only one value should be returned for a key. Additionaly, retrievals for a sequence should be possible. I see the nearest approximation in designing a dedicated data structure containing a hash map for fast access based on the name, and a list keeping the order of insertions. The access would be based on the overall sequence number or on the name plus index for the name. The implementation would be according the following lines:

public class Employee {
    public String name;  public int sal;        
    public Employee() {name = ""; sal = 0;}
    public Employee(String name, int sal) {
        this.name = name; this.sal = sal;
    }
    @Override public String toString() {return "(" + name + "," + sal + ")";}
}

public class Team {
    private Map<String, ArrayList<Employee>> employees = 
             new HashMap<String, ArrayList<Employee>>();
    private ArrayList<Employee> order = new ArrayList<Employee>();

    public void addEmployee(Employee e) {
        ArrayList<Employee> list = employees.get(e.name);     
        if (list == null) {
            list = new ArrayList<Employee>();
            employees.put(e.name, list); 
        } 
        list.add(e);
        order.add(e);
    }         
    public int getNumEmployees() {return order.size();}
    public Employee getEmployee(int n) {return order.get(n - 1);}       
    public int getNumEmployees(String name) {
        ArrayList<Employee> list = employees.get(name);
        return list == null ? 0 : list.size();
    }
    public Employee getEmployee(String name, int n) {
        ArrayList<Employee> list = employees.get(name);
        return list == null ? null : list.get(n - 1);
    }
}

// Test:
Team team = new Team();
team.addEmployee(new Employee("Bob", 11));
team.addEmployee(new Employee("Bob", 12));
team.addEmployee(new Employee("Eve", 13));
team.addEmployee(new Employee("Eve", 14));

System.out.println("Num all: " + team.getNumEmployees()); 
System.out.println("3rd: " + team.getEmployee(3));
System.out.println("Num Bobs: " + team.getNumEmployees("Bob")); 
System.out.println("2nd Bob: " + team.getEmployee("Bob", 2));

creating a map with duplicate keys

4 Answers4