深入理解Java中Set/HashSet的内部工作原理

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

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

!How Set/HashSet works internally in Java

让我们通过一个例子来理解这一点。请看下面这段试图向HashSet中添加重复元素的程序输出结果。

Java


CODEBLOCK_e255bf92


Output:

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) 方法时，它会返回与该键关联的旧值，如果没有该键的映射，则返回 null。因此，在 add() 方法中，我们检查map.put(key, value)方法的返回值是否为 null。

• 如果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对象作为支撑映射。

相关文章： HashMap在Java内部是如何工作的。