What difference exactly will come for this case if I override hashcode and equals?

[Monica Shiralkar]

Stephan van Hulst wrote:What does it matter? Isn't it enough that HashSet's internal consistency depends on the correct implementation of equals() and hashCode(), regardless of what method you call?

Thanks. I think I understood now.

[Monica Shiralkar]

Thanks. I think I understood this time.

It is the basic nature of HashSet (being a Set) that one cannot insert duplicates in it.

From what I understand, for a HashSet if one does not override the equals and hashcode, it will allow duplicates (since every element is unique unless these 2 methods are overridden). Thus, in that case it would not even behave like a set.

[Stephan van Hulst]

You're putting the cart before the horse. Don't implement equals() just to tell Set how to behave. The equals() method DEFINES which objects are equal. YOU decide which objects are equal by implementing equals(). Set just says: "Oh, these two objects are equal? Then I'll make sure I don't contain them both at the same time".

Set simply does not allow duplicates, period.

If you don't override equals and hashCode(), you still won't be able to put duplicates in the set, because by DEFINITION two separate instances will be unequal to each other.

[Monica Shiralkar]

Stephan van Hulst wrote:You're putting the cart before the horse.

Yes, what I said was incorrect.

I think the correct statement  would instead be that if one uses HashSet but doesn't override equals and hashcode methods , then there would be no point in using a Set (which by its nature doesn't allow duplicates) ,when duplicates would not even be a possibility in the first place (as equals and hashcode are not overridden).

Is that correct?

[Stephan van Hulst]

No.

If you don't override equals(), you will still be able to add multiple references to the same object to a List.

If you don't override equals() and hashCode() you will NOT be able to add multiple references to the same object to a Set.

The latter can be useful if you're storing services in a set, because even though every instance is unequal to every other instance, you don't want multiple references to the same service instance in your set.

[Monica Shiralkar]

Thanks. I understood that

"If you don't override equals() and hashCode() you will NOT be able to add multiple references to the same object to a Set."

However, what I did not understand is that why is the below statement wrong:

if one uses HashSet but doesn't override equals and hashcode methods , then there would be no point in using a Set (which by its nature doesn't allow duplicates) ,when duplicates would not even be a possibility in the first place (as equals and hashcode are not overridden)

[Monica Shiralkar]

I have a question. In which scenario does the case arises that two objects have the same hashcode but are not equal?

[Monica Shiralkar]

Overall, below is my understanding on hashing , hashcode and equals methods.

1. Hashing is the concept used by some collections like HashSet,HashMap and HashTable for faster retrieval performance.
2. Instead of having the elements scattered all over the memory, if those are stored in the hashbuckets based on hashcode, then the retrieval would be fast. A Hashbucket is like address of object in memory.
3. Each object has a hashcode value and by default each object is unique.
4. Objects with similiar hashcode are stored in the same hashbucket. This does not mean that along with these this bucket does not have other objects with other hashcodes.
5. For using the objects as elements in HashSet or as keys of HashMap, the class should implement the hashcode and equals method. The latter wiill have the conditions based on which objects would be considered duplicates.
6. While retrieving from a hash based collection, it would first locate the element (i.e find its hashbucket based on hash value) and since there would be multiple objetcs there equals will help in finding the element.
7. If two objects are equal as per the equals method those should have similiar hashcode. Whereas if two objects have same hashcode they may or may not be equal.

Please correct me if I am wrong.

[Jesse Silverman]

Hi Stephan:

First I'd like to apologize for possibly adding to Monica's confusion earlier by making some next-level statements before I ensured we were on the same page so far.

In retrospect I would have clarified some of the points or asked her to explain them to me in her own words before doing so.

I feel like while we are still (collectively) on slightly shaky ground you are highlighting a use case that is relatively rare, where we actually care about the reference identity per se of the key or element:
https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/util/IdentityHashMap.html#%3Cinit%3E()

Earlier in the thread, I was trying to work out just exactly what was going to be based on or depend on our Override of .equals(Object o) for our class.

For my own code I can use all sorts of custom tests or predicates to decide all sorts of things on my own.

But my .equals(Object o) override for my class will completely determine the results of (at least) the following:
.contains(), .containsAll(), .remove(), .removeAll(), .retainAll() from Collection [in any Set, List, or Queue or Deque they might go into]

The behavior of any HashMap oriented methods using objects of my class as keys....telling us whether a key was or was not found....

Other things that I am not thinking of at the moment.

It is true that List structures will allow storage of multiple duplicates of objects that compare .equals(), and that Set and Key-based ones will not.

I'd just want to make sure that we are all aware, most of the time, normally, we are concerned across the whole Collections Framework with a consistent defined notion of value content .equals() for a class, and that actually intending to use reference equality in the Collections Framework is considered a relatively rare special case that many average developers may never need to use.  I am basing this on a presentation I saw including IdentityHashMap by one of the team at Oracle that worked on it.

[Jesse Silverman]

Hi Monica:

I like almost everything about your latest summary of your understanding of the hash-based data structures, with the possible exception of:

A Hashbucket is like address of object in memory.

I wouldn't say that statement.

You may have references to the same object that happen to be stored in three lists, two HashSets and a few HashMap or TreeMap objects.

In a given particular HashMap or HashSet, at a given moment, the storage of your object in that particular HashMap or HashSet will be in one of the buckets that make it up at the time.

If we add just possibly even one more element, to maintain performance, when the total number of entries in that particular HashSet or HashMap reaches the number of buckets times the loadFactor we set for it in its construction (defaulting to 0.75 if we do not specify it)...the whole thing gets automatically re-hashed, with each object finding itself having new neighbors in its new bucket in some way that could in theory be predicted, but is way beyond the level of detail anyone not writing the Collection Framework for us would normally pay attention to.

This won't affect what bucket the same reference will be found in for any *other* hash-based structure it may also be in, nor will it affect anything about any List or Queue-based structure that reference might also happen to be in, nor anything about any of our own classes that might have one of our objects in it.

So "which bucket is my object in" is a temporary and changing property of any particular hash-based data structure true only at that time for only that one structure.  There will be a different answer for any other hash-based structures the same object is also stored in even at the same moment, and it will change over time as objects are added to the structure.

What is constant and in common for all of these everywhere, is your good old .hashCode() value, which will be the same for any combination of data that would make .equals() true.

When I am talking about all the different structures your object might be, let's say your studentID might be found as a key in a AddressByStudentId HashMap, a gradesByStudentId HashMap, and a HashSet of StudentId  elements representing Computer Science students at the school.

That may have been an unnecessarily long answer to why I didn't like the phrase "A Hashbucket is like address of object in memory." despite liking every other thing which you said in that post.

[Paul Clapham]

Monica Shiralkar wrote:I have a question. In which scenario does the case arises that two objects have the same hashcode but are not equal?

There is an unbelievably large number of String objects, all of which have hash codes of course. But there's only 2^32 possible hash codes. So that tells us that there must be at least two String objects with the same hash code. Most likely there's an unbelievably large number of String objects whose hash code is zero, for example. And an unbelievably large number whose hash code is -10377643. And so on.

So if you have a class of objects with a String value which is part of the rules for equality of those objects, then you're probably going to use the hash code of that String to compute a hash code for those objects. Your code might only have a few thousand of those objects but it would still be possible for two objects which aren't equal to have the same hash code. But of course you don't care about that because it's quite all right for that to happen, isn't it?

[Campbell Ritchie]

Monica Shiralkar wrote:Overall, below is my understanding on hashing , hashcode and equals methods.

1. Hashing is the concept used by some collections like HashSet,HashMap and HashTable for faster retrieval performance.

No. Hashing is a way to reduce an object to a number

2. Instead of having the elements scattered all over the memory, if those are stored in the hashbuckets based on hashcode, then the retrieval would be fast. A Hashbucket is like address of object in memory.

That sounds all confused, as if you didn't know the difference between a memory location, a pointer, and a reference. The bucket indirectly contain references to the objects in question, which might be anywhere in heap memory.

3. Each object has a hashcode value and by default each object is unique.

That is a platform specific implementation detail. C has structs rather than what we call objects, and they don't return hash codes by default. You would have to create a function to calculate a hash code.
What is meant here by "unique"?

. . . 5. For using the objects as elements in HashSet or as keys of HashMap, the class should implement the hashcode and equals method. The latter wiill have the conditions based on which objects would be considered duplicates.

“implement”? Surely you meant, “override”?
You have already been told that the equals() method defines which two instances are and are not equal to each other. Yes, you can use objects with un‑overridden equals() and hashCode() in hash‑based data structures, and I think you have already been told how such data structures will behave.

. . . 7. If two objects are equal . . . those should have similiar hashcode. . . .

You mean they must have the same hash code. Not “similar”.

[Jesse Silverman]

Campbell Ritchie wrote:

Monica Shiralkar wrote:Overall, below is my understanding on hashing , hashcode and equals methods.

1. Hashing is the concept used by some collections like HashSet,HashMap and HashTable for faster retrieval performance.

No. Hashing is a way to reduce an object to a number

2. Instead of having the elements scattered all over the memory, if those are stored in the hashbuckets based on hashcode, then the retrieval would be fast. A Hashbucket is like address of object in memory.

That sounds all confused, as if you didn't know the difference between a memory location, a pointer, and a reference. The bucket indirectly contain references to the objects in question, which might be anywhere in heap memory.

3. Each object has a hashcode value and by default each object is unique.

That is a platform specific implementation detail. C has structs rather than what we call objects, and they don't return hash codes by default. You would have to create a function to calculate a hash code.
What is meant here by "unique"?

. . . 5. For using the objects as elements in HashSet or as keys of HashMap, the class should implement the hashcode and equals method. The latter wiill have the conditions based on which objects would be considered duplicates.

“implement”? Surely you meant, “override”?
You have already been told that the equals() method defines which two instances are and are not equal to each other. Yes, you can use objects with un‑overridden equals() and hashCode() in hash‑based data structures, and I think you have already been told how such data structures will behave.

. . . 7. If two objects are equal . . . those should have similiar hashcode. . . .

You mean they must have the same hash code. Not “similar”.

Happy New Year everyone!
This definitely illustrates to me that if you want to really know you know something, try to teach it to someone who doesn't yet know it or is confused by points of it.

1. Yes, hashing is the process of producing a number based on the identity, or the contents of an object.  
Any code that we, or the rest of our teams write, could possibly depend on the values returned by .hashCode() and .equals().
During this long thread I was attempting to determine all of the parts of the Collections Framework, or possibly the standard Java classes in general, that might depend on our implementations of .hashCode() and .equals().
For .equals() that certainly includes at least all of the Collections Framework methods that apply to all classes that implement the Collection interface: .contains(), .containsAll(), remove(), .removeAll(), .retainAll(), and many methods of the Map interface, e.g. containsKey(), containsValue(), and many more.
For .hashCode(), I believe it is clear to both Monica and myself that the workings of HashSet methods and those concerning HashMap keys storing objects of our classes depend on our implementation of .hashCode().  It seems plausible that other parts of standard Java also depend on our .hashCode() implementation for their behavior, but in what she writes there she indicates she is only thinking of it in terms of HashSet and HashMap behavior.  Those are the only places I am currently sure of in standard Java that depend on our .hashCode() implementation for our classes we write, I am ready to learn and remember any others.

2. I agreed with you on how what she wrote there sounded, and wrote a much more verbose explanation of why what she wrote there seemed confused, and why.

3. I took what she said there to mean simply that without overriding the .hashCode() implementation inherited from Object, each instance of an Class will return a unique specific value based solely on its address in memory, regardless of its value contents.  That reading was based on her prior posts in the thread.   A value type has no identity beyond its current value, but Project Valhalla hasn't come to fruit yet, and we can only store reference types that inherit from Object anywhere in the Collection Framework.  If at some point in the future we can store primitive or other value types in Collections, further learning will be required regarding the difference between reference and value types as effects both C# and C++ already, for instance.  I am not sure whether mentioning this at this time adds or removes any remaining confusion she may have about the proper implementation for .equals() and .hashCode() in classes we create in Java.  As someone who had been expecting Project Valhalla to have arrived already, with widespread implications across the Collections Framework and beyond, and someone who is used to making the distinction between value types and reference types in collections in C++ and C#, it means a lot to me longer term, but not in terms of the topic at hand which I take to be:
"What's the deal with .hashCode() and .equals() in Java?  What depends on my implementations of those besides code in classes I write?"
It is relevant to the extent that when implementing our .hashCode() override for our class, we do need to know how to handle any primitive data members, which do not have their own .hashCode() nor any other methods, as they are not instances of classes.
I have seen in either this thread or the other related one, that she has put thought into how to properly do that, and others have suggested how to go about it.
It is something I have started paying attention to, as there is no one right way to do it, but many wrong ways, I think.

Campbell: Thanks so much for your continued patience in explaining this very basic yet still sometimes misunderstood facet of Java.  I have slightly extended the scope of the question from "for this case" in the title to "across my whole program" but I think that is reasonable as the two questions are necessarily related.  When I questioned whether or not it was helpful to bring value types into the discussion here, I may be presuming that people coding primarily in Java have less awareness of the distinctions between value types and reference types than those who also use C++, C# etc. but that is my impression.  I am also confused about where Project Valhalla is at, I expected primitive/value types to be causing widespread relief and confusion across the Collections Framework well before Java 15 but it seems not to have taken place.  I would totally be interested in that topic outside of this thread.

Monica: I hope I am right and justified in seeing that both of us are thinking the importance of our .hashCode() implementation primarily involves the use of objects of our Classes in HashMap and HashSet structures, and that if there are other standard places it is also used, besides in methods we write, we need to become aware of them.

[Campbell Ritchie]

Jesse Silverman wrote:. . . Happy New Year everyone!

Thank you and same to you.

. . . . without overriding . . . .hashCode() . . . each instance of an Class will return a unique specific value based solely on its address in memory . . .

That is what everybody thinks, but it isn't necessarily true. A memory location can change, for example whenever garbage collection happens, and the current API documentation doesn't say anything about memory locations. Some old versions did.

Project Valhalla . . .

Can't arrive too soon.

Campbell: Thanks so much . . .

That's a pleasure but I'm the only person helping you.

distinctions between value types and reference types . . . .

That is because there isn't such a distinction in Java®. After Valhalla, that might be a different story.

[Jesse Silverman]

Hi Campbell:

One thing I was trying to get clear was all the places where what one chooses to write for her .equals() and .hashCode() implementations will make a difference.
Obviously in the code that she writes which explicitly looks at .hashCode() values, or calls .equals() explicitly for sure, but I mean all the standard stuff most programs use without thinking much about.

I went from over-focusing on just HashMap and HashSet to realizing that pretty much more of the Collections Framework methods than not will change behavior based on her .equals() implementation.

While hashing is most certainly a general concept not limited to the Collections Framework nor to Java, are there other places we should be aware of in our Java programs where  our. hashCode() override makes a difference?

One set I found out for myself where .equals() will define the behavior, Arrays.equals() and Arrays.deepEquals() for sure, Arrays.compare() and Arrays.mismatch() are supposed to have results compatible with the .equals(), tho they actually call either the Comparable implementation or the supplied Comparator rather than .equals()...

I see that both sort() and the binarySearch() in sorted collections and Arrays, for instance, depends on Comparable or a supplied Comparator and never looks at either .equals() nor .hashCode().  They don't seem to mention it at all.

So hashing and equality are general concepts not limited to Java or even to programming.
Where will the choices I make for .hashCode() and .equals() be making a difference -- have I now listed all the important ones?

[Monica Shiralkar]

Happy New Year to all.

Campbell Ritchie wrote: as if you didn't know the difference between a memory location, a pointer, and a reference

But pointers do not exist in Java (they exist in C).

Campbell Ritchie wrote:The bucket indirectly contain references to the objects in question, which might be anywhere in heap memory.

Thanks. So instead of saying that elements are stored in hash buckets based on hash code, one should say that the references of elements are stored in the hash buckets based of hashcode and the objects actually are in the heap memory.

Is the difference between any normal java objects and objects stored in hashing based collections that while in case of hashing based collections the class is made to override equals and hashcode (and thus all objects of such a class having the same hashcode are made to go in the same hashbucket to give us faster retrieval performance) whereas in all other cases we don't override these 2 methods and thus references of all such objects are scattered all over the memory?

[Monica Shiralkar]

Paul Clapham wrote: But there's only 2^32 possible hash codes.

Suppose our class has employeeName and employeeAge and the hashCode method is being calculated based on these. How does this limitation of 2^32 come?

[Carey Brown]

Because a hash code is an int and that is the size of an int.

[Monica Shiralkar]

Thanks

[Carey Brown]

That may be the limit on the number of unique hash codes but the number of buckets is typically much, much, much, less. You could have, for example, a HashMap with only 64 buckets.

[Carey Brown]

In which case that particular HashMap instance has to take a given hash code of an int and convert it to a number from 0-63 to determine which bucket it belongs in.

[Monica Shiralkar]

Carey Brown wrote:for example, a HashMap with only 64 buckets.

I was thinking that since hash buckets is for each and every java object it would not make any difference for the number of buckets that whether those are normal java objects or objects that are being stored in a hash based collection like hash map.

[Carey Brown]

An object reference does not go into any hash bucket unless you "put" it there. So, only a select few of the references to all the objects created by a running program end up in hash buckets.

[Monica Shiralkar]

Carey Brown wrote:unless you "put" it there. So, only a select few of the references to all the objects created by a running program end up in hash buckets.

Thanks. I think that means it goes there only for the cases where we are using some hashing based collection like hash code or hash table.


But the hashcode is there for every java object created. So what is the significance of hashcode for normal java objects which we have not intention of storing in any hash based collection?

[Carey Brown]

When you create a HashMap instance, for example, that instance owns its own set of buckets. If you create another HashMap that has its own buckets. The two sets are completely different. The reference to a particular data object may be "put" in either one, or both.

[Monica Shiralkar]

Carey Brown wrote:When you create a HashMap instance, for example, that instance owns its own set of buckets. If you create another HashMap that has its own buckets. The two sets are completely different. The reference to a particular data object may be "put" in either one, or both.

Thanks. Understood.

My question is that since every object has an hashcode, what is the significance of hashcode for any normal java objects which we are not storing in any hash based collection (like hash map , hash set)?

[Carey Brown]

HashMap and HashSet are Collections that use hash code values. HashTable does also but this class is mostly obsolete.

Every object implements hashCode() so that it could be used in a hash Collection or in some other manner of your own design.

[Monica Shiralkar]

Thanks.
So does that mean that  although every object has a hashcode but it will come into significance only if we are using hashing somewhere for e.g while storing in hash based collection like hashmap/hashset/hashtable. ?

[Carey Brown]

A hash code doesn't need to be stored. You can get the value from an object's hashCode() method, use it, and the throw it away. Certainly for any object not in a hash Collection it is highly likely that their hash code is not actually stored but can be computed any time it's needed. It is likely that a HashMap will actually store the hash codes in order to do comparisons while searching.

[Monica Shiralkar]

Thanks.

[Carey Brown]

You might find it an interesting exercise to write your own HashMap or HashSet. Keep it simple (that's a relative term), only hold Strings, only allocate 128 buckets (as a place to start). Figure out how you want to handle the conversion of hash code int's to 128 buckets; how you'll handle when more that one reference needs to be added to the same bucket. I think you'd find this to be an eye opener and I guarantee you'll understand it a whole lot better when you're done.

[Carey Brown]

public class MyHashSet
{

	public MyHashSet() {
		// TODO
	}
	
	public  boolean add( String s ) {
		// TODO
		return true; // place holder
	}
	
	public boolean contains( String s ) {
		// TODO
		return true; // place holder
	}
	
	public boolean remove( String s ) {
		// TODO
		return true; // place holder
	}
	
	public int size() {
		// TODO
		return 0; // place holder
	}
}

[Campbell Ritchie]

I would prefer the placeholder code you get with NetBeans:-public void foo(Foo f) {   throw new UnsupportedOperationException("Not implemented yet."); }

[Monica Shiralkar]

Campbell Ritchie wrote:I would prefer the placeholder code you get with NetBeans:-public void foo(Foo f) {   throw new UnsupportedOperationException("Not implemented yet."); }

I have seen another style of placeholder commonly in C# code too(Visual studio generated).

 throw new MethodNotImplementedException()

[Monica Shiralkar]

Carey Brown wrote: I guarantee you'll understand it a whole lot better when you're done.

Yes, that's true.

[Monica Shiralkar]

Campbell Ritchie wrote:

Monica Shiralkar wrote:Overall, below is my understanding on hashing , hashcode and equals methods.

1. Hashing is the concept used by some collections like HashSet,HashMap and HashTable for faster retrieval performance.

No. Hashing is a way to reduce an object to a number

But I could not understand why is it wrong to say "Hashing is the concept used by some collections like HashSet,HashMap and HashTable for faster retrieval performance."  since ultimately thats the benefit we are aiming to get in Hashing based collections using hashing.

[Campbell Ritchie]

The hash data structure doesn't do any hashing, at least not in Java® (it might in other languages). In Java® each object does its own hashing.

[Monica Shiralkar]

Campbell Ritchie wrote:The hash data structure doesn't do any hashing, at least not in Java® (it might in other languages). In Java® each object does its own hashing.

Thanks. Understood. Every object has a hashcode and overriding this hashcode is useful in cases such as when objects are being stored as keys of HashMap or as elements in HashSet. In such kind of cases hashing is done and is done by the objects themselves (not the hashing based collection).

[Campbell Ritchie]

Monica Shiralkar wrote:. . . Thanks.

That's a pleasure

. . . Every object has a hashcode . . . hashing is done . . . by the objects themselves . . . .

Spot on

[Monica Shiralkar]

I have a question.
If we are making use of hashing and say using objects in hash based collections such as HashMap/HashSet , we override hashcode (and equals ofcourse).
If not so , we do not override the default hashcode method. So what is the significance of the 'default hashcode value' for an object?