Java集合
Java中集合
- Java中集合类是Java编程中使用最频繁、最方便的类。集合类作为容器类可以存储任何类型的数据，当然也可以结合泛型存储指定的类型（不过泛型仅仅在编译期有效，运行时是会被擦除的）。集合类中存储的仅仅是对象的引用，并不存储对象本身。集合类的容量可以在运行期间进行动态扩展，并且还提供很多很方便的方法，如求集合的并集、交集等。
-
集合类结构
- Java中的集合包含多种数据结构，如链表、队列、哈希表等。从类的继承结构来说，可以分为两大类，一类是继承自Collection接口，这类集合包含List、Set和Queue等集合类。另一类是继承自Map接口，这主要包含了哈希表相关的集合类。
List、Set和Queue
- Collection 接口的接口 对象的集合（单列集合）
-
- List接口：元素按进入先后有序保存，可重复
-
- LinkedList：接口实现类， 链表， 插入删除， 没有同步， 线程不安全
- ArrayList：接口实现类， 数组， 随机访问， 没有同步， 线程不安全
- Vector：接口实现类 数组， 同步， 线程安全
- Stack：是Vector类的实现类
- Vector，它是ArrayList的线程安全版本，而Stack则对应栈数据结构
- ArrayList与LinkedList对比：ArrayList的底层的通过数组实现，所以其随机访问的速度比较快，但是对于需要频繁的增删的情况，效率就比较低了。而对于LinkedList，底层通过链表来实现，所以增删操作比较容易完成，但是对于随机访问的效率比较低。
- Set接口：仅接收一次，不可重复，并做内部排序
- HashSet：使用hash表（数组）存储元素
- LinkedHashSet：链表维护元素的插入次序
- HashSet和LinkedHashSet的区别
- HashSet和LinkedHashSet的区别在于后者可以保证元素插入集合的元素顺序与输出顺序保持一致。而TresSet的区别在于其排序是按照Comparator来进行排序的，默认情况下按照字符的自然顺序进行升序排列。
- TreeSet：底层实现为二叉树，元素排好序
- HashSet：使用hash表（数组）存储元素
- HashSet底层数据结构采用哈希表实现，元素无序且唯一，线程不安全，效率高，可以存储null元素，元素的唯一性是靠所存储元素类型是否重写hashCode()和equals()方法来保证的，如果没有重写这两个方法，则无法保证元素的唯一性
- LinkedHashSet底层数据结构采用链表和哈希表共同实现，链表保证了元素的顺序与存储顺序一致，哈希表保证了元素的唯一性。线程不安全，效率高。
- TreeSet底层数据结构采用二叉树来实现，元素唯一且已经排好序；唯一性同样需要重写hashCode和equals()方法，二叉树结构保证了元素的有序性。
- Set和List的总结
- List,Set都是继承自Collection接口，Map则不是
- Set与List的主要区别是Set是不允许元素重复的，而List则可以允许元素重复的。判断元素的重复需要根据对象的hash方法和equals方法来决定。这也是我们通常要为集合中的元素类重写hashCode方法和equals方法的原因
- Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变。
- Queue接口
- Queue：一般可以直接使用LinkedList完成，从上述类图也可以看出，LinkedList继承自Deque，所以LinkedList具有双端队列的功能。PriorityQueue的特点是为每个元素提供一个优先级，优先级高的元素会优先出队列。
- Iterable接口：从这个图里面可以看到Collection类继承自Iterable，该接口的作用是提供元素遍历的功能，也就是说所有的集合类（除Map相关的类）都提供元素遍历的功能。
- ArrayList和Vector都是用数组实现的，主要有这么三个区别：
- Vector是多线程安全的，线程安全就是说多线程访问同一代码，不会产生不确定的结果。而ArrayList不是，这个可以从源码中看出，Vector类中的方法很多有synchronized进行修饰，这样就导致了Vector在效率上无法与ArrayList相比；
- 两个都是采用的线性连续空间存储元素，但是当空间不足的时候，两个类的增加方式是不同。
- Vector可以设置增长因子，而ArrayList不可以。
- Vector是一种老的动态数组，是线程同步的，效率很低，一般不赞成使用
-
适用场景分析
- Vector是线程同步的，所以它也是线程安全的，而ArrayList是线程异步的，是不安全的。如果不考虑到线程的安全因素，一般用ArrayList效率比较高。
- 如果集合中的元素的数目大于目前集合数组的长度时，在集合中使用数据量比较大的数据，用Vector有一定的优势。
- TreeSet 是二差树（红黑树的树据结构）实现的,Treeset中的数据是自动排好序的，不允许放入null值
- HashSet 是哈希表实现的,HashSet中的数据是无序的，可以放入null，但只能放入一个null，两者中的值都不能重复，就如数据库中唯一约束
- HashSet要求放入的对象必须实现HashCode()方法，放入的对象，是以hashcode码作为标识的，而具有相同内容的String对象，hashcode是一样，所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例
-
适用场景分析:
- HashSet是基于Hash算法实现的，其性能通常都优于TreeSet。为快速查找而设计的Set，我们通常都应该使用HashSet，在我们需要排序的功能时，我们才使用TreeSet。
Map接口键值对的集合(双列集合)
-
Map用于保存具有映射关系的数据，Map里保存着两组数据：key和value，它们都可以使任何引用类型的数据，但key不能重复。所以通过指定的key就可以取出对应的value。
-
请注意！！！， Map 没有继承 Collection 接口
-
Map类型的集合最大的优点在于其查找效率比较高，理想情况下可以实现O(1)的时间复杂度
-
Hashtable 接口实现类， 同步， 线程安全
-
HashMap 接口实现类 ，没有同步， 线程不安全-
- LinkedHashMap 双向链表和哈希表实现
- WeakHashMap
-
TreeMap 红黑树对所有的key进行排序
-
IdentifyHashMap
-
EnumMap
-
-
HashMap和HashTable的区别
-
TreeMap方法
-
Map其他方法
-
HashMap 非线程安全
HashMap：基于哈希表实现。使用HashMap要求添加的键类明确定义了hashCode()和equals()[可以重写hashCode()和equals()]，为了优化HashMap空间的使用，您可以调优初始容量和负载因子。TreeMap：非线程安全基于红黑树实现。TreeMap没有调优选项，因为该树总处于平衡状态。
-
适用场景分析：
- HashMap和HashTable:HashMap去掉了HashTable的contains方法，但是加上了containsValue()和containsKey()方法。HashTable同步的，而HashMap是非同步的，效率上比HashTable要高。HashMap允许空键值，而HashTable不允许。
- HashMap：适用于Map中插入、删除和定位元素。
- Treemap：适用于按自然顺序或自定义顺序遍历键(key)。
-
线程安全集合类与非线程安全集合类
- LinkedList、ArrayList、HashSet是非线程安全的，Vector是线程安全的;
- HashMap是非线程安全的，HashTable是线程安全的;
- StringBuilder是非线程安全的，StringBuffer是线程安全的。
-
数据结构
- ArrayXxx:底层数据结构是数组，查询快，增删慢
- LinkedXxx:底层数据结构是链表，查询慢，增删快
- HashXxx:底层数据结构是哈希表。依赖两个方法：hashCode()和equals()
- TreeXxx:底层数据结构是二叉树。两种方式排序：自然排序和比较器排序
-
实体类对比：
- Map中最常用的是HashMap，LinkedHashMap与HashMap的区别在于前者能够保证插入集合的元素顺序与输出顺序一致。这两者与TreeMap的区别在于TreeMap是根据键值进行排序的，当然其底层的实现也有本质的区别，如HashMap底层是一个哈希表，而TreeMap的底层数据结构是一棵树。
- TreeMap和LinkedHashMap的区别，前者是按字符串排序进行输出的，而后者是根据插入顺序进行输出 的。细心的读者可以发现，HashMap与TreeMap的区别，与之前提到的HashSet与TreeSet的区别是一致的，在后续进行源码分析的时候，我们可以看到HashSet和TreeSet本质上分别是通过HashMap和TreeMap来实现的，所以它们的区别自然也是相同的。HashTable现在已经很少使用了，与HashMap的主要区别是HashTable是线程安全的，不过由于其效率比较低，所以通常使用HashMap，在多线程环境下，通常用CurrentHashMap来代替。