Java Set/HashSet的内部工作

我们知道，一个集合是一个 定义明确的 不同对象的集合。一个集合的每个成员都被称为该集合的一个元素。因此，换句话说，我们可以说一个 集合永远不会包含重复的元素 但是在java中Set接口实现的类如HashSet、LinkedHashSet、TreeSet等是如何实现这种唯一性的。在这篇文章中，我们将讨论这个唯一性背后隐藏的真相。

HashSet在Java内部是如何工作的？

Java中SetHashSet的内部工作
我们将通过一个例子来了解这个问题。让我们看看下面这个程序的输出，它试图在一个HashSet中添加重复的元素。

// Java program to demonstrate
// internal working of HashSet
  
import java.util.HashSet;
  
class Test
{    
    public static void main(String args[]) 
    {
        // creating a HashSet
        HashSet hs = new HashSet();
          
        // adding elements to hashset
        // using add() method
        boolean b1 = hs.add("Geeks");
        boolean b2 = hs.add("GeeksforGeeks");
          
        // adding duplicate element
        boolean b3 = hs.add("Geeks");
          
        // printing b1, b2, b3
        System.out.println("b1 = "+b1);
        System.out.println("b2 = "+b2);
        System.out.println("b3 = "+b3);
          
        // printing all elements of hashset
        System.out.println(hs);
              
    }
}

输出:

b1 = true
b2 = true
b3 = false
[GeeksforGeeks, Geeks]

现在从输出结果中可以看出，当我们试图用add()方法将一个重复的元素添加到一个集合中时，它返回false，并且元素不会被添加到hashset中，因为它已经存在。现在问题来了，add()方法如何检查集合中是否已经包含了指定的元素。如果我们仔细看一下HashSet类中的add()方法和默认构造函数，就会更清楚。

// predefined HashSet class
public class HashSet
{
    // A HashMap object 
    private transient HashMap map;

    // A Dummy value(PRESENT) to associate with an Object in the Map
    private static final Object PRESENT = new Object();

    // default constructor of HashSet class
    // It creates a HashMap by calling 
    // default constructor of HashMap class
    public HashSet() {
        map = new HashMap<>();
    }

    // add method 
    // it calls put() method on map object
    // and then compares it's return value with null
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

    // Other methods in Hash Set
}

现在你可以看到，每当我们创建一个HashSet时，它都会在内部创建一个HashMap，如果我们使用add()方法在这个HashSet中插入一个元素，它实际上是在内部创建的HashMap对象上调用put()方法，你所指定的元素是它的键，名为 “PRESENT “的恒定对象是它的值。所以我们可以说 Set是通过HashMap在内部实现唯一性的 现在，整个故事围绕着HashMap和put()方法的内部运作展开。

我们知道在HashMap中每个键都是唯一的，当我们调用put(Key, Value)方法时，它会返回与键相关的前一个值，如果没有键的映射，则返回空。所以在add()方法中，我们检查map.put(key, value)方法的返回值是否为空。

如果map.put(key, value)返回null，那么语句 “map.put(e, PRESENT) == null “将返回true，元素被添加到HashSet（内部为HashMap）。
如果map.put(key, value)返回键的旧值，那么语句 “map.put(e, PRESENT) == null “将返回false，元素不会被添加到HashSet（内部HashMap）。

由于LinkedHashSet扩展了HashSet，所以它在内部使用super()调用HashSet的构造函数。同样的，创建TreeSet类的对象也会在内部创建Navigable Map的对象作为支持Map。