这 3 个 Set 集合的实现有点简单，那来做个总结吧

• 2019 年 10 月 3 日
• 筆記

Set ??? Java Collections Framework ?????????????????????????????? null ???Java ??????? Set ????

• HashSet: ????????????????????????????
• LinkedHashSet: ?????????????????????????
• TreeSet: ?????????????????????????

JDK ?????? 3 ? Set ???????????????: HashMap, LinkedHashMap ? TreeMap???? 3 ? Map ??????????????????

????? 3 ? Set ??????????????????????????

HashSet

???????HashSet ???? 200 ?????????????????????

public class HashSet<E> extends AbstractSet<E>      implements Set<E>, Cloneable, java.io.Serializable {    // ?????????    private transient HashMap<E,Object> map;      // ??? HashMap ??? key ???? value ?    private static final Object PRESENT = new Object();    // ?????    public HashSet() {        map = new HashMap<>(); // 0.75f ????    }    // ????????????    public HashSet(Collection<? extends E> c) {        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));        addAll(c);    }    // ???? HashMap ??????????    public HashSet(int initialCapacity, float loadFactor) {        map = new HashMap<>(initialCapacity, loadFactor);    }    // ???????    public HashSet(int initialCapacity) {        map = new HashMap<>(initialCapacity);    }    // ?????????????? LinkedHashSet ???    // ?? LinkedHashMap ??????    HashSet(int initialCapacity, float loadFactor, boolean dummy) {        map = new LinkedHashMap<>(initialCapacity, loadFactor);    }    // HashSet ???????? HashMap ?? key    public Iterator<E> iterator() {        return map.keySet().iterator();    }      // ?????????? Set ???????????    public int size() {        return map.size();    }      public boolean isEmpty() {        return map.isEmpty();    }      public boolean contains(Object o) {        return map.containsKey(o);    }    // ?????? value ??? PRESENT ?? Object ??    public boolean add(E e) {        return map.put(e, PRESENT)==null;    }      public boolean remove(Object o) {        return map.remove(o)==PRESENT;    }      public void clear() {        map.clear();    }    // JDK 8 ??????????? - ??????    public Spliterator<E> spliterator() {        return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);    }  }

????????? HashMap ?????????? PRESENT ?????? map ? value ?????????????????? HashMap?

??? Set ?? Map?????????? Java ????????????????? equals ? hashCode ?????

• ?????? equals ???????????????? hashCode
• ????????????? hashCode

???HashSet ?????????????? equals ? hashCode ?????

???HashSet ???????? HashMap ? key??????

1. ??????? hashCode ????????????
2. ?????????????? equals ??????
3. ?????????????????????????? value ????? key ????

??????????? HashMap ?? KeyIterator?

LinkedHashSet

LinkedHashSet ????????????? HashSet??????

public class LinkedHashSet<E> extends HashSet<E>    implements Set<E>, Cloneable, java.io.Serializable {    // ???????????????? LinkedHashMap    public LinkedHashSet(int initialCapacity, float loadFactor) {      super(initialCapacity, loadFactor, true);    }      public LinkedHashSet(int initialCapacity) {      super(initialCapacity, .75f, true);    }      public LinkedHashSet() {      super(16, .75f, true);    }      public LinkedHashSet(Collection<? extends E> c) {      super(Math.max(2*c.size(), 11), .75f, true);      addAll(c);    }      @Override    public Spliterator<E> spliterator() {      return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);    }  }

???????????????????? super ???? HashSet ?????????????????????????? LinkedHashMap?

? HashSet ???????????????????? add, contains ? remove?????? HashSet?????????????????????????LinkedHashSet ??????????????? HashSet ???????????????????

TreeSet

TreeSet ?????? Set ?????????????????????????? Comparator ????

??? TreeMap ???????????????? API ???lower?floor?ceiling ? higher ????????????????????????????? log(n) ???????????? add, contains ? remove?

?????????Set ???????? equals ???????????? TreeSet ???? compareTo ?? compare ??????????????????????? Set ??????

TreeSet ????????????? TreeMap ?????????????

??????????

?????????????????????????????????????????????????????????????

ArrayList ? LinkedList ??????

• ???????ArrayList ???????LinkedList ??????
• ????ArrayList ??????????????????????????LinkedList ?????????????????????????
• LinkedList ???????????
• ???????? null ?????????
• ???????????????? Collections.synchronizedList(List list) ??????????? List

ArrayList ? Vector ??????

• ArrayList ??????Vector ????
• ????ArrayList ?? 1.5 ???? ; Vector ?? 2????

JDK 8 ? HashMap ???????

• ????????? + ?? + ???????????????????????????? O(n) ?? O(log(n))
• ???????? 1.7 ??4???? + 5?????????1???? + 1?????
• ???????1.7 ?????????????? 1.8 ????2?????????????????????????????????????????????????

HashMap ? HashTable ???

• HashMap ????? ; HashTable ????
• HashMap ?? key ? Vale ? null ; HashTable ??? key?value ? null
• HashMap ????? 2^4 ?????? 2^n ; HashTable ?????11????, ???? 2^n
• HashTable ?????????????? ; HashMap ?? & ??? ????

HashMap ? LinkedHashMap ???

• LinkedHashMap ??? HashMap ???????????????
• LinkedHashMap ????????????
• LinkedHashMap ???????????? ; ? HashMap ????????
• LinkedHashMap ???????????????? LRU ??

??? fast-fail???????

fast-fail?????????????????????????????????? ConcurrentModificationException ??????

??????????????????????????????????????

??????? modCount ??????????????????????????? iterator() ?????????? modCount ????????????????????????? next, remove ????????

??

??????????????????????????????????????? Java ????????????????????????????