How HashSet is working when adding variable

Question

As I know HashSet is not adding duplicate variable, but if I have the code:

public class A {
int i, j;
public A(int i, int j) {
    this.i = i;
    this.j = j;
}
public static void main(String[] args) {
    Set<A> s = new LinkedHashSet<>();
    s.add(new A(3,1));
    s.add(new A(1,3));
    s.add(new A(3,1));
    s.add(new A(3,1));
    s.add(new A(2,1));
    System.out.println(s.size());
}

To make sure to not duplicate the variable when I add them to s, I need to override HashCode and equals, but I want to know how Set is working when he adds some variables to the list? What did he check to verify that the Object are not duplicate?

"*To make sure to not duplicate the variable when I add them to s, **I need to override HashCode and equals***" ... "*What did he check to verify that the Object are not duplicate?*" You literally wrote the answer in the previous sentence. — Michael, Jul 29 '21 at 09:19
Yes, but how did he check it to print the size. For example, to print that the size if 4, how I need here to implement hashcode and equals — Pedro Gómez, Jul 29 '21 at 09:22
What do you mean how? Is your question about how to properly implement `hashCode` and `equals`? — Henry Twist, Jul 29 '21 at 09:28
No, my question is if there is a way to implement `hashCode` and `equals` so that the size of the `HashSet` in the main will be 4 — Pedro Gómez, Jul 29 '21 at 09:29
You didn't mention that in your question at all. But regardless, I'm not sure why it would ever be 4? You have 3 duplicates (`A(3, 1)`) so the size would be 3? — Henry Twist, Jul 29 '21 at 09:32
@PedroGómez All you need to do is to implement equals() so that it works correctly, then any version if hashCode() that satisfies the contract will work, even ``return 1;``. I'm not saying to do that, but it will work for this assignment. — NomadMaker, Jul 29 '21 at 10:03

score 2 · Answer 1 · answered Jul 29 '21 at 09:19

2

A HashSet is actually a HashMap where the value is always the same.

The way a HashMap / hashtable work is, It generates hashes of keys (objects) and positions them into a table. Then each time you look for a key, its hash is computed and the bucket in the table is referenced directly.

This means you have just one operation (best case) to access the map. The HashSet simply contains the keys, So .contains(..) gives time-complexity of O(1) and remove(..) also give the time-complexity of O(1) they are the only operations of a HashSet, So it is faster than an ArrayList which have a time complexity of O(n). Iteration is giving the same time complexity.

answered Jul 29 '21 at 09:19

Maneesha Indrachapa

882
5
18

Thanks! So for example for this case, can I create a hashcode so that the size will be 4? – Pedro Gómez Jul 29 '21 at 09:27
1

Yes, you can create, right now what's happening is you create `objects` and each 'object` is unique, you can follow this to get and idea of implementing with unique objects https://stackoverflow.com/questions/3692426/hashset-does-not-seem-to-realize-that-two-objects-are-the-same – Maneesha Indrachapa Jul 29 '21 at 09:47

How HashSet is working when adding variable

1 Answers1