Collection体系
Collection体系
工作中消失而面试却长存的算法与数据结构
- 优秀的算法和数据结构被封装到了Java的集合框架之中
数据结构考点
- 数组和链表的区别
- 链表的操作，如反转，链表环路检测，双向链表，循环链表相关操作
- 队列，栈的应用
- 二叉树的遍历方式及其递归和非递归的实现
- 红黑树的旋转
算法考点
- 内部排序：如递归排序，交换排序（冒泡、快排），选择排序，插入排序
- 外部排序：应掌握如何利用有限的内存配合海量的外部存储来处理超大数据集，写不出来也要有相关的思路
考点扩展
- 哪些排序是不稳定的，稳定意味着什么
- 不同数据集，各种排序最好和最差的情况
- 如何优化算法
Java集合框架
Collection 接口有 3 种子类型集合: List、Set 和 Queue，再下面是一些抽象类，最后是具体实现类， ArrayList、LinkedList、HashSet、LinkedHashSet、ArrayBlockingQueue等
集合(Set)
集合(Set<\E>)是一种容器(Collection
ConcurrentSkipListSet, CopyOnWriteArraySet, EnumSet, HashSet, LinkedHashSet, TreeSet，ImmutableCollections.SetN这些类。都是集合。只不过他们用来容纳数据。并且保证数据不重复的手段不一样。
映射（Map）是什么？
映射(Map)是两个集合间的对应关系。在Java中的Map将键(Key)映射到值(Value)。Map在Java中是一个接口，具体的实现有很多，比如HashMap，TreeMap ,Hashtable，SortedMap等。
为了实现映射，我们需要容器存储Key，需要容器存储value，也需要容器存储key-value。一组key-value在Java中我们称之为一个条目(Entry)。
Map的诸多实现中有：ConcurrentHashMap, ConcurrentSkipListMap, EnumMap, HashMap, Hashtable, LinkedHashMap, Properties, TreeMap,
和集合类似Map最常的种实现如下：
- ConcurrentHashMap，HashMap、Hashtable、LinkedHashMap是基于哈希表的实现
- TreeMap是基于树的实现
- ConcurrentSkipListMap是基于跳表的实现
- EnumMap是基于位运算的实现
和集合类似，哈希表的实现是一种稀疏的结构。树的实现是一种紧密的结构。树的实现中间继承路径中会实现NavigableMap<K,V>，从而实现浏览的能力。
HashMap vs Hashtable
上面诸多实现当中HashMap和Hashtable实现非常相近。这里有2个显著的区别：
- Hashtable中的所有对用户的方法都用synchronized关键字上了锁（因此线程安全）。如果你学到了本课程后续的并发编程环节。你会知道这并不是一种好的实现方案。HashMap没有做任何控制。
- HashMap允许null key/null value； Hashtable不允许null key/null value
