Java集合API

1. ArrayList
(1) 当List<String> list = new ArrayList<String> ();
其构造器执行：
this.elementData = new Object[10];
即创建一个大小为10的Object类型的数组。

(2) add(E): 用传入的对象填充数组的下一个位置。
若数组长度不够用了怎么办呢？
1) minCapacity = 数组中已有元素的数目 + 1;
2) 用minCapacity与数组的大小比较（注：数组中元素的数目不一定等于数组的大小）
若 minCapacity > 数组的大小(oldCapacity)
         则 newCapacity = oldCapacity * 1.5 + 1;
              若newCapacity仍 < minCapacity
                    则newCapacity = minCapacity;

然后用newCapacity作为新数组的长度。
用elementData = Arrays.copyOf(elementData, newCapacity);来生成新的数组的长度。

(3) add(int, E): 将元素插入到指定下标的位置上
首先要确保要插入指定的index下标必须 < 数组的长度
然后将元素放到指定的index位置，将index之后的元素向右移动一位。

(4) remove(E): 使用ArrayList的fastRemove方法删除在遍历中所有为E的对象。
fastRemove的实现为：
将index之后的对象往前移一位，并将数组的最后一个元素的位置置为null.

(5) remove(int): 删除指定位置的对象
remove(int)相比remove(E)少了对象位置的查找，所以性能会好些。

(6) iterator(): 该方法由ArrayList的父类AbstractList实现，每次调用iterator方法时，都会创建一个新的AbstractList内部类Iter类的实例。
1）当调用hasNext()时，会比较当前指向的数组位置是否等于数组中所有元素的数目，相等则返回false.
2）当调用next()时，则通过index调用get(index+1)来获取元素。

(7) contains(E): 判断E在ArrayList中是否存在
若E为null, 则用==判断
若E不为null, 则用equals判断

ArrayList总结：
1） ArrayList是基于数组方式实现的，但可以无限的扩容。
2）在ArrayList中插入元素时，可能要扩容；但在删除元素时，并不会减小数组的容量，如果希望缩小容量，则需要调用ArrayList的trimToSize().
3）ArrayList是非线程安全的。

2. LinkedList
LinkedList是基于双向链表实现的，即集合中的每一个元素，都知道其前一个元素和后一个元素的位置。
在LinkedList中，以一个内部类Entry来代表集合中的元素。
元素的值赋值给Entry内部类的element属性，Entry的next属性指向元素的后一个元素；Entry的previous属性指向元素的前一个元素。
基于这样的机制，可以快速实现集合中元素的移动。
(1) LinkedList():
在创建LinkedList对象的实例时，先创建一个element属性为null, next属性为null, previous属性为null的Entry对象，并赋值给LinkedList的全局变量header: header.next = header.previous = header;
即在执行构造器时，将header的next, header的previous都指向header，以形成双向链表所需的闭环。

(2) add(E)
当向LinkedList中增加元素时：
1）建一个Entry对象
2）将此Entry对象的next指向header
3）将此Entry对象的previous指向header的previous
4）将新元素的previous对象的next指针指向新元素
5）将新元素的next对象的next对象的previous指针指向新元素
以此完成双向链表共4个指针的修改。

LinkedList的add方法，不用想ArrayList，要考虑数组扩容以及复制的问题，但它每增加一个元素，就要增加一个Entry对象，并修改它相邻的两个元素的属性

(3) remove(E)
LinkedList删除元素时，要遍历整个LinkedList，匹配过程与ArrayList一致，但找到元素后，删除元素的过程比ArrayList快多了：只需要修改双向指针，不用移动元素。

(4) get(int)
LinkedList存于双向链表中，所以不像数组有下标，get过程比ArrayList麻烦：
若index < LinkedList长度的一半
    则从头查找index位置的元素
否则
    则从尾向前查找index位置的元素

(5) iterator()
也由其父类AbstractList实现。
但由于LinkedList是双向链表，所以也可以调用hasPrevious()与previous()向前遍历。

(6) contains(E)
遍历所有元素，过程与ArrayList一致
对null用==，对非null用equals

LinkedList总结：
1）LinkedList是基于链表实现的。
2）LinkedList在插入元素时，要创建一个Entry对象，并切换相应元素的前后引用；在查找元素时，要遍历整个链表；在删除元素时，找到要删除的元素，然后将此元素从链表上删除。
3）LinkedList是非线程安全的

3. Vector
Vector与ArrayList一样，也是基于Object数组实现的

(1) add(E)
Vector的add方法加入了Synchronized关键字，所以是线程安全的
与ArrayList不同的是：扩容方法不同。
capacityIncrement为Vector扩容时自动增加的大小, 有创建Vector时有构造器参数传入，默认为0
若capacityIncrement > 0
     则newCapacity = oldCapacity + capacityIncrement；
若capacityIncrement <= 0
     则capacityIncrement = oldCapacity * 2；

(2) Vector的其他方法都与ArrayList一致，唯一不同的是加入了Synchronized关键字，变成了线程安全。

4. Stack
Stack继承自Vector, 在其基础上实现了栈的后进先出（LIFO): 主要增加了push(), pop(), peek()三个方法。
(1) push()
向Stack中增加元素，具体过程同Vector的add(E)

(2) peek()
先计算出数组的大小，然后获取数组的最后一个元素。

(3) pop()
先用peek()获取到数组中最后一个元素，然后从数组中删除这个元素

Stack总结：Stack是基于Vector的实现，遵循LIFO原则。

5. HashSet
HashSet是对Set接口的实现。
Set接口与List接口的区别：Set是无序不可重复；List是有序可重复。

(1) HashSet()
新建一个HashMap对象

(2) add(E)
调用HashMap的put(Object, Object)方法来完成：将需要增加的元素作为map中的key, value则传入一个已经创建好的对象：private static final Object PRESENT = new Object();

(3) remove(E)
调用HashMap的remove(E)

(4) contains(E)
调用HashMap的containsKey(E)

(5) iterator()
调用Hashmap的内部类keySet的iterator()方法

HashSet总结：
(1) HashSet是基于HashMap实现的，无容量限制。
(2) Hashset是非线程安全的

6. TreeSet
TreeSet基于TreeMap实现。
TreeSet与HashSet的主要区别在于,TreeSet支持排序。

TreeSet与TreeMap的关系类似于HashSet与HashMap的关系

TreeSet与HashSet一样，也是完全基于Map来完成的，并且同样不支持get(int)来获取指定元素的位置。TreeSet还提供了一些排序方面的支持，
例如：我的代码中的“TreeSet排序”中，可以加入实现了Comparable接口类的实例作为TreeSet的元素，这样即使加入的顺序是混乱的，TreeSet会根据compareTo方法定义来自动做排序。打印结果为：
age:20,, age:21,, age:22,,

TreeSet总结：
(1) TreeSet基于TreeMap实现，支持排序
(2) TreeSet是非线程安全的

7. HashMap(重中之重)
(1) HashMap的数据结构
HashMap的数据结构是“数组+链表”。即HashMap的底层就是一个数组，而数组中的每个元素又是一个链表。

当新建一个HashMap的时候，会初始化一个Entry类型的数组：
transient Entry[] table;

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;
    ……
}
Entry对象就是数组的元素，每个Entry对象就是一个Key-Value对，它持有指向链表下一个对象的引用next.

(2) HashMap的存，取，删除实现
1）put(Object key, Object value): 向HashMap加入key-value, 若key已经存在，则用newValue替换掉oldValue, 并返回oldValue.

put的源代码如下：
public V put(K key, V value) {
    // HashMap允许存放null键和null值。
    // 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。
    if (key == null)
        return putForNullKey(value);
    // 根据key的hashCode重新计算hash值。
    int hash = hash(key.hashCode());
    // 搜索指定hash值所对应table中的索引（table为HashMap Entry[]对象数组的实例）。
    int i = indexFor(hash, table.length);
    // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            //如果在HashMap中找到了与要插入的key相同的元素，说明要用新的value替换掉旧的value.
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    //如果执行到此处，说明要插入的key在HashMap中无这个key
    // 如果i索引处的Entry为null，表明此处还没有Entry。
    // modCount记录HashMap中修改结构的次数
    modCount++;
    // 将key、value添加到i索引处。
    addEntry(hash, key, value, i);
    return null;
}

当执行put的时候，先根据key的hashcode重新计算hash值，然后根据hash值获取这个元素在数组中的位置（即下标），如果数组该位置已经有其他元素了，那么在这个位置上的元素将以链表的形式存放。新加入的放在链表的表头，最先加入的放在链表的表尾。如果数组上该位置没有元素，则直接将新的元素放在该位置上。

2）V get(Object key)：在HashMap中获取指定key的value.
源代码如下：
public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
        e != null;
        e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}
从HashMap中get元素时，先计算key的hashcode, 然后根据hashcode找到数组中对应位置的某一元素，再通过key的equals方法在对应位置的链表中找到需要的元素。

3）remove(Object key)：删除指定的key的元素，返回值为删掉的元素。
remove过程与get类似：只是在找到指定的key之后，如果数组上的元素等于key,则将数组上的该元素置为其next元素的值；如数组上的元素不等于key, 则对链表遍历，一直到找到匹配的key或链表的结尾。

(3) HashMap的扩容
当HashMap中元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。为了提高查询的效率，就需要对HashMap的数组进行扩容，扩容时最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是HashMap的resize.

那么，什么时候需要对HashMap进行扩容呢？
当HashMap中元素的个数超过“数组的大小*loadFactor”的时候，就会进行数组扩容，loadFactor默认值为0.75, 数组的默认大小是16.那么当HashMap中的元素大小超过16 * 0.75 =12的时候（这个值就是HashMap源码中的threshold值，也叫临界值），就把数组大小扩大为16 * 2 = 32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这时一个非常消耗性能的操作。
所以我们如果已经预知HashMap中元素的格式，那么就预设元素的个数，这样能够有效的提高HashMap的性能。

HashMap包含如下几个构造器：
1）HashMap(): 构建一个初始大小为16的，负载因子为0.75的HashMap
2）HashMap(int initialCapacity): 构建一个初始大小为initialCapacity，负载因子为0.75的HashMap
3）HashMap(int initialCapacity, float loadFactor): 构建一个初始大小为initialCapacity，负载因子为loadFactor的HashMap
注：
initialCapacity：HashMap的最大容量，即为底层数组的长度
loadFactor：负载因子：散列表的实际元素数目(n)/散列表的容量(m).

HashMap总结：
1）HashMap与HashTable的区别在于HashMap是非同步的，即非线程安全的。HashMap的key和value都允许为null, 而HashTable不允许。
2) HashMap的key都是保存在Set中，因此HashMap中的对象是无序的，如果要保重Map中的对象按顺序排列，最好使用TreeMap.

这样遍历HashMap:
public void pringHashMap (HashMap hashMap)
{
    if (hashMap == null) {
        return;
    }
    Iterator iter = hashMap.entrySet().iterator();
    while (iter.hasNext) {
        Map.Entry entry = (Map.Entry)iter.next();
        System.out.println("key = " + entry.getKey());
        System.out.println("value = " + entry.getValue());
    }
}


8. TreeMap
TreeMap是支持排序的Map实现，其实现方式与HashMap完全不同。
(1) Put(Object key, Object value):
当调用put时，先判断root属性是否为Null，如是，则创建一个新的Entry对象，并赋值给root属性，如不是，则首先判断是否传入了指定的Comparable实现，
    如已传入，则基于红黑树的方式遍历，基于comparable来比较key应放在当前节点的左边还是右边，如找到相等的key, 则直接替换其value, 并返回oldValue.
    如没有传入, 则判断key是否为Null，是则抛出NPE.

综上，TreeMap是典型的红黑树的实现。

(2) get(Object)
TreeMap的查找过程就是典型的红黑树的查找过程，从根对象开始往下比较，一直找到相等的key, 并返回其value。
与put的处理方式相同，如果未传入Comparable的实现，当传入的Object为null时，则直接抛出NPE.

TreeMap是红黑树的实现
TreeMap是非线程安全的。

9. 如何选择集合类
(1) 先根据功能选择要用List, Set, Map.
List适用于允许重复元素的单个对象的集合
Set适用于不允许重复元素的单个对象的集合
Map适用于key-value结构的集合

(2) 在选择好List, Set, Map后，就要选择相应的实现类了。
ArrayList：通过位置读取元素
LinkedList：要对头尾操作，及插入到指定位置
Vector：线程安全的ArrayList
Stack：线程安全的后进先出
HashSet： 元素无序且不允许重复
TreeSet： 要排序的无重复元素
HashMap：绝大部分的key-value
TreeMap：要排序存放的key-value.