How does a hashSet admit elements

Question

I have a list of objects that I need to add to a HashSet, say List<Node> books. Say further that no two books are equal in the very sense that their equals method would each return false; say, however, that their hashCode method each return 1. I am using this extreme case so that I can understand fully how admission works. So my question is this: Will the HashSet admit all my objects?

public class Book{
  ...
  @Override
  public boolean equals(Book other){
    return false;
  }

  @Override
  public int hashCode(){
    return 1;
  }
}

recall that hashSet does not admit duplicates.

I am wondering about this because by the very name a hashSet uses a hash of the object. Is that hash by any chance related to the hashCode of the object being added?

And yes I am aware of

Adds the specified element to this set if it is not already present. More formally, adds the specified element e to this set if this set contains no element e2 such that (e==null ? e2==null : e.equals(e2)). If this set already contains the element, the call leaves the set unchanged and returns false.

But how are the hashCode of the object related to its hash value in the HashSet?

possible duplicate of [Hashcode and Equals for Hashset](http://stackoverflow.com/questions/5396939/hashcode-and-equals-for-hashset) — user1717259, Apr 30 '15 at 15:35

npe · Accepted Answer · 2015-04-30T15:41:50.603

A Set is composed of buckets to speed up searching. When new object is added to a Set, its hash is evaluated using object's hashCode() method.

Then, based on that hash, the Set decides which bucket the object is to be stored in.

Then, when you search for an object inside that Set (using for example contains() method), the hash is evaluated again, and then the Set iterates over all the elements in a single bucket (instead of iterating over all elements of a Set). This makes it much faster, because - usually - set elements are distributed (more or less) equally among many buckets.

In your case, all the objects will be stored in a single bucket, thus your Set will not really work differently (performance-wise, that is) than a List.

And answering the original question: Yes, it will store all your objects as long, as their equals() is implemented correctly.

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

1

Use this answer: How does a Java HashMap handle different objects with the same hash code? and the information, that HashSet<E> is just a HashMap<E, Object>.

edited May 23 '17 at 12:14

Community

1
1

answered Apr 30 '15 at 15:35

muued

1,666
13
25

score 0 · Answer 3 · edited May 23 '17 at 12:14

I'm slightly confused by your question. The HashSet will use the hashCode() method of the element you add (the List<Node> books in this case). So if you add the List itself, HashSet will call hashCode on the List, not on Book, unless you add the Book elements individually. If you add them individually, it was call the hashCode() you defined in your question.

As a side note, don't ever return a constant value in your hashCode(). See Best implementation for hashCode method

How does a hashSet admit elements

3 Answers3