HashSet Buckets And HashCode In Java

Items in Separate Buckets

1. HashSet Buckets Overview

In the past Java HashSet example, we learnt about the Java HashSet and its Set implementation and how it keeps the uniqueness. Now, in this example, we will learn about the Buckets and how it aids quicker retrieval and search. These buckets improve the performance of search action and this example will research how these bucketing concepts work with HashSet Class and hashCode override of its stored object.

2. Need for Buckets

Let us say we have a single big bucket with different colored discs in it. Also note that each disc is having numbers in it. This bucket can be seen as follows:

All items in Single Bucket
All items in Single Bucket

In the above picture, we can see how each coloured disc is mixed. We will also assume there are hundreds of discs in each color and they have unique numbers. Now, if somebody asks you to check Green Disc with number 67 exists in the basket, you will check it till you visit all the green-coloured discs. During your search, you may separate the green-coloured disc for a quick surf and may ask for a new basket to dump all the green disc in it. This is how bucketing comes into the picture.

Now, let us say we arrange the discs in separate baskets and each basket is holding a unique colored disc. This is shown in the below picture:

Items in Separate Buckets
Items in Separate Buckets

This time our search for green disc numbered 67 becomes easy as we ignore the other baskets. Because we directly land into green baskets and start searching the disc with number 67. You can see how we eliminated other baskets. This is how Hashing works in Java Collection framework. Now let us create an example using HashSet class and see how these buckets are created. Here, we use eclipse to visualize the bucketing concepts.

3. Visualizing the HashSet Buckets

3.1 HashSet with 25 Products

First, we will add 25 Product instances to the HashSet class. In the below code, we use a for loop to add these 25 objects to the HashSet Collection.

Using Eclipse debugger, when we drill down the Products reference, we see 25 slots. The below picture shows this, and we can’t see any buckets formed for now. This is because the number of items is less and Java’s HashSet decides not to create any buckets for now.

Java hashSet with 25 Items - No Buckets
Java hashSet with 25 Items – No Buckets

3.2 HashSet with 1000 Products

Since we cannot visualize the buckets using 25 Products; we are now increasing the number of products to 1000. The code same like the previous section. But this time we add 1000 products to the Products HashSet collection. Below is the code:

We also use the contains method to check how it invokes the hashCode override on the Product instance. Yon can refer the code for the Product class in the example here: Set and HashSet Example.

The eclipse debugger now shows the buckets since the number of products in the collection is 1000. Below is the picture for reference:

Java hashSet with 1000 Items - Spread on 10 Buckets
Java hashSet with 1000 Items – Spread on 10 Buckets

In the picture, we can notice 10 Buckets created and each one will hold 100 products in it. The contains method of the HastSet will make a call to the hashCode override on the Product instance to get the hash code of the passed-in parameter. Let us say, we pass Product 231 to the contains method. The method first generates the hashSet code and then decides which bucket to search. For product 231, HashSet directly goes to third bucket and performs a search for product id 231. This improves the performance as instead of scanning 1000 product, now it scans only 100 products on a specific bucket.

3.3 HashSet with 1 Lakh Products (Bucket of Buckets)

Now look at the code snippet below:

This time we insert 100 thousand products to our Products HashSet collection. When we drill-down to the Products using eclipse debugger, it shows how Java HashSet arranges the buckets. Below is the picture:

Java hashSet with 1Lakh Items - Bucket of Buckets
Java hashSet with 1Lakh Items – Bucket of Buckets

The picture shows how the Bucket of 100 products is bundled and placed in a master bucket. You can also visualize how quick the search will be. The hashing techniques in Java show its actual performance difference when your collection grows to a big extend. The search performance will be noticeable when we compared with plain ArrayList.

4. Complete Code Example

4.1 Product Class

4.2 HashSetTest Main Program

5. Watch this Example as YouTube Video

Do you like this Example? Please comment about it for others!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.