java_basic

list

List以线性方式存储元素，集合中可以存放重复对象，元素有序。
最常用实现类：

ArrayList：随机访问元素快，增删元素慢。
Vector：Vector与ArrayList相似。但Vector的方法是线程安全的，而ArrayList的方法不是，
        由于线程的同步必然要影响性能，因此ArrayList的性能比Vector好。
LinkedList：随机访问元素慢，顺序访问快，增删元素快。
Stack：栈，继承Vector，特点是先进后出(FILO, First In Last Out)。

set

Set不保存重复的元素。Set与Collection有完全一样的接口。Set接口不保证维护元素的次序。
最常用实现类：

HashSet : 随机查找快。存入HashSet的对象必须定义hashCode()。HashSet查找某个对象时，
          首先用hashCode()方法计算出这个对象的Hash码，然后再根据Hash码到相应的存储区域用equals()方法查找，从而提高了效率。
TreeSet : 保存次序的Set, 底层为树结构。使用它可以从Set中提取有序的序列。
LinkedHashSet : 具有HashSet的查询速度，且内部使用链表维护元素的顺序。于是在使用迭代器遍历Set时，结果会按元素插入的次序显示。

Map

Map 是一种把键对象和值对象映射的集合，它的每一个元素都包含一对键对象和值对象。 Map没有继承于Collection接口。
最常用的实现类：

HashMap：Map基于哈希表的 Map 接口的实现。
HashTable：hashtable和hashmap，从存储结构和实现来讲基本上都是相同的，最大的不同就是hashtable是线程安全的。
LinkedHashMap： LinkedHashMap是HashMap的一个子类，是Map接口的哈希表和链接列表实现。
               它维护着一个双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。
TreeMap ： 基于红黑树的实现。

工具类

Iterator迭代器、ListIterator迭代器、Enumeration枚举类、Arrays 和 Collections

Iterator迭代器:        迭代器是一个用来遍历并选择序列中的对象。Java的Iterator的只能单向移动。
ListIterator迭代器:    ListIterator是一个更加强大的Iterator的子类型。它只能用于各种List类的访问。它最大的优点是可以双向移动。
Arrays:               Java.util.Arrays类能方便地操作数组，它提供的所有方法都是静态的。
Collections:          java.util.Collections是一个包含各种有关集合操作的静态多态方法的工具类，服务于Java的Collection框架。

ArrayList Vector LinkedList Stack fail-fast

1   arraylist 主要是扩容
    
 private void grow(int minCapacity) {
        // 获取当前数组的容量
        int oldCapacity = elementData.length;
        // 扩容。新的容量=当前容量+当前容量/2.即将当前容量增加一半。
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果扩容后的容量还是小于想要的最小容量
        if (newCapacity - minCapacity < 0)
            //将扩容后的容量再次扩容为想要的最小容量
            newCapacity = minCapacity;
        //如果扩容后的容量大于临界值，则进行大容量分配
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData,newCapacity);
    }
 Iterator迭代器、ListIterator迭代器  都是快速失败的 （fail-fast）

2   Vector

    Vector底层是数组。
    有序。Vector底层是数组，数组是有序的。
    可重复。数组是可重复的。
    随机访问效率高，增删效率低。通过索引可以很快的查找到对应元素，而增删元素许多元素的位置都要改变。
    线程安全。很多方法都是synchronized的。

3 fail-fast

    fail-fast 机制是java容器（Collection和Map都存在fail-fast机制）中的一种错误机制。在遍历一个容器对象时，当容器结构被修改，
    很有可能会抛出ConcurrentModificationException，产生fail-fast。  

4   LinkedList

    LinkedList底层是双向链表。
    有序。链表是有序的。
    元素可重复。链表元素可重复。
    随机访问效率低，增删效率高。

    ArrayList与迭代器模式
    Vector与迭代器模式
    LinkedList与迭代器模式
    
5   栈 Stack  先进后出(FILO, First In Last Out) 

    public class Stack<E> extends Vector<E>
    它继承Vector，并额外提供了push、pop、peek、empty、search这几个方法。
    当stack被第一次创建时，它包含0个元素。
    Deque接口和它的实现是更强大的先进先出的栈的实现。
    
总结:

List以线性方式存储元素，集合中可以存放重复对象，元素有序。

最常用实现类：
ArrayList：随机访问元素快，增删元素慢。
Vector：Vector与ArrayList相似。但Vector的方法是线程安全的，而ArrayList的方法不是，由于线程的同步必然要影响性能，因此ArrayList的性能比Vector好。
LinkedList：随机访问元素慢，顺序访问快，增删元素快。
Stack：栈，继承Vector，特点是先进后出(FILO, First In Last Out)。
从上面List的各个实现类的特点不难得出以下结论：

需要快速插入删除元素，应使用LinkedList
不需要快速插入删除元素，需要快速随机访问元素
只有单个线程操作list，应使用ArrayList
有多个线程操作list，应使用Vector

Hashtable与HashMap不同点

Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。

HashMap与LinkedHashMap比较

不同点:

相同点:

都是基于哈希表的实现。
存储的是键值对映射。
都继承了AbstractMap，实现了Map、Cloneable、Serializable。
它们的构造函数都一样。
默认的容量大小是16，默认的加载因子是0.75。
都允许key和value为null。
都是线程不安全的。

TreeMap与HashMap比较

不同点:

增删改查操作的时间复杂度 O(1) log(n)

相同点:

都以键值对的形式存储数据。
都继承了AbstractMap，实现了Map、Cloneable、Serializable。
都是非同步的。

实现类比较

内部排序，至少掌握基础算法如归并排序、交换排序（冒泡、快排）、选择排序、插入排序等。
外部排序，掌握利用内存和外部存储处理超大数据集，至少要理解过程和思路。