1

I have a class with its own hashCode() method. I am adding this class to a HashSet. How can I remove an item by its hashCode, without knowing the object itself?

For example, if I have the following code

HashSet<Data> set = new HashSet<>();
set.add(new Data(10, 5));
...
class Data {
    public int importantVal;
    public int notImportantVal;
    //... constructor ...
    @Override
    public int hashCode() {
        return importantVal;
    }
}

and I knew the importantVal of a Data object, but not the object itself. How would I remove it? set.remove(10) does not work.

Best solution I can think of is to also override equals() to return if importantVal is the same, and then do set.remove(new Data(10, anyPlaceholderValue))

I am looking for a O(1) solution. I obviously know how to loop through the HashSet and check each element, but that is too slow.

Will Kanga
  • 652
  • 1
  • 6
  • 12
  • 4
    You do realise that hash codes may not be unique, right? There could be multiple unequal objects in a set, that all have the same hash code. Do you want to remove all of them in that case? – Sweeper May 19 '21 at 05:52
  • 2
    "Best solution I can think of is to also override `equals()` to return if `importantVal` is the same". So `equals` _isn't_ implemented like that right now? How is `equals` implemented then? – Sweeper May 19 '21 at 05:55
  • I think if importantVal is unique for all objects then set.remove(new Data(10, anyPlaceholderValue)) will give O(1) complexity. But only if equals method is defined correctly. – Sergey Afinogenov May 19 '21 at 05:55
  • 2
    Sounds like you should be using a `Map` instead of a set. – khelwood May 19 '21 at 05:56
  • Your hashCode and equals method should absolutely follow the same logic?! – GhostCat May 19 '21 at 06:04

1 Answers1

2

No, object required, hash code does not suffice

How can I remove an item by its hashCode, without knowing the object itself?

You cannot.

The hash code is only the first step in tracking an object within a HashSet or HashMap.

Hash codes are not necessarily unique. Two different objects may coincidentally have the same hash code result. Such collisions are expected.

So a hash-based collection is built to secondarily track the colliding objects as a group, and work through them by using the equals method. Equality is used to differentiate between objects that happen to produce the same hash code calculation result.

So you cannot retrieve an object from a hash-driven collection using only its hash code calculated value. The original object is needed for the equality test.

And this explains why your equals and hashCode methods must use mutually consistent logic. And, of course, never override one without overriding the other.

See: How does a Java HashMap handle different objects with the same hash code?.

Map

If you want to track objects for speedy retrieval by a particular property of that class such as a unique identifier, use a Map rather than a Set. A map tracks key-value pairings.

For example, we want to track each person by their assigned identifier, a UUID.

record Person ( UUID id , String name , String phone ) {}

So we define a mapping of UUID to Person.

Map< UUID , Person > map = new HashMap<>() ;

Instantiate an object of that class.

UUID id = UUID.fromString( "5595d84e-b86b-11eb-8529-0242ac130003" ) ;
Person alice = new Person( id , "Alice" , "555-1234" ) ;

Add a Person object to the map.

map.put( alice.id() , alice ) ;

Retrieve.

Person x = map.get( UUID.fromString( "5595d84e-b86b-11eb-8529-0242ac130003" ) ) ;
Basil Bourque
  • 303,325
  • 100
  • 852
  • 1,154