本文共 6043 字,大约阅读时间需要 20 分钟。
LinkedHashSet
public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable |
可以看到LinkedHashSet是继承自HashSet,但是在看源码注释时,会发现LinkedHashSet存储的元素是不可重复,有序的集合,可在将HashSet时,就知道了HashSet是无序的,这是怎么回事。
先看下LinkedHashSet的源码。
/** * 构造器 * @param initialCapacity 容量 * @param loadFactor 加载因子 */ public LinkedHashSet(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor, true); }
/** * 构造器 * @param initialCapacity 容量 */ public LinkedHashSet(int initialCapacity) { super(initialCapacity, .75f, true); }
/** * 构造器,默认容量是16,加载因子是0.75,但是会发现里面的源码中多了一个参数,而这个构造器一样是调用了父类的构造器 */ public LinkedHashSet() { super(16, .75f, true); } /** * 构造器,指定集合 * @author suzhiwei * @param c void */ public LinkedHashSet(Collection<? extends E> c) { super(Math.max(2*c.size(), 11), .75f, true); addAll(c); } /** * 可分割的迭代器,主要用于多线程迭代时使用的 * @return Spliterator<E> */ @Override public Spliterator<E> spliterator() { return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED); } |
以上就是LinkedHashSet的全部源码,感觉很不可思议,只有4个构造器加上一个方法就没了,而LinkedHashSet是继承自HashSet,说明增删改查的方法都是来自HashSet的。
在第三个构造器中,很奇怪,多了个参数,点进去看下会发现,这个就是之前在HashSet讲的,那个特殊的修饰符default的构造器。
/** * 构造器 * @param initialCapacity 容量 */ public LinkedHashSet(int initialCapacity) { super(initialCapacity, .75f, true); }
/** * 这个构造器的修饰符是defualt,这个构造器主要是给子类LinkedHashSet用的 * @param initialCapacity * @param loadFactor * @param dummy 这个是用于LinkedList */ HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); } |
由此可见LinkedHashSet的底层,其实就是用了LinkedHashMap的Key特性(有序),这一点和HashSet有点类型,HashSet则是用了HashMap的特性。
这说明了,LinkedHashSet底层就是数组+红黑树+双向链表的,进而也实现了有序。
public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; } |
进一步追溯这个构造器时,会发现accessOrder是false,并且也没有提供别的构造器了,说明了LinkedHashSet仅支持插入顺序排序,不支持访问顺序排序。
TreeSet
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable |
TreeSet是不可重复的有序集合,特点是可以按照自然排序,或通过实现Comparable或Comparator接口来自定义排序规则。
TreeSet实现了NavigableSet接口,而NavigableSet接口继承自SortedSet接口的。
SortedSet接口的特性就是确保有序性,这也说明了为什么TreeSet是有序的,而且在SortedSet源码的注释中,可以看到通过实现Comparable或Comparator接口来实现自定义排序。
public interface NavigableSet<E> extends SortedSet<E> |
属性与构造器:
/** * 存储元素的集合,而会发现TreeMap也是实现了NavigableMap这个接口。 */ private transient NavigableMap<E,Object> m;
/** * value的占位符 */ private static final Object PRESENT = new Object();
/** * 指定NavigableMap的子类集合进来。 */ TreeSet(NavigableMap<E,Object> m) { this.m = m; }
/** * 构造器,会发现实际里面是创建了一个TreeMap */ public TreeSet() { this(new TreeMap<E,Object>()); } /** * 构造器,里面还是使用TreeMap * @param comparator 指定排序规则 */ public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<>(comparator)); } /** * 按照指定集合 * @param c */ public TreeSet(Collection<? extends E> c) { this(); addAll(c); }
/** * 将SortedSet的集合中的元素放到TreeMap * @param s */ public TreeSet(SortedSet<E> s) { this(s.comparator()); addAll(s); } |
在此系列文章中,之前讲的TreeMap就是实现了NavigableMap接口,而在TreeSet中会发现,存储的元素就是NavigableMap容器。
在TreeSet的构造器中,可以发现如果没有指定NavigableMap接口的容器的话,默认的存储容器就是TreeMap,在一定程度上来说,可以说TreeSet底层就是用TreeMap存储。
序列化:
实现序列化接口,但是存储的容器NavigableMap是用transient修饰的,所以序列化和HashSet是一样的。
/** * 序列化写出 * @param s */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out any hidden stuff s.defaultWriteObject();
// Write out Comparator s.writeObject(m.comparator());
// Write out size s.writeInt(m.size());
// Write out all elements in the proper order. for (E e : m.keySet()) s.writeObject(e); }
/** * 序列化读取 * @param s */ private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in any hidden stuff s.defaultReadObject();
// Read in Comparator @SuppressWarnings("unchecked") Comparator<? super E> c = (Comparator<? super E>) s.readObject();
// Create backing TreeMap TreeMap<E,Object> tm = new TreeMap<>(c); m = tm;
// Read in size int size = s.readInt();
tm.readTreeSet(size, s, PRESENT); }
/** * 分割迭代器,主要用于多线程迭代 * @return Spliterator<E> */ public Spliterator<E> spliterator() { return TreeMap.keySpliteratorFor(m); } |
其他方法:
/** * 元素数量 * @return int */ public int size() { return m.size(); } /** * 容器是否为空 * @return boolean */ public boolean isEmpty() { return m.isEmpty(); } /** * 是否包含这个元素 */ public boolean contains(Object o) { return m.containsKey(o); } /** * 新增元素 */ public boolean add(E e) { return m.put(e, PRESENT)==null; } /** * 删除元素 */ public boolean remove(Object o) { return m.remove(o)==PRESENT; } /** * 清空容器 */ public void clear() { m.clear(); } /** * 截取 */ public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { return new TreeSet<>(m.subMap(fromElement, fromInclusive, toElement, toInclusive)); } /** * 头set */ public NavigableSet<E> headSet(E toElement, boolean inclusive) { return new TreeSet<>(m.headMap(toElement, inclusive)); } /** * 尾set */ public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { return new TreeSet<>(m.tailMap(fromElement, inclusive)); } /** * 截取 */ public SortedSet<E> subSet(E fromElement, E toElement) { return subSet(fromElement, true, toElement, false); } /** * 头 */ public SortedSet<E> headSet(E toElement) { return headSet(toElement, false); } /** * 尾set */ public SortedSet<E> tailSet(E fromElement) { return tailSet(fromElement, true); } /** * 比较 */ public Comparator<? super E> comparator() { return m.comparator(); } /** * 首元素 */ public E first() { return m.firstKey(); } /** * 尾元素 */ public E last() { return m.lastKey(); } /** * 小于e的最大元素 */ public E lower(E e) { return m.lowerKey(e); } /** * 大于或等于e的最大元素 */ public E floor(E e) { return m.floorKey(e); } /** * 大于或等于e的最小元素 */ public E ceiling(E e) { return m.ceilingKey(e); } /** * 移除首元素 */ public E pollFirst() { Map.Entry<E,?> e = m.pollFirstEntry(); return (e == null) ? null : e.getKey(); } /** * 移除尾元素 */ public E pollLast() { Map.Entry<E,?> e = m.pollLastEntry(); return (e == null) ? null : e.getKey(); } |
会发现这些方法都是调用存储容器NavigableMap(TreeMap)的方法,并且也是没有get()方法。
转载地址:http://vlmxi.baihongyu.com/