Introduction to the graphic code of Set in Java collection

Set is also inherited from Collection. Set is also a type of collection. At the same time, Set does not allow duplicate elements to exist. The implementation classes of Set are all implemented based on Map, where HashSet is implemented through HashMap, and TreeSet is implemented through TreeMap.

Set architecture:

##(1) Set is the

interface# inherited from Collection ##, it is a collection that does not allow duplicate elements. (2) AbstractSet is an

abstract class

, which inherits AbstractCollection. AbstractCollection implements most of the functions in Set, providing convenience for Set implementation classes. . (3) HashSet and TreeSet are two implementation classes of Set. HashSet relies on HashMap, and is actually implemented through HashMap. The elements in HashSet are unordered. TreeSet depends on TreeMap, and is actually implemented through TreeMap. The elements in TreeSet are ordered.

Java8-based AbstractCollection source code:

public abstract class AbstractCollection<E> implements Collection<E> {
    protected AbstractCollection() {//构造函数
    }
    public abstract Iterator<E> iterator();//迭代器

    public abstract int size();//集合大小

    public boolean isEmpty() {//集合是否为空
        return size() == 0;
    }
    public boolean contains(Object o) {//判断是否包含某个元素，通过迭代遍历的方式
        Iterator<E> it = iterator();
        if (o==null) {
            while (it.hasNext())
                if (it.next()==null)
                    return true;
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return true;
        }
        return false;
    }
    public Object[] toArray() {//生成数组
        // Estimate size of array; be prepared to see more or fewer elements
        Object[] r = new Object[size()];
        Iterator<E> it = iterator();
        for (int i = 0; i < r.length; i++) {
            if (! it.hasNext()) // fewer elements than expected
                return Arrays.copyOf(r, i);
            r[i] = it.next();
        }
        return it.hasNext() ? finishToArray(r, it) : r;
    }
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {//泛型方式生成数组
        // Estimate size of array; be prepared to see more or fewer elements
        int size = size();
        T[] r = a.length >= size ? a :
                (T[])java.lang.reflect.Array
                        .newInstance(a.getClass().getComponentType(), size);
        Iterator<E> it = iterator();
        for (int i = 0; i < r.length; i++) {
            if (! it.hasNext()) { // fewer elements than expected
                if (a == r) {
                    r[i] = null; // null-terminate
                } else if (a.length < i) {
                    return Arrays.copyOf(r, i);
                } else {
                    System.arraycopy(r, 0, a, 0, i);
                    if (a.length > i) {
                        a[i] = null;
                    }
                }
                return a;
            }
            r[i] = (T)it.next();
        }
        // more elements than expected
        return it.hasNext() ? finishToArray(r, it) : r;
    }
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    @SuppressWarnings("unchecked")
    private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
        int i = r.length;
        while (it.hasNext()) {
            int cap = r.length;
            if (i == cap) {
                int newCap = cap + (cap >> 1) + 1;
                // overflow-conscious code
                if (newCap - MAX_ARRAY_SIZE > 0)
                    newCap = hugeCapacity(cap + 1);
                r = Arrays.copyOf(r, newCap);
            }
            r[i++] = (T)it.next();
        }
        // trim if overallocated
        return (i == r.length) ? r : Arrays.copyOf(r, i);
    }
    //对输入的minCapacity判断最大容量
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError
                    ("Required array size too large");
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }
    //添加对象
    public boolean add(E e) {
        throw new UnsupportedOperationException();
    }
    //通过迭代查找，删除对象
    public boolean remove(Object o) {
        Iterator<E> it = iterator();
        if (o==null) {
            while (it.hasNext()) {
                if (it.next()==null) {
                    it.remove();
                    return true;
                }
            }
        } else {
            while (it.hasNext()) {
                if (o.equals(it.next())) {
                    it.remove();
                    return true;
                }
            }
        }
        return false;
    }
    //判断集合C中的元素是否都存在
    public boolean containsAll(Collection<?> c) {
        for (Object e : c)
            if (!contains(e))
                return false;
        return true;
    }
    //将集合c中的元素添加
    public boolean addAll(Collection<? extends E> c) {
        boolean modified = false;
        for (E e : c)
            if (add(e))
                modified = true;
        return modified;
    }
    //删除掉集合c中在此集合中的元素
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        boolean modified = false;
        Iterator<?> it = iterator();
        while (it.hasNext()) {
            if (c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }
    //删除掉此集合中在c中不存在的对象
    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        boolean modified = false;
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            if (!c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }
    //清空集合
    public void clear() {
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            it.next();
            it.remove();
        }
    }
    //通过StringBuilder生成string
    public String toString() {
        Iterator<E> it = iterator();
        if (! it.hasNext())
            return "[]";

        StringBuilder sb = new StringBuilder();
        sb.append(&#39;[&#39;);
        for (;;) {
            E e = it.next();
            sb.append(e == this ? "(this Collection)" : e);
            if (! it.hasNext())
                return sb.append(&#39;]&#39;).toString();
            sb.append(&#39;,&#39;).append(&#39; &#39;);
        }
    }

}

Java8-based AbstractSet source code:

public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {

    protected AbstractSet() {
    }
    public boolean equals(Object o) {//判断两个集合是否相同
        if (o == this)
            return true;

        if (!(o instanceof Set))
            return false;
        Collection<?> c = (Collection<?>) o;
        if (c.size() != size())
            return false;
        try {
            return containsAll(c);
        } catch (ClassCastException unused)   {
            return false;
        } catch (NullPointerException unused) {
            return false;
        }
    }
    //计算hashCode
    public int hashCode() {
        int h = 0;
        Iterator<E> i = iterator();
        while (i.hasNext()) {
            E obj = i.next();
            if (obj != null)
                h += obj.hashCode();
        }
        return h;
    }
    //删除此集合中与c中相同的对象
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        boolean modified = false;

        if (size() > c.size()) {
            for (Iterator<?> i = c.iterator(); i.hasNext(); )
                modified |= remove(i.next());
        } else {
            for (Iterator<?> i = iterator(); i.hasNext(); ) {
                if (c.contains(i.next())) {
                    i.remove();
                    modified = true;
                }
            }
        }
        return modified;
    }

}

SortSet source code based on Java8:

SortedSet<> Set<> {
    Comparator<? > ()SortedSet<> (fromElementtoElement)SortedSet<> (toElement)SortedSet<> (fromElement)()()Spliterator<> () {
Spliterators.IteratorSpliterator<>(
Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED) {
Comparator<? > () {
SortedSet..comparator()}
        }}
}

NavigableSet source code based on Java8:

NavigableSet<> SortedSet<> {
(e)(e)(e)(e)()()Iterator<> ()NavigableSet<> ()Iterator<> ()NavigableSet<> (fromElementfromInclusivetoElementtoInclusive)NavigableSet<> (toElementinclusive)NavigableSet<> (fromElementinclusive)SortedSet<> (fromElementtoElement)SortedSet<> (toElement)SortedSet<> (fromElement)}

Set source code based on Java8 :

public interface Set<E> extends Collection<E> {
int size(); //大小
boolean isEmpty();//是否为空
boolean contains(Object o); //是否包含某个对象
Iterator<E> iterator(); //生成迭代器
Object[] toArray(); //返回Object数组
<T> T[] toArray(T[] a); //返回泛型数组
boolean add(E e); //向set中添加元素
boolean remove(Object o); //从set中删除某个元素
boolean containsAll(Collection<?> c); //某个Collection是否都包含在此lset中
boolean addAll(Collection<? extends E> c); //将某个Collection追加到此set中
boolean retainAll(Collection<?> c); //删除不存在于Collection中的set中的元素
boolean removeAll(Collection<?> c); //删除包含在此Collection中的元素
void clear(); //清空set
boolean equals(Object o);//判断两个set是否相同
int hashCode(); //计算set的hashCode
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.DISTINCT);
}
}

The above is the detailed content of Introduction to the graphic code of Set in Java collection. For more information, please follow other related articles on the PHP Chinese website!