Java Improvement (24) -----HashSet

Original text from: http://www.php.cn/

## In the previous blog post (java Improvement Chapter (23) -----HashMap) explains the implementation process of HashMap in detail. For HashSet, it is implemented based on HashMap, and the bottom layer uses HashMap to save elements. So if you are familiar with HashMap, then HashSet is so easy!!

1. Definition

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

HashSet inherits the AbstractSet class and implements the Set, Cloneable, and Serializable interfaces. Among them, AbstractSet provides the backbone implementation of the Set interface, thus minimizing the work required to implement this interface. The Set interface is a Collection that does not contain duplicate elements. It maintains its own internal ordering, so random access does not make sense.

Basic attributes

//基于HashMap实现，底层使用HashMap保存所有元素
private transient HashMap<E,Object> map;

 //定义一个Object对象作为HashMap的value
 private static final Object PRESENT = new Object();

## Constructor

/**
         * 默认构造函数
         * 初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。
         */
        public HashSet() {
            map = new HashMap<>();
        }
        
        /**
         * 构造一个包含指定 collection 中的元素的新 set。
         */
        public HashSet(Collection<? extends E> c) {
            map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
            addAll(c);
        }
        
        /**
         * 构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和指定的加载因子
         */
        public HashSet(int initialCapacity, float loadFactor) {
            map = new HashMap<>(initialCapacity, loadFactor);
        }
           
        /**
         * 构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和默认的加载因子（0.75）。
         */
        public HashSet(int initialCapacity) {
           map = new HashMap<>(initialCapacity);
        }
           
        /**
         * 在API中我没有看到这个构造函数，今天看源码才发现（原来访问权限为包权限，不对外公开的）
         * 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。
         * dummy 为标识 该构造函数主要作用是对LinkedHashSet起到一个支持作用
         */
        HashSet(int initialCapacity, float loadFactor, boolean dummy) {
           map = new LinkedHashMap<>(initialCapacity, loadFactor);
        }

It can be seen from the constructor that all the constructors of HashSet are It constructs a new HashMap. The last constructor is not public for package access and only takes effect when using LinkedHashSet.

2. Method

               

Since HashSet is based on HashMap, then for HashSet, the implementation process of its method is very simple.

public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

The iterator() method returns an iterator that iterates over the elements in this set. The order in which the elements are returned is not specific. The underlying call to HashMap's keySet returns all keys. This reflects that all elements in the HashSet are stored in the HashMap's key, and the value is the PRESENT object used, which is static final.

public int size() {
        return map.size();
    }

          size() returns the number of elements in this set (the capacity of the set). The bottom layer calls the size method of HashMap and returns the size of the HashMap container.

public boolean isEmpty() {
        return map.isEmpty();
    }

isEmpty(), determines whether the HashSet() collection is empty, and returns if it is empty true, otherwise false

is returned.

public boolean contains(Object o) {
        return map.containsKey(o);
    }

#contains(), determines whether an element exists in HashSet(), returns true if it exists , otherwise return false. To be more precise, this relationship should be satisfied to return true: (o==null ? e==null : o.equals(e)). The bottom layer calls containsKey to determine whether the key value of HashMap is empty.

public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

   

         

add() If this set does not yet contain the specified element, add the specified element. If this Set does not contain e2 that satisfies (e==null ? e2==null : e.equals(e2)), then e2 is added to the Set, otherwise it is not added and false is returned. Since the bottom layer uses the put method of HashMap to construct key = e, value = PRESENT into a key-value pair, when e exists in the key of HashMap, the value will overwrite the original value, but the key remains unchanged, so If an existing e element is added to the HashSet, the newly added element will not be saved in the HashMap, so this satisfies the feature that the elements in the HashSet will not be repeated.

public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

               

removeIf the specified element exists in this set, remove it. The bottom layer uses the remove method of HashMap to delete the specified Entry.

public void clear() {
        map.clear();
    }

clear从此 set 中移除所有元素。底层调用HashMap的clear方法清除所有的Entry。

public Object clone() {
        try {
            HashSet<E> newSet = (HashSet<E>) super.clone();
            newSet.map = (HashMap<E, Object>) map.clone();
            return newSet;
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
    }

          clone返回此 HashSet 实例的浅表副本：并没有复制这些元素本身。

          后记：

          由于HashSet底层使用了HashMap实现，使其的实现过程变得非常简单，如果你对HashMap比较了解，那么HashSet简直是小菜一碟。有两个方法对HashMap和HashSet而言是非常重要的，下篇将详细讲解hashcode和equals。

---------------------------------------------------------------------------------------------------------

以上就是java提高篇（二四）-----HashSet的内容，更多相关内容请关注PHP中文网（www.php.cn）！