Merge entries in Map

Question

I have class ID and Value, and a Map from ID to Value

public class IDs {

    public TreeSet<Integer> ids;
    public HashSet<IDs> neighbors;
    public static HashSet<IDs> idSet = new HashSet<>();

    private boolean hash;
    private int hashcode;

    public IDs(int id,HashSet<IDs> neighbors) {
        this.ids = new TreeSet<>();
        this.ids.add(id);
        this.neighbors = neighbors;
        idSet.add(this);

        this.hash = false;
        this.hashcode = 0;
    }

    public void addNeighbor(IDs neighbor) {
        this.neighbors.add(neighbor);
        neighbor.neighbors.add(this);
    }

    public static boolean cluster(IDs id1,IDs id2) {
        if (id1.equals(id2))
            return false;
        id1.ids.addAll(id2.ids);
        id2.ids.addAll(id1.ids);
        id2.neighbors.remove(id1);
        id1.neighbors.remove(id2);
        id1.neighbors.addAll(id2.neighbors);
        id2.neighbors.addAll(id1.neighbors);

        id1.hash = false;

        return true;
    }

    @Override
    public String toString() {
        String name = "{";
        for (Integer i:ids)
            name += "Cell " + i + ", ";
        name += "}";
        return name;
    }

    @Override
    public boolean equals(Object obj) {
        IDs o = (IDs) obj;
        return this.ids.containsAll(o.ids) && o.ids.containsAll(this.ids);
    }

    @Override
    public int hashCode() {
        if (this.hash)
            return this.hashcode;
        TreeSet temp = (TreeSet) this.ids.clone();
        int first,hash = 0;
        while (!temp.isEmpty()) {
            first = (int) temp.first();
            temp.remove(temp.first());
            hash = CantorPair(hash,first);
        }
        this.hash = true;
        this.hashcode = hash;
        return hash;
    }

    private int CantorPair(int k1,int k2) {
        return (k1 + k2) * (k1 + k2 + 1) / 2 + k2;
    }

}


class Value{
    Integer value;
}
Map<ID,Value> map = new Map<>();

Now I want to merge entries together, new value is the sum of old values, but what I have created are entries with duplicate keys and old values instead. Anyone has any idea how to solve this?

EDIT1: I overrode the equals() and hashCode() already, sorry for not showing it here, the Map still have duplicate key entries!

EDIT2: I have uploaded the full code of my class for the keys

You have not defined `hashCode` and `equals` for your `ID` – Cratylus Nov 23 '17 at 19:54 — Cratylus, Nov 23 '17 at 19:54

naXa stands with Ukraine · Answer 1 · 2017-11-23T19:50:32.880

When the hashCode() and equals(Object o) methods are not overridden by your key class (ID), Java just uses the actual reference to the object in memory (pointer address) to calculate the values (i.e. to check if it is the same instantiation of the class). That's why you get duplicate keys (Java "thinks" all results are unique).

To solve this you need to override both methods, equals() and hashCode().

class ID {
    private String id;

    public String getId() { return id; }
    public String setId(String id) { this.id = id; }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if ((obj == null) || (obj.getClass() != this.getClass()))
            return false;
        // safe cast to ID
        ID test = (ID)obj;
        // is id nullable? if so, you need to make an additional null-check here
        return this.getId().equals(test.getId());
    }

    @Override
    public int hashCode() {
        // is id nullable? if so, you need to make an additional null-check here
        return this.getId().hashCode();
    }

}

See Why do I need to override the equals and hashCode methods in Java?

The above code should help you with using your custom class (ID) as a collection key. But I see that there's another one problem in your question:

Now I want to merge entries together, new value is the sum of old values,

Please try to solve it yourself first and (if you do not succeed) post a question that shows your efforts here. Your question, as it's currently written, doesn't show what you have tried.

I have uploaded the full code of my class, as you can see `.equals()` and `.hashCode()` have already been overridden, but merging the key objects still result in the Map have duplicate key entries. — Quynh Vo, Nov 24 '17 at 17:10

fps · Answer 2 · 2017-11-24T17:33:29.457

1

Classes that are used as keys of a Map need to override both the hashCode and equals methods in a consistent manner. (In short, this means that if two instances are equal as per the equals method, then their hashCode method must return the same value).

You are not overriding neither equals nor hashCode in your ID class, so you will get unexpected results whenever you use it as the key of your map.

As per the merging of the values, there's a merge method in Map, which is definitely what you're looking for. If you had i.e. a sum method in your Value class, you could do it as follows:

class Value {
    Integer value;

    Value sum(Value another) {
        value += another.value;
        return this;
    }
}

Map<ID, Value> map = new HashMap<>(); // Map is an interface, 
                                      // you need an actual implementation

map.merge(someId, someValue, Value::sum);

edited Nov 24 '17 at 17:33

answered Nov 23 '17 at 20:02

fps

33,623
8
55
110

Let me update you with the full code of my program, I should have done this from the beginning. – Quynh Vo Nov 24 '17 at 16:55
As for the meaning of the boolean hash, I am supposed to process very large datasets, so I supposed if there is a way to remember that the hashCode has already been computed, it will cut down some of the computation. So the hash is for that purpose – Quynh Vo Nov 24 '17 at 16:57
@QuynhVo OK, so you are caching the hash code. That makes sense, if the set of ids is very large, and *only if you have noticed a degradation in performance*. Otherwise, you would be doing premature optimization, which never leads to good results. Why don't you just try with `return this.ids.hashCode()` and see what happens? Same for `equals`: just try with `return this.ids.equals(o.ids)`. – fps Nov 24 '17 at 17:04
Sure, I will take your advice and see what will happen, still, my question lies in whether we can merge entries in Map if there are duplicate key? – Quynh Vo Nov 24 '17 at 17:13
@QuynhVo I have already answered to that: use the `merge` method. – fps Nov 24 '17 at 17:15
I have read the `merge()` doc, in my understanding it says that it will merge a list with an existing list value through a mapping function i.e. in your program, if the map contains `somekey`, it will simply add up the current value with `someValue`, it does not have anything to do with duplicate keys – Quynh Vo Nov 24 '17 at 17:18
@QuynhVo A map cannot have duplicate keys, that's the idea. Only one key, and one value for each key. If you try to put an entry into a map by using an already existent key, then the entry will be overwritten, i.e. the old value will be replaced with the new value. Unless you use merge, in which case the new value is merged with the old value (in your case they will be summed). – fps Nov 24 '17 at 17:29

Merge entries in Map

2 Answers2