集合

一 集合有哪些

1. Collection
   • List
     • 概述
       • 序列 索引
       • 四种访问列表元素方法：get iterator ListIterator foreach
       • 排序：
         • java.lang.Comparable：很多数据类均已实现，如String/Integer
         • java.util.Comparator：扩展使用
         • Collections.sort(List<T> list) <T extends Comparable>
         • Collections.sort(List<T> list, Comparator<? super T> c)
     • ArrayList
       • 基于数组的list实现，默认容量为10，add复杂度O(n)；
       • 相当于Vector，但不同步，Collections.synchronizedList(new ArrayList(...))，基于synchronized代码块；
       • 扩容：最大为Integer.MAX_VALUE，每次add时候计算容量，如果超过，则扩容，每次扩容为oldCapacity的一半，若扩容后还小于所需，则使用minCapacity；
       • 场景：随机查找O(1)，更适合查找，不太适合增删比较多的场景；
       • tips clone 浅拷贝
         • 赋值：基本数据类型和引用数据类型都是同一份，即均改变；
         • 浅拷贝：基本数据类型拷贝，引用数据类型只拷贝指针，即引用数据类型是同一份，若改变则受影响；
         • 深拷贝：全拷贝，基本数据和引用数据类型都是个一份，互不影响；
     • LinkedList
       • 结构：属性(Node<E> first & Node<E> last)
         内嵌private 静态内部类node，
         private static class Node<E> {
         E item;
         Node<E> next;
         Node<E> prev;
         Node(Node<E> prev, E element, Node<E> next) {
         this.item = element;
         this.next = next;
         this.prev = prev;
         }
         }
       • 双链表，实现了List和Deque接口，具有双向队列的特性；
       • 不同步，Collections.synchronizedList(new LinkedList(...))；
       • 相反的顺序返回此deque元素的迭代器，descendingIterator()；
       • 场景：增删O(1)，更适合频繁增删，虽支持随机查找，但需要遍历链表，使用的是折半查找；
     • Vector
       • 概述
         • 基于数组实现，默认容量为10，等同于ArrayList；
         • 同步，所有public method均是synchronized 方法；
         • 扩容：跟ArrayList的区别是，在new Vector可以指定扩容时增长多少，若未设置，则是oldCapacity，默认扩容1倍；
       • Stack
         • 结构：LIFO，更常用的是
           Deque<Integer> stack = new ArrayDeque<Integer>();
         • method：peek()/push()/pop();
   • Set
     • 概述
       • 元素唯一，只有一个空元素；
     • HashSet
       • 概述
         • 内嵌HashMap，初始容量16，负载因子为0.75；
         • HashMap默认的value是new Object()，如何保证不重复，HashMap的key是避免重复的；
         • 不同步，Collections.synchronizedSet(new HashSet(...))；
       • LinkedHashSet
         • 跟HashSet并无什么不同，只不过底层依赖的是LinkedHashMap；
         • 迭代顺序跟add放入的顺序一致，so当你想以放入的顺序返回；
     • TreeSet
       • 内嵌NavigableMap(导航map)，默认是依赖TreeMap，底层是红黑树，根据Comparator比较放入；
       • 默认是自然顺序，另可在new TreeSet时指定Comparator；
       • add/remove/contains的时间复杂度是log(n)；
     • EnumSet
       • 专门用于操作枚举集，对枚举的操作效率高，内嵌Enum<?>[]；
       • iterator返回的迭代器以自然顺序 （枚举常量的声明顺序）遍历元素；
       • 不允许null元素，内嵌静态内部类SerializationProxy进行序列化；
   • Queue
     • 概述
       • 队列，通常但不一定是以FIFO（先进先出）方式排序元素，尾部插入，头部删除；
       • 插入/提取/检查操作，这些方法中的每一种都有两种形式：如果操作失败，则抛出一个异常，另一种返回一个特殊值（ null或false ，具体取决于操作）；
       • remove()和[`poll()方法删除并返回队列的头；
       • element()和peek()方法返回，但不要删除，头的队列；
       • Queue实现通常不允许插入null元素，但LinkedList是个例外；
     • Deque
       • 双端队列，支持两端元素插入和移除的线性集合；
       • 作为队列时，具有FIFO的行为，尾部插入，头部删除；
       • 作为堆栈时，具有LIFO的行为，应优先于传统的Stack，元素从头部弹出；
       • 与List接口不同，Deque不支持索引访问元素；
       • Deque同样不允许插入null元素；
       • 插入：add=addLast/addFirst/offer=offerLast/offerFirst
       • 检索：element/peek=peekFirst/peekLast
       • 删除：poll=pollFirst/pollLast/remove=removeFirst/removeLast
       • 堆栈操作：push/pop；
2. Map
   • 概述
     • 键值对，替代原有抽象类Dictionary；
     • 内嵌子接口：Entry<K,V>；
   • HashMap
     • 概述
       • 基于hash表实现，允许null key & value，与Hashtable相当，但不同步；
       • capacity为16，必须是2的倍数，load factor指table的填充比例，默认0.75，当对迭代性能要求比较高时，不能把capacity设置的太大，同时load factor不要超过0.75，否则会明显增加冲突几率；
       • put原理：当在第一次put时，先对table初始化，通过hash计算得到存放位置table[i]，存放；当再次put时，同样经过hash计算得到位置，则采用链表法解决冲突，存放在相同位置的next区域；在JDK8中设置了链表的默认阈值为8，如果超过这个值，则进行红黑树化；如果节点已经存在就替换old value(保证key的唯一性)；如果bucket满了(超过load factor*current capacity)，就要resize，变为原来2倍；
     • LinkedHashMap
       • 基于hash表和双向链表，与HashMap的区别在于迭代顺序；
       • 迭代顺序：内置标识位boolean accessOrder，默认为false，则是插入顺序，设置为true，则是访问顺序；
   • Hashtable
     • 基于hash表的实现，继承于Dictionary，现已废弃，主要了解与HashMap的区别；
     • 区别是：同步（所有方法被synchronized修饰），不允许null key & value，key的hash方式也不同；
     • tips：hash冲突处理
       • 拉链法：构建一个同义词的链表，hashmap就是基于此；
       • 开放定址法：当p冲突时，基于p再hash处理，直到不冲突为止，主要有三种实现方式，即线性探测/二次探测/伪随机探测；
   • TreeMap
     • 基于红黑树实现，containsKey/get/put/remove的时间复杂度log(n);
     • 排序是根据key的Comparable natural ordering，或者在构造map的时候传递Comparator；
   • EnumMap
     • 类似于EnumSet，但key是Enum对象
3. Iterator
   • 概述
     • 只有remove方法；
     • list迭代顺序均是放入的顺序，set的迭代是按add后排序后，hashset根据hashcode处理（但不保证），treeset则是自然顺序；
   • ListIterator
     • 只有list接口才有，增加了add和set方法，并可指定索引迭代；
     • add是在迭代之后的地方add，set是对正迭代的进行修改；