Java Set Interface
The Java Set interface is a data structure that organizes elements in a way similar to an array, without allowing duplicates. If an attempt is made to add an element that already exists in the Set, it will not be stored. This interface is commonly employed to mimic the characteristics of a mathematical set.
Java HashSet class
The Java HashSet class is utilized to manage a collection of elements, ensuring uniqueness without a specific order. It creates a data structure based on a hash table to store these elements effectively. This class inherits characteristics from the AbstractSet class and implements the Set interface. The mechanism employed to store and access elements is known as hashing, and internally, HashSet relies on HashMap in Java.
If we aim to establish a HashSet for storing a collection of Strings, we can initialize the object as follows:
HashSet<String> hs=new HashSet<>();
The placeholder <String> is used as a generic type parameter that signifies the type of element being stored in the HashSet data structure.
The HashSet class is an implementation of the Set interface, ensuring that all elements within it are unique. This uniqueness is maintained by storing elements as keys with equal values. Unlike other data structures, HashSet does not provide a direct method to access objects stored within it. Instead, objects can be retrieved using an Iterator. Internally, when a HashSet object is created, it initializes an instance of HashMap with a default initial capacity of 16.
The HashSet class provides a constructor, HashSet(int capacity), which specifies the initial capacity of the HashSet to determine how many elements it can store. The capacity of the HashSet can expand dynamically as more elements are added for storage.
A different constructor available for HashSet is HashSet(int capacity, float loadfactor). In this scenario, the loadfactor determines the threshold at which the HashSet's capacity will be expanded internally. For instance, if the capacity is 101 and the loadfactor is 0.5, the product is 101 * 0.5 = 50.5. This signifies that once the 50th element is added to the HashSet, its capacity will be automatically increased to accommodate more elements. By default, the initial capacity of a HashSet is set to 16, while the default load factor is 0.75.
HashSet Implementation
Below, we will be coding the add function that inserts an element into a HashSet.
Example
import java.util.*;
public class HashsetDemo
{
public static void main(String[] args)
{
HashSet<String> hs= new HashSet<String>();
hs.add(?India?);
hs.add(?America?);
hs.add(?Russia?);
System.out.println(?Set is ?+hs); //view HashSet
Iterator it=hs.iterator(); //add an iterator to hs
System.out.println("Elements using iterator:");
while(it.hasNext()) //display elements by using iterator
{
String s=(String)it.next();
System.out.println(s);
}
}
}
Output:
Set is [America, India, Russia]
Elements using iterator:
America
India
Russia
In this instance, we are attempting to insert duplicate values.
Example
import java.util.*;
public class Main
{
public static void main(String[] args)
{
HashSet<String> hs= new HashSet<String>();
hs.add("India");
hs.add("America");
hs.add("Russia");
hs.add("China");
hs.add("India"); //duplicate value
hs.add("Russia"); //duplicate value
System.out.println("Set is "+hs); //view HashSet
Iterator it=hs.iterator(); //add an iterator to hs
System.out.println("Elements using iterator:");
while(it.hasNext()) //display elements by using iterator
{
String s=(String)it.next();
System.out.println(s);
}
}
}
Output:
Set is [China, America, India, Russia]
Elements using iterator:
China
America
India
Russia
In the previously shown example, we included certain redundant values. It is noticeable that redundant values are not retained within the HashSet data structure. If duplicate elements are provided to the add function of the Set instance, it will internally yield a false response.
An inquiry emerges regarding how it results in false. Upon examining the add function within the HashSet implementation in Java APIs (found in rt.jar), the code snippet below is uncovered:
public class HashSet<E> extends AbstractSet<E>
{
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public HashSet()
{
map = new HashMap<>();
}
public boolean add(E e)
{
return map.put(e, PRESENT)==null;
}
}
Within the provided code snippet, the invocation of the add(object) method is internally routed to put(key, value). Here, the key represents the object that has been supplied, while the value corresponds to a distinct object known as PRESENT, which is a fixed entity within the java.util.HashSet framework.
Uniqueness in the Set is attained using an internal HashMap structure. Instantiating a HashSet object results in the creation of a HashMap object. The HashMap ensures uniqueness of each key. When invoking the add(E e) method, an argument is passed where a value needs to be assigned to the key. In this scenario, the value is associated with a Dummy value, represented by (new Object), which is referenced by the Object reference PRESENT.
Upon adding an element, such as "India", into a HashSet using the add method in Java, the process internally involves placing the element, represented by the key "India", into a HashMap which is created during the initialization of the HashSet object. Additionally, a dummy value, typically an instance of the Object class, is associated with this key within the HashMap.
put method of HashMap
put(Key k, Value v)
{
//some code
}
Key information regarding the put(key, value) method includes:
- In case the key is unique and successfully added to the map, the method will return null.
- If the key is a duplicate, the method will return the previous value associated with the key.
In Java, when the add method is called in a HashSet, the system internally verifies the outcome of the map.put(key, value) method by comparing it against null.
public boolean add(E e)
{
return map.put(e, PRESENT==null);
}
- If the method map.put(key, value) returns null, then the method map.put(e, PRESENT)==null will return true internally, and the element added to the HashSet.
- If the method map.put(key, value) returns the old value of the key, then the method map.put(e, PRESENT)==null will return false internally, and the element will not add to the HashSet.
Retrieving Object from the HashSet
The iterator method is employed to fetch objects from a HashSet in Java. This method belongs to the java.util.HashSet class and provides an iterator for the backup Map retrieved by the map.keySet.iterator method.
public Iterator<E> iterator()
{
return map.keySet().iterator();
}