Set也是继承自Collection,Set也是集合的一种,同时Set不允许重复的元素存在。Set的实现类都是基于Map来实现的,其中HashSet是通过HashMap来实现的,TreeSet是通过TreeMap实现的。
Set架构:
(1)Set是继承于Collection的接口,它是一个不允许重复元素的集合。
(2)AbstractSet是一个抽象类,继承了AbstractCollection,AbstractCollection实现了Set中的绝大部分函数,为Set的实现类提供了便利。
(3)HashSet和TreeSet是Set的两个实现类。HashSet依赖于HashMap,实际上是通过HashMap来实现的,HashSet中的元素是无序的。TreeSet依赖于TreeMap,实际上是通过TreeMap实现的,TreeSet中的元素是有序的。
基于Java8的AbstractCollection源码:
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('['); for (;;) { E e = it.next(); sb.append(e == this ? "(this Collection)" : e); if (! it.hasNext()) return sb.append(']').toString(); sb.append(',').append(' '); } } }
基于Java8的AbstractSet源代码:
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; } }
基于Java8的SortSet源码:
public interface SortedSet<E> extends Set<E> {
Comparator<? super E> comparator();
SortedSet<E> subSet(E fromElement, E toElement);
SortedSet<E> headSet(E toElement);
SortedSet<E> tailSet(E fromElement);
E first();
E last();
@Override
default Spliterator<E> spliterator() {
return new Spliterators.IteratorSpliterator<E>(
this, Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED) {
@Override
public Comparator<? super E> getComparator() {
return SortedSet.this.comparator();
}
};
}
}
基于Java8的NavigableSet源码:
public interface NavigableSet<E> extends SortedSet<E> {
E lower(E e);
E floor(E e);
E ceiling(E e);
E higher(E e);
E pollFirst();
E pollLast();
Iterator<E> iterator();
NavigableSet<E> descendingSet();
Iterator<E> descendingIterator();
NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive);
NavigableSet<E> headSet(E toElement, boolean inclusive);
NavigableSet<E> tailSet(E fromElement, boolean inclusive);
SortedSet<E> subSet(E fromElement, E toElement);
SortedSet<E> headSet(E toElement);
SortedSet<E> tailSet(E fromElement);
}
基于Java8的Set源码:
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); } }