HashSets What are they?

Head First Java shows where HashSet  fits in the API Collection tree.

Collection
(interface)
  ^
Set
(interface)
  ^  
HashSet

From reading about Using a HashSet Instead of ArrayList I can tell that HashSet can hold objects.   I have to look for information on What a HashSet is and what a HashCode is.   I think that each object gets its own unique  HashCode in the HashSet but that is all that I know about it.

I'll read about HashSets and read any explanation you can give me.

Thanks,

Kevin

Hash codes are NOT unique!!! Thinking they are will lead you down the wrong path.

Carey,

I looked at the API for HashSet.  All I can tell is that it is a collection of objects.

The book goes from   "Using a HashSet instead of ArrayList."  
to
What makes two objects equal.

It explains Reference equality.  It is fwo references pointing to the same object.  That makes sense.

The next part is Object equality.  I understand that it means "meaningfully equivalent"
My understanding is that the HashCode is inherited from Class Object.  I'm guessing each Object is created with one that has not been allocated before.  

Both hashCode and equals have to match for two or more object to be equal (or pointing to the same object I think??)

Thanks,

Kevin

I think you need to revise some maths before looking at those classes; find out what the difference between a List (sometimes called a sequence) and a Set is.

kevin Abel wrote:I looked at the API for HashSet.  All I can tell is that it is a collection of objects.

A Set is a collection that may not contain the same object more than once. Whether two objects are considered the same is determined by the equals() method. A List on the other hand is an indexed sequence of elements, where the same object may appear more than once.

HashSet is a specific implementation of Set. Its implementation determines how fast it is at storing and looking up objects in the set, and how much memory it needs to store objects. A different implementation of Set is TreeSet, which stores and looks up elements in a different way.

My understanding is that the HashCode is inherited from Class Object.  I'm guessing each Object is created with one that has not been allocated before.

The hashCode() method is inherited from Object, but classes that override equals() must also override the hashCode() implementation. So you can't really say that every object is allocated a hash code. Every object determines its own hash code, based on the properties that also determine whether an object is equal() to another one.

The hashCode() method is necessary for HashSet to quickly look up the location where it has stored an element. So it's really all about performance.

Objects that are equal must also return the same hash code. However, as Carey already pointed out, objects that are not equal are NOT required to have different hash codes.

Here is an example of how you could implement a value type in Java 11:
final class PlayingCard {  private final Rank rank;  private final Suit suit;  PlayingCard(Rank rank, Suit suit) {    this.rank = requireThat("rank", rank, is(notNullValue()));    this.suit = requireThat("suit", suit, is(notNullValue()));  }  Rank rank() {    return rank;  }  Suit suit() {    return suit;  }  @Override  public boolean equals(Object obj) {    if (!(obj instanceof PlayingCard)) {      return false;    }    var other = (PlayingCard) obj;    return this.rank.equals(other.rank)        && this.suit.equals(other.suit);  }  @Override  public int hashCode() {    return Objects.hash(rank, suit);  }  @Override  public String toString() {    return String.format("PlayingCard[rank=%s, suit=%s]", rank, suit);  } }
As you can see, the equality of two playing cards is determined by comparing the rank and the suit of the two cards in the equals() method. The hashCode() method MUST be overridden to return a code that is based on a (subset of) these two properties, and nothing else. In general, an easy way to implement hashCode() is to simply call Objects.hash() with the same properties that you used inside the equals() method.

Starting with Java 16, you can implement such value types very easily using records. It would look like this:
record PlayingCard(Rank rank, Suit suit) {  PlayingCard {    requireThat("rank", rank, is(notNullValue()));    requireThat("suit", suit, is(notNullValue()));  } }
Declaring this type as a record causes it to automatically implement the rank() and suit() methods, and to override the equals(), hashCode() and toString() methods.

Hashes are one-way and collision resistant, meaning that an input value will generate an output that is a fixed length and unique.  
This fixed length will then improve performance when used to compare values within a collection.

Here's Autin Griffith explaining the properties of hash functions.  
His tools Eth.Build are focused on web3/blockchain, but can be used to gain an understanding of the underlying technologies.

Peter Rooke wrote:Hashes are one-way and collision resistant, meaning that an input value will generate an output that is a fixed length and unique.  

It is NOT unique except by chance.

Here's Autin Griffith explaining the properties of hash functions.

By Autin's comparison of a hash to a finger print he implies that it is unique, which is not true. He also said that you could take the hash of "hello world" and figure out the "hello world" was your secret message. This is false, there are an infinite number of messages that would have the identical hash as "hello world".

The idea that hash codes for elements of a particular Java class should be unique is very, very far from being true.

Consider for example the String class. The number of possible String objects is ridiculously enormous -- the maximum length of a String is 2,147,483,647 characters. And there are 65,536 possible values for each of those characters. But every one of those ridiculously-many String objects has a hash code, which must be an int value. In other words, there are only 65,535 possible hash codes.

That means, using the pigeonhole principle, that if you choose an int value at random, there is a ridiculously enormous number of String objects which have that value as their hash code.

Paul Clapham wrote:. . . there are only 65,535 possible hash codes. . . .

The number of different hash codes depends on what datatype they are defined in. CRC codes and SHA256 are all kinds of hash code with their results of different “sizes”. 65535 (=2¹⁶ − 1) is the maximum size of a 16‑bit unsigned binary number, but since 0 is a permissible hash code result, a 16‑bit hash code has 65536 possible different values. Java® uses an int as the return type from hashCode(), and that has 2³² (=4,294,967,296) potential distinct values. That still means the possible number of Strings is large; it is too large for even BigInteger to calculate.

kevin Abel wrote:I think that each object gets its own unique  HashCode

Peter Rooke wrote:Hashes are one-way and collision resistant

As already been mentioned, collisions can happen. In case you wonder how is that possible.

Theoretical proof.

Hash code is of type int. An int in Java has a range of -2147483648 to 2147483647, that means, roughly about 4 billions hash codes.

Now, take an English alphabet, that has 26 letters A-Z (times 2 if you consider lower case as well).

So now you can start building permutations:
A, a, AA, Aa, aA, aa, B, b, BB, Ba, bB, bb, AB...

You get an idea.

Having 26 letters at your disposal and 7 characters string, you can build 26^7 = 8_031_810_176 variants of string (8 billions), which already exceeds possible number of hash codes - so they must collide.

None of this discussion mentions the reason for the existence of HashSet and hashCode in the first place. What's the point, anyway?

Okay. We want to have a Set, so we can corral a bunch of objects which are all different. Duplicates can be annoying for many tasks. So what does that imply? For one thing, when you add an object to a Set you need to make sure it isn't the same as an object which is already in the Set. So how to do that? Simplest way: compare the incoming object to all the objects which are already there, and ignore it if it's equal to one of them.

Okay, that would work fine, so why don't we have that in Java? It's because after you've added a few thousand entries to your Set, it gets slower and slower to add a new entry. That's a Bad Thing because it will make people say Java is slow. So here's the trick: We'll add a value called "Hash Code" to every object which is going to be put into a Set. This code should be the same for two objects which are equal, but it should try to be different for two objects which are not equal. That first part is non-negotiable but the second part isn't always possible.

Then when you go to add an object to a Set, you look at its hash code. If it's different than the hash code of the entries which are already in the Set then it's new and you can accept it. If the hash code the same as one of the entries in the Set, it still might be not equal to that entry, so you have to compare the two.

So how is this better? Looks like you still have to compare the new entry to all of the existing entries, only with more complicated machinery. The trick is that you're comparing int values, so you can build an index which maps hash codes to objects, sort of. Then you just have to look at the index instead of looking at all of the entries.

It's a lot more complicated under the hood but you don't need to know about all that (until you decide you want to work on this kind of optimization). Short story is that adding a new entry is no longer O(N), it's now O(1). You pay for that improvement by having to write code which produces useful hash codes for your objects.

I still think OP should start off by learning what the difference is between Sets and Lists, never mind how they are implemented.

take a list and run it thru a for loop, append each item to a set, the set removes all duplicates from the list, that's how you make a set. as was already said, a set is the same idea as a set in mathematics, so there's no need to use an if-statement to prevent duplicates getting added into a set, duplicates are prevented automatically.
list: red, blue, green, green, red ----> set: red, blue, green

i think there is also a convenience method in collections to add everything to a set, or you could do it with a lambda, lots of ways to do it.
hashset is backed by a hashmap, but there's also a treeset, i think the set interface you'd probably never need in your entire life.
hashset and treeset are all i ever needed.

im not too sure how java decides if 2 objects are equal, but you can override their default behavior with your own equality operator as needed.

comparing can be a bit tricky for those new to java, you have to use String::equals() instead of == operator when comparing strings.
the equals() method is basically the same as strcmp in C, and == is probably just comparing the memory address of 2 objects to see if they're the same.
using == on two different string objects will be a result of not equal, even if the text of both objects is identical.

S Fox wrote: i think the set interface you'd probably never need in your entire life

Oh, I almost use it daily.

Set<String> alphabet =  new HashSet<>();Set<String> alphabet =  new TreeSet<>();

yeah i meant all you really need is HashSet and TreeSet, i have never needed to implement the set interface itself to create a custom type of set.

S Fox wrote:yeah i meant all you really need is HashSet and TreeSet, i have never needed to implement the set interface itself to create a custom type of set.

Ah, me neither. But I trust that's not absolute.

[edit]This post was written before I saw the three posts before it.[/edit]

S Fox wrote:take a list and run it thru a for loop, append each item to a set

i think there is also a convenience method in collections to add everything to a set

I wouldn't call it a convenience method. "Convenience method" implies that the only benefit is that the programmer can write the code more simply.

For many collection implementations, calling addAll() once may have some significant performance benefits over calling add() multiple times. If you already have a collection of objects that you want to add to a set in its entirety, there's never a good reason to do it with a loop.

i think the set interface you'd probably never need in your entire life.

You should always "code to an interface", if you can. If the Set interface contains everything you need, there is no reason to declare a variable as HashSet or TreeSet. If you declare a variable as an implementation type, it makes it harder for you to refactor the code when you later decide you want to use a different implementation. Even worse, when you have a public API with a method that accepts a HashSet when you only need Set, you are limiting the clients of your public API in how they can use the API.

Let's say you're writing a public library that contains all sorts of utilities for working with mathematical sets, and you've written a method that returns the intersection of two sets:
public static <E> HashSet<E> intersectionOf(HashSet<? extends E> firstSet, HashSet<?> secondSet) {  HashSet<E> result = new HashSet<>(firstSet);  result.retainAll(secondSet);  return result; }
Now, if I want to use your library, but I've decided that I need a TreeSet in my application, I have a problem when I want to call the interectionOf() method:
TreeSet<Integer>  firstSet = calculateFirstSet(); TreeSet<Integer> secondSet = calculateSecondSet(); var intersection = intersectionOf(firstSet, secondSet); // This doesn't compile
Now I first need to convert my TreeSet to a HashSet before I can call your method, for no reason other than that you didn't declare your method to use Set instead of HashSet.

im not too sure how java decides if 2 objects are equal, but you can override their default behavior with your own equality operator as needed.

Method, not operator.

For objects that don't have their equals() method overriden, Java just uses the == operator, which, as you already pointed out, compares the memory addresses of the objects.

S Fox wrote:. . . im not too sure how java decides if 2 objects are equal

I thought that had already been explained in this thread.

but you can override their default behavior with your own equality operator . . .

That is very imprecise. You cannot override operators in Java® at all. You have to override methods.

. . . the equals() method is basically the same as strcmp in C

I don't think OP knows about strcmp. Although String#equals() and strcmp can both tell you whether two bits of text would read the same, they are different. For a start, a Java® String is a full‑blown object, whereas text in C can sort of degenerate to a pointer to its first character. It even says in the Java® Language Specification (=JLS) that the two are different datatypes. I don't think that C supports strings as a distinct datatype, but uses char[]s instead. Remember too, the char datatype in Java® is different from the similarly named datatype in C.

. . .== is probably just comparing the memory address of 2 objects to see if they're the same. . . .

There is no “probably” about it. The behaviour of == is strictly defined in Java®.

Stephan van Hulst wrote:. . . For objects that don't have their equals() method overriden, Java just uses the == operator . . .

What Stephan means, is that an un‑overridden equals() method uses == as a default, as that link will tell you.

Just to see how a hash set might be implemented.
import java.util.LinkedList; // An example of a hash set implementation stripped to the bare // bones. // 1) Only supports a payload of String. // 2) The bucket array is a fixed size and will not grow as they //    get filled - leads to more collisions and slower performance. // 3) Only supports add(), remove(), and print(). // 4) The ARRAY_SIZE must be a power of 2 so that the string's //    hash code can be reduced to the least significant N bits.   public class HashSet4Strings { private static final int ARRAY_SIZE = 4096; private LinkedList<String>[] array = (LinkedList<String>[]) new Object[ ARRAY_SIZE ]; public void add( String s ) { // least significant 12bits int hashCode = s.hashCode() & (ARRAY_SIZE-1); LinkedList<String> list = array[ hashCode ]; if( list == null ) { list = new LinkedList<>(); list.add( s ); array[hashCode] = list; } else if( ! list.contains( s ) ) { list.add( s ); } } public boolean remove( String s ) { // least significant 12bits int hashCode = s.hashCode() & (ARRAY_SIZE-1); LinkedList<String> list = array[ hashCode ]; if( list == null ) return false; return list.remove( s ); } public void print() { for( int i=0 ; i < ARRAY_SIZE ; i++ ) { LinkedList<String> list = array[ i ]; if( list != null ) { for( String s : list ) { System.out.println( s ); } } } } }

Campbell wrote:I think you need to revise some maths before looking at those classes; find out what the difference between a List (sometimes called a sequence) and a Set is.

I worked with data sets in BASIC and VBA although at the time didn't know they were called sets. They have arrays and keyword/data pairs. I don't recall anything that behaved like a list.  

I remember seeing link-lists in C so I know what lists are.  It's items stored as one long amount of items.  There is no random access.  I have to look at one item at a time to find out what it is.

Many people answered my question in this thread.  I'll take some time off from the book and read here for a while.

Thanks all,

Kevin

Carey Brown wrote:Just to see how a hash set might be implemented.

Just a small note: Most hash tables distribute objects over their buckets using a function that involves the % operator, not the & operator.

[edit]The above is factually false. See the conversation below[/edit]

kevin Abel wrote:I worked with data sets in BASIC and VBA although at the time didn't know they were called sets.

Be careful. The term "data set" generally refers to something other than a mathematical set. The term is poorly defined and data sets may indeed contain duplicate entries, depending on the context in which the term is used.

I remember seeing link-lists in C so I know what lists are.  It's items stored as one long amount of items.  There is no random access.

Once again, be careful. Linked lists may not be random access, but that doesn't mean that there aren't lists that ARE random access. In Java, the most commonly used List implementation is ArrayList, and it provides random access just fine.

These are the most important differences between lists and sets that you should remember:

Lists may contain duplicates, sets must not.

Lists are always ordered, sets might or might not.

Elements of a list can be retrieved by index, elements of a set might or might not.

Stephan van Hulst wrote:. . . the % operator, not the & operator.

Please tell us why the & operator (=bitwise AND) might be better than the remainder operator (%).

I must apologize. I misremembered the inner workings of HashMap. It indeed uses the & operator internally.

An advantage of & is that it always yield a non-negative number, whereas % may yield negative numbers.

This is the function that HashMap uses, more or less:
bucketIndex(h, c) = (h ^ (h >>> 16)) & (c - 1)
Where h is the hash code of the element, and c is the current capacity of the hash table, a power of two.

The (h ^ (h >>> 16)) part just XORs the most significant bits with the least significant bits, to give the hash code a better distribution. The rest is identical to Carey's implementation.

You can also execute bitwise AND in one clock cycle, whereas remainder may require thirty‑two clock cycles for ints.

You are quite correct. My post that suggested to use the modulus operator instead of the conjunction operator was mistaken on multiple counts.

Stephan wrote:Lists are always ordered, sets might or might not.

I'm confused about what ordered means for Lists.   Does it mean that we can ask Java to tell us what item number 27 is in a list?    I have to go back to the book to read about lists again.  

Thanks,

Kevin

All lists (sometimes called sequences) have an encounter order. You should always be able to access element n of any list, assuming there are enough elements. In some concrete implementations, however, that is not the most efficient way to traverse a list. Most lists default to using insertion order (element inserted first=element found first) but many list implementation allow that order to be changed.
The mathematical abstraction “set” doesn't specify any particular order for its elements. Some computer implementations (e.g. HashSet) have an unpredictable order if you traverse all its elements. Some implementations add extra functionality. For example a TreeSet gives you its elements sorted in terms of some feature of the element, and a LinkedHashSet gives you its elements in order of first insertion.
Most of these datatype implementations will give you the same order of traversal if you do it twice without changing anything else.

I appreciate the information.  

When I first read "concrete implementation"  my thoughts jumped to interfaces and something to do with concrete.  I don't think it means that in your last post.

Thanks,

Kevin

kevin Abel wrote:When I first read "concrete implementation"  my thoughts jumped to interfaces and something to do with concrete.  I don't think it means that in your last post.

In this context "concrete" means the opposite of "abstract".

The List interface expresses the abstract notion of an indexed sequence of elements.

The LinkedList class is a concrete implementation of the abstract notion that List expresses.

What Campbell meant is that in theory, you can iterate over any list simply by accessing each element by its index:
for (var i = 0; i < list.size(); i++) {  var element = list.get(i);  doSomethingWith(element); }
In practice however, this is a bad idea because many concrete implementations of List don't support random access for the get() method. LinkedList is an example of a concrete implementation of List that doesn't support random access times.

For this reason, when iterating over all elements of a list, you should use an iterator instead of the get() method:
for (var element: list) {  doSomethingWith(element); }

kevin Abel wrote:. . . "concrete implementation" . . .  I don't think it means that in your last post. . . .

It means, if you make a wall out of it and bang your head against it, it hurts a lot more than banging your head against an abstract wall.

Stephan,

I'm glad you told me about this.   I'm so used to coding the  top way with BASIC, Clipper and VBA.  I think that I'll remember it.

Campbell,

I got a smile from your line in the last comment.

Kevin

Hello

HashSet:
HashSet is a class in Java that implements the Set interface. It is used to store a collection of unique elements, meaning no duplicate elements are allowed. HashSet does not maintain any order for its elements. It is based on a hash table data structure, which allows for efficient insertion, deletion, and lookup operations.

HashCode:
HashCode is a method defined in the Object class in Java. It returns an integer value that represents the object's memory address or a unique identifier generated by the object's contents. The hashCode() method is used in hash-based data structures like HashSet to determine the index where an element should be stored or retrieved.

In the context of HashSet, each object you add to the HashSet is associated with a hash code. When you add an element to a HashSet, Java calculates the hash code for that element using the hashCode() method. This hash code is then used to determine where the element should be stored in the underlying hash table. If two objects have the same hash code (a collision), the HashSet uses additional mechanisms (like equality checks) to handle and store them properly.

HashSet is a collection that stores unique elements using a hash table, and the hash code of an object is used to determine its storage and retrieval within the HashSet.

If you're looking for more in-depth information, I recommend reading the Java documentation on HashSet and the concepts of hashing and hash codes.

GB: welcome to the Ranch

greg bowers wrote:HashCode:
... It returns an integer value that represents the object's memory address or a unique identifier generated by the object's contents.

I don't think that's an accurate characterization. The API documentation for Object.hashCode() says this:

This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the Java™ programming language.)

So, yes, the value is typically based on an object's internal address but since it's an implementation detail, you can't assume that is always the case. Case in point: the hashCode() is for an Integer (the wrapper class) object is the integer's value itself, not the object's internal address.

Also, there is always the chance of hashCode collisions given a large enough set of possible objects. This means some objects may end up having the same hashCode even though their internal addresses are different. Again, hash codes are not unique identifiers and you shouldn't think of them as such.

Junilu Lacar wrote:. . . The API documentation for Object.hashCode() says this . . .

Only in old versions. The latest version for JDK20 says something different. If you go back to Java11, it does mention memory:-

(The hashCode may or may not be implemented as some function of an object's memory address at some point in time.)

Even Java7 hedges its bets:-

(This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)

The point still holds: hashCode() is not necessarily a unique identifier for an object (although implementers are encouraged to make them unique as practically possible)  nor is it necessarily based on the object's internal address even though it could be and typically is. The language leaves room for implementers to find other ways of calculating a hash code.

I was reading the Object equality part of the Head First Book.  It's my second pass through the book.  

I keep understanding the two types of object equality better, but I still have a lot to learn.

Thanks all,

Kevin