In Java, HashSet is a class that implements the Set interface, which represents a collection of unique elements. HashSet uses a hash table to store elements and provides constant-time performance for the basic operations (add, remove, contains, and size), assuming a good hash function is used. It does not maintain the order of elements in the set.
Here's a brief explanation of the its constructors, and some of its methods:
1. HashSet(): This creates an empty HashSet with the default initial capacity (16) and default load factor (0.75).
2. HashSet(int initialCapacity): This creates an empty HashSet with the specified initial capacity and the default load factor (0.75).
3. HashSet(int initialCapacity, float loadFactor): This creates an empty HashSet with the specified initial capacity and load factor.
4. HashSet(Collection c): This creates a HashSet containing the elements of the specified collection.
1. add(E e): This adds the specified element to the HashSet if it is not already present.
2. remove(Object o): This removes the specified element from the HashSet if it is present.
3. contains(Object o): This returns true if the HashSet contains the specified element.
4. size(): This returns the number of elements in the HashSet.
5. clear(): This removes all elements from the HashSet.
6. isEmpty(): This returns true if the HashSet contains no elements.
7. iterator(): This returns an iterator over the elements in the HashSet.
8. toArray(): This returns an array containing all elements in the HashSet.
9. equals(Object o): This returns true if the specified object is also a HashSet and contains the same elements.
10. hashCode(): This returns the hash code value for the HashSet.
Note : HashSet does not allow duplicate elements, so if you try to add an element that is already present in the set, the add() method will return false and the element will not be added. HashSet also allows null elements, but only one null element can be added to the set. Finally, because HashSet uses a hash table, the elements are not guaranteed to be stored in the order they were added.
HashSet is implemented using a hash table, which is a data structure that allows for fast access, insertion, and deletion of elements by using a hash function to map elements to an index in an array. Here's how HashSet is implemented internally:
1. HashSet uses a hash table internally to store the elements. The hash table is an array of buckets, where each bucket is a linked list of elements that have the same hash code.
2. When an element is added to the HashSet using the add() method, its hash code is computed using the hashCode() method of the object. The hash code is then used to determine the index of the bucket in which the element should be stored.
3. If the bucket at the computed index is empty, the element is added to the bucket. If the bucket already contains elements, a linear search is performed on the linked list to see if the element is already present. If the element is not found, it is added to the end of the linked list.
4. When an element is removed from the HashSet using the remove() method, its hash code is computed, and the index of the bucket in which it should be located is determined. The linked list at that bucket is then searched for the element to be removed. If the element is found, it is removed from the linked list. If the linked list becomes empty after the removal, the bucket is also removed.
5. The size() method returns the number of elements in the HashSet, which is computed by adding up the size of each bucket in the hash table.
6. The contains() method checks whether an element is present in the HashSet by computing its hash code, determining the index of the bucket in which it should be located, and then performing a linear search on the linked list at that bucket.
7. The hash table is resized dynamically as the number of elements in the HashSet grows. When the number of elements exceeds the capacity of the hash table multiplied by the load factor, the hash table is resized to twice its current size, and all elements are rehashed and redistributed to new buckets.
Overall, HashSet's internal implementation using a hash table allows for fast access, insertion, and deletion of elements, making it a very efficient data structure for storing and manipulating sets of unique elements.
Here's an example of using a HashSet in Java:
import java.util.HashSet;
public class HashSetExample {
public static void main(String[] args) {
// Create a new HashSet
HashSet<String> mySet = new HashSet<>();
// Add some elements to the HashSet
mySet.add("apple");
mySet.add("banana");
mySet.add("orange");
mySet.add("apple"); // This element will not be added since it is a duplicate
// Print the HashSet
System.out.println("My HashSet contains: " + mySet);
// Check if the HashSet contains an element
if (mySet.contains("banana")) {
System.out.println("My HashSet contains the element 'banana'");
}
// Remove an element from the HashSet
mySet.remove("orange");
// Print the HashSet again
System.out.println("My HashSet now contains: " + mySet);
}
}
In this example, we first create a new HashSet called mySet. We then add some elements to it using the add() method. Note that we add the element "apple" twice, but only one copy is stored since duplicates are not allowed in a HashSet.
We then print the contents of the HashSet using the println() method. Note that the order of the elements in the HashSet is not guaranteed.
Next, we check if the HashSet contains the element "banana" using the contains() method. If it does, we print a message saying so.
We then remove the element "orange" from the HashSet using the remove() method.
Finally, we print the contents of the HashSet again to show that the element "orange" has been removed.