What is the best method to treat multiple objects, without retreating already treated objects?

user_10291218 0
Viewed 128

Say I'd like to treat multiple objects of some class Object over the course of some higher level algorithm, with some method treat(Object o). In this algorithm, identical objects may occur (not having the same address), and so I don't want to treat every one of these identical objects, only the first one appearing, ignoring others.

A simple solution would be to implement an ArrayList structure to stock all already treated objects, named treated, and do as follows. 

if (!treated.contains(o)){
    treat(o);
    treated.add(o);
}

However, I think the contains method runs in linear time, whereas using a HashSet instead of an ArrayList would be able to do it in constant time.

Here is my problem though : same hashcodes do not ensure equality. In other words, using HashSet treated as follows :

if (!treated.contains(o)){
    treat(o);
    treated.add(o);
}

might not treat all distinct objects, since some object o1 might end up having the same hashcode as a different object o2. If o1 is treated, then o2 will not be, and vice versa. Would a HashMap treated, used alongside some equals(), be better suited for my problem? 

if (treated.containsKey(o.hashCode())){
    Object o2 = treated.get(o.hashCode());
    if (!o.equals(o2)){
        treat(o);
    }
} else {
    treat(o);
    treated.put(o.hashCode(), o);
}

What would be the recommended method to this problem?

NB : I've seen comments about using a "perfect hashcode", i.e. a hashcode assigning a unique value to every unique object, thus not obtaining similar hashcodes for different objects. I don't see this as a solution, since (theoretically speaking) I can have any amount of distinct objects to treat, whereas hashcodes are of type int which effectively limits the amount of distinct hashcodes.

arraylist hashcode hashset equals java
1 Answers

In other words, using HashSet treated as follows [...] might not treat all distinct objects, since some object o1 might end up having the same hashcode as a different object o2

This is based on a mistaken assumption that HashSet.contains only checks the hash code. It doesn't - it uses the hash code to find equal candidates, but then checks for actual equality with equals as normal.

From the contains method documentation:

Returns true if this set contains the specified element. More formally, returns true if and only if this set contains an element e such that Objects.equals(o, e).

user_226560
Related