1 the concept

HashSet implements the Set interface, supported by a hash table (which is actually a HashMap instance). It holds non-repeating elements and does not guarantee the iteration order of the set. This class allows the use of null elements. As for HashSet, it is implemented based on HashMap. HashSet uses HashMap to store all elements at the bottom level, so the implementation of HashSet is relatively simple. Operations related to HashSet are basically completed by directly calling related methods of underlying HashMap.

2 Source code interpretation

Let’s look at the constructor source:

    public HashSet(a) {
        map = new HashMap<>();
    }
Copy the code

As you can see, the underlying HashSet is actually a HashMap. Add () = add();

    public boolean add(E e) {
        // Return true if successfully added, false otherwise
        return map.put(e, PRESENT)==null;
    }
 
    
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false.true);
    }
    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
                        break; p = e; }}if(e ! =null) { // existing mapping for key
                V oldValue = e.value;
                if(! onlyIfAbsent || oldValue ==null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
Copy the code

We see that the put() method of the HashMap is also called, which treats the added element as the key of the HashMap, returning true if it was added successfully and false otherwise.

3 Application Examples

Here I want to illustrate the use of HashSet with an example application. For a string, design an efficient algorithm to find the character repeated for the first time. Given A string (not necessarily all letters)A and its length n. Return the first recurring character. Ensure that there are duplicate characters in the string. The length of the string is less than or equal to 500 characters. Test example: SeUME666,8

Returns: e

The implementation code is also simple:

/ * * *@author Carson Chu, [email protected]
 * @date2020/4/13 when *@description* /
public class Main {
    public static void main(String[] args) {
        System.out.println(findChar("seume666".8));
    }

    public static char findChar(String input, int length) {

        char[] a = input.toCharArray();
        HashSet hashSet = new HashSet<>();
        for (int i = 0; i < length; i++) {
            if(! hashSet.add(a[i])) {// Add failed, indicating that it already exists in set
                returna[i]; }}return 0; }}Copy the code