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不同点

不同点	HashMap	Hashtable
数据结构	数组+链表+红黑树	数组+链表
继承的类不同	继承AbstractMap	继承Dictionary
是否线程安全	否	是
性能高低	高	低
默认初始化容量	16	11
扩容方式不同	原始容量x2	原始容量x2 + 1
底层数组的容量为2的整数次幂	要求一定为2的整数次幂	不要求
确认key在数组中的索引的方法不同	i = (n – 1) & hash;	index = (hash & 0x7FFFFFFF) % tab.length;
遍历方式	Iterator(迭代器)	Iterator(迭代器)和Enumeration(枚举器)
Iterator遍历数组顺序	索引从小到大	索引从大到小

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

HashMap与LinkedHashMap比较

不同点:

不同点	HashMap	LinkedHashMap
数据结构	数组+链表+红黑树	数组+链表+红黑树+双向循环链表
是否有序	无序	有序

相同点:

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

TreeMap与HashMap比较

不同点:

不同点	HashMap	TreeMap
数据结构	数组+链表+红黑树	红黑树
是否有序	否	是
是否实现NavigableMap	否	是
是否允许key为null	是	否

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

相同点:

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

实现类比较

实现类	数据结构	是否线程安全	key是否可为null	是否有序
HashMap	数组+链表+红黑树（since JDK1.8）	否	是	否
Hashtable	数组+链表	是	否	否
LinkedHashMap	数组+链表+红黑树（since JDK1.8）+ 双重链接列表	否	是	是
WeakedHashMap	数组+链表+队列	否	是	否
TreeMap	红黑树	否	否	是

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