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:
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:
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.
|
1 2 3 4 5 6 7 8 |
Set<Product> Products = new HashSet<Product>(); //Sample 02: First Let us create 25 products Products.clear(); for (int i = 1; i < 26; i++) { Products.add(new Product(i, ("Product-" + i))); } int size = Products.size(); System.out.println("The size now is: " + size); |
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.
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:
|
1 2 3 4 5 6 7 |
//Sample 03: Let us increase the size to 1000 Products.clear(); for (int i = 1; i < 1001; i++) { Products.add(new Product(i, ("Product-" + i))); } size = Products.size(); System.out.println("The size now is: " + size); |
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.
|
1 2 3 4 5 |
//3.1: Check for contains Product p1 = new Product(231, "Product-231"); boolean ret = Products.contains(p1); Product p2 = new Product(3661, "Product-3661"); ret = Products.contains(p2); |
The eclipse debugger now shows the buckets since the number of products in the collection is 1000. Below is the picture for reference:
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:
|
1 2 3 4 5 6 7 8 9 10 11 |
//Sample 04: Let us further increase the Size to 100000 //4.1: Further Increase the products Products.clear(); for (int i = 1; i < 100001; i++) { Products.add(new Product(i, ("Product-" + i))); } size = Products.size(); System.out.println("The size now is: " + size); //4.2: Check for Contains Product p3 = new Product(12157, "Product-12157"); ret = Products.contains(p3); |
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:
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
import java.util.Objects; public class Product { private int ProdId; private String ProdName; // 1.1: Ctor Product(int id, String name) { ProdId = id; ProdName = name; } // 1.2: toString Override @Override public String toString() { return ProdId + ":" + ProdName ; } //1.3 Getter and Setter public int getProdId() { return ProdId; } public void setProdId(int prodId) { ProdId = prodId; } public String getProdName() { return ProdName; } public void setProdName(String prodName) { ProdName = prodName; } //Sample 02: Modify HashCode and Equals to print hash code @Override public int hashCode() { int x = Objects.hashCode(ProdId); System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"); System.out.println("Collection Called our hashCode"); System.out.println("Hash code for " + this.ProdName + " is : " + x); System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"); return x; } @Override public boolean equals(Object obj) { System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"); System.out.println("Collection Called our equals method"); System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"); Product prod = (Product) obj; return (this.ProdId == prod.getProdId()); } } |
4.2 HashSetTest Main Program
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
//Sample01: Set & HashSet part of Util Package import java.util.HashSet; import java.util.Set; public class HashSetTest { public static void main(String[] args) { Set<Product> Products = new HashSet<Product>(); //Sample 01: First Let us create 25 products Products.clear(); for (int i = 1; i < 26; i++) { Products.add(new Product(i, ("Product-" + i))); } int size = Products.size(); System.out.println("The size now is: " + size); //Sample 02: Let us increase the size to 1000 Products.clear(); for (int i = 1; i < 1001; i++) { Products.add(new Product(i, ("Product-" + i))); } size = Products.size(); System.out.println("The size now is: " + size); //2.1: Check for contains Product p1 = new Product(231, "Product-231"); boolean ret = Products.contains(p1); Product p2 = new Product(3661, "Product-3661"); ret = Products.contains(p2); //Sample 03: Let us further increase the Size to 100000 Products.clear(); for (int i = 1; i < 100001; i++) { Products.add(new Product(i, ("Product-" + i))); } size = Products.size(); System.out.println("The size now is: " + size); //2.2: Check for Contains Product p3 = new Product(12157, "Product-12157"); ret = Products.contains(p3); } } |
5. Watch this Example as YouTube Video
Categories: Java
Tags: Buckets, hashCode, HashSet
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.