CODEWITHSUNDEEP
javaequalshashset
Amaar
Amaar

Reputation: 337

Create a HashSet that uses a custom condition instead of equals

Here is the structure of the class that I am working with:

public class Foo {
    private final Bar bar; //Bar is immutable
    private int state;

    public Foo(Bar bar, int state) {
        this.bar = bar;
        this.state = state;
    }

    public Bar getBar() {
        return bar;
    }

    public int getState() {
        return state;
    }

    public void setState(int state) {
        this.state = state;
    }

    @Override
    public int hashCode() {
        return Objects.hash(bar, state);
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Foo)) return false;
        Foo other = (Foo) obj;
        return Objects.equals(bar, other.getBar()) && state == other.getState();
    }
}

The problem I am encountering is the following:

Bar bar = ...;
Foo foo = new Foo(bar, 0);
Set<Foo> set = new HashSet<>();
set.add(foo);
foo.setState(1);
set.remove(foo); //foo is not removed!

The element foo is not removed from the set because its hashcode changed as a result of foo.setState(1) and thus the hash set is not able to find it. The functionality that I want is for the HashSet<Foo> to organize its hash buckets and check for equality using foo.getBar(). Something along the following lines:

Bar bar = ...;
Foo foo = new Foo(bar, 0);
Set<Foo> set = new HashSet<>(Foo::getBar);
set.add(foo);
foo.setState(1);
set.remove(foo); //foo is removed since oldFoo.getBar().hashCode() == newFoo.getBar().hashCode() && Objects.equals(oldFoo.getBar(), newFoo.getBar())

To accomplish this, I came up with the following class:

public class KeyExtractedHashSet<T, K> extends AbstractSet<T> implements Set<T> {
    private final Map<K, T> map;
    private final Function<? super T, ? extends K> keyExtractor;

    public KeyExtractedHashSet(Function<? super T, ? extends K> keyExtractor) {
        map = new HashMap<>();
        this.keyExtractor = keyExtractor;
    }

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public Iterator<T> iterator() {
        return map.values().iterator();
    }

    @Override
    public boolean add(T t) {
        return map.put(keyExtractor.apply(t), t) == null;
    }
}

Are there any potential problems with this approach?

Upvotes: 1

Views: 1075

Answers (1)

davidxxx
davidxxx

Reputation: 131456

Implementing its own Set implementation is a hard job, easily error prone or less efficient.
For example, HashSet overrides and optimizes multiple methods implemented in parent classes (AbstractCollection and AbstractSet).

For example what about contains(Object o) ?

You inherit from that defined in AbstractCollection that has a O(n) time complexity and that is normal as a abstract collection doesn't have an abstraction level that allows to iterate faster on its elements : 

public boolean contains(Object o) {
    Iterator<E> it = iterator();
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)
                return true;
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                return true;
    }
    return false;
}

while you could do that with your map as the O(1) time complexity implementation of HashSet: 

public boolean contains(Object o) {
   return map.containsKey(o)   
}

But since foo elements are stored in values of the map, you should rather do :

public boolean contains(Object o) {
   return map.containsValue(o);   
}

But it will not work as expected since Foo.equals() considers the state field that you want to ignore. And besides map.containsValue(o) is not O(1) either as it iterates potentially on all elements of the map.

Same issue for remove(Object o).

As another example imagine that :

Set<Foo> foos = new KeyExtractedHashSet<Foo, Bar>();
// populate, remove...

And later a method creates a new Set from foos : 

Set<Foo> someFoos = foos.stream().filter(...).toSet();

someFoos is no more a KeyExtractedHashSet. It can easily be forgotten.

Long story short : you should reconsider your design and favor immutable objects as keys of your HashSet as this is advised.

Upvotes: 1

Related Questions