数据结构

继承关系图
-- Collection <Interface>
    -- List <Interface>
        -- ArrayList
        -- Vector
        -- LinkedList
    -- Set <Interface>
        -- HashSet
            -- LinkedHashSet
        -- TreeSet
-- Map <Interface>
    -- HashMap
        -- LinkedHashMap
    -- TreeMap

Colletion

Collection是单列集合继承树中的根接口，有两大子接口List和Set。

List

List集合的特点：有序（存和取的顺序一致）、可重复

ArrayList

底层结构用数组实现，因此查询快，增删慢。
线程不安全，但效率高。

Vector

底层结构用数组实现，因此查询快，增删慢。
线程安全，但效率低。

LinkedList

底层结构用链表实现，因此查询慢，增删快。
线程不安全，但效率高。

Set

Set集合的特点：无序（存和取的顺序不一致）、不重复。

HashSet

HashSet每次调用add()的时候都要去重复元素。依赖于HashMap实现。
去重复元素方法：

    1. 先调用hashCode()得到hash值，比较hash值，如果没有相同的hash值则直接存储。
    2. 如果hash值相同时，则调用equal()方法比较。
    3. 如果返回true则不添加，如果返回false则将元素加入集合中。

LinkedHashSet

特点：怎么存的就怎么取。
继承自HashSet，为链表结构。

TreeSet

特点：二叉树结构，按照指定的方式进行排序。依赖于TreeMap实现。
比较要有个Comparator比较器或对象是实现了Comparable接口。

Map

双列集合的根接口。
put数据的时候，会返回被覆盖的value。如果第一次存储，返回null；第二次存储，覆盖前一次的值，并返回。

HashMap、LinkedHashMap、TreeMap

Map的数据结构集中在key。将value都变为空对象时，HashMap就变为HashSet了。

HashMap与Hashtable的区别

共同点：
    HashMap和Hashtable都是用哈希算法

不同点：
    1. Hashtable是JDK1.0版本出现的，同步（线程安全），效率低；
    HashMap是JDK1.2版本出现的，不同步（线程不安全），效率高。
    2. Hashtable存的键和值都不能为null，否则报NullPointerException；
    HashMap存的键和值都可以为null，保证代码可以继续执行。

Collection与Collections的区别

Collection是单列集合的根接口，Collections是List的一个工具集合，多为static方法。
除名字相似外并无可比性。

List中ArrayList、LinkedList、Vector的选择

1. 增删少、查询多，且为单线程 选ArrayList
2. 增删少、查询多，但为多线程 选Vector
3. 增删多、查询少 选LinkedList
4. 单线程，增删与查询都多 选ArrayList