一、Java集合必备元素
集合框架：根本上是Map，Set和List的实现类集合
泛型：类型的参数化
比较器：Comparable接口和Comparator接口。Comparable接口提供了CompareTo()，Comparator接口提供了Compare()和equals()
迭代器：Iterator接口。提供了很多对集合元素进行迭代的方法，包括remove(),hasNext(),next()
二、比较器和迭代器
迭代器Iterator
iterator是为了实现对Java容器（collection）进行遍历功能的一个接口。
在iterator实现了Iterator接口后，相当于把一个Collection容器的所有对象，做成一个线性表（List），而iterator本身是一个指针，开始时位于第一个元素之前。
Iterator的三个主要方法：
1.Boolean hasNext();
判断 iterator 内是否存在下1个元素，如果存在，返回true，否则返回false。（注意，这时上面的那个指针位置不变）
2.Object next();
返回 iterator 内下1个元素，同时上面的指针向后移动一位。
故，如果不断地循环执行next()方法，就可以遍历容器内所有的元素了。
3.void remove();
删除 iterator 内指针的前1个元素，前提是至少执行过1次next();
(这个方法不建议使用，建议使用容器本身的romove 方法)
比较器Comparable和comparator
1.Comparable是一个内比较器，也就是说，可以自己跟自己进行比较。提供了一个compareTo方法用于比较，也被成为自然比较方法。**如果想使用Collections.sort方法排序某个对象容器的话，该容器必须实现Comparable接口。
2.Comparator相当于一个外比较器，也就是说，不支持自己跟自己比较。提供了compare和equals两个方法。如果一个对象没有实现Comparable接口，可以使用Comparator在主类中比较两个对象之间的值。
3.Comparator相对于Comparable来说，更个性化一些：如果实现类没有实现COmparable接口，又想对两个类进行比较，就可以使用Comparator进行自定义设置；同时，实现Comparator接口比实现Comparable接口耦合性要更弱一些，所以，从耦合性上，Comparator也比Comparable更好一些。
三、集合框架
父接口：Map接口和Collection接口。
Collection子接口：Set接口和List接口。
Set：不能包含重复的元素，无序。
List：可以包含重复的元素，有序(这里的有序指的是按照索引的升序，和值无关)。
Map接口的实现类：HashMap、TreeMap、HashTable、ConcurrentHashMap等。
Set接口的实现类：HashSet、TreeSet、LinkedHashSet等。
List接口的实现类：ArrayList、LinkedList、Stack、Vector等。
四、集合类相关特性分析
有关于集合类的讨论，主要是分析一下特性：
底层数据结构
CRUD
初始容量，扩容方式，扩容时机
是否线程安全
是否允许空，是否允许重复，是否有序
1. ArrayList&Vector&LinkedList
ArrayList
-
底层数据结构：Object数组
-
CRUD：增删时都会首先判断索引是否合法，容量是否需要改变，然后就是正常的通过检查下标对数组的增删改查。
-
初始容量，扩容方式，扩容时机：默认初始容量为10，随着元素的增加，容量也会不断自动增长。
private static final int DEFAULT_CAPACITY = 10; // 初始化的默认容量为10
public ArrayList(int initialCapacity) { // 如果初始化带参，容量为参数；否则默认初始化容量为10
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public boolean add(E e) {
ensureCapacityInternal(size + 1); //首先确定容量是否够，不够扩容
elementData[size++] = e; // 扩容后添加元素
return true;
}
private void grow(int minCapacity) { // 扩容机制，默认取1.5倍扩容和要求的容量的较大者
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity); // 这里的MAX_ARRAY_SIZE为Integer.MAX_VALUE-8,所以巨大化的话会增加到MAX_VALUE
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity); // 这里返回一个new的一个新长度的数组，不会改变原数组值
}
-
是否线程安全：非线程安全
-
是否允许空，是否允许重复，是否有序：允许为空，允许重复，有序(有下标)。
-
CRUD时的线程安全：
Fail-Fast 机制
我们知道 java.util.ArrayList 不是线程安全的，ArrayList，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。
这一策略在源码中的实现是通过 modCount 域，modCount 顾名思义就是修改次数，对ArrayList 内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的 expectedModCount。
在迭代过程中，判断 modCount 跟 expectedModCount 是否相等，如果不相等就表示已经有其他线程修改了 ArrayList。
所以在这里和大家建议，当大家遍历那些非线程安全的数据结构时，尽量使用迭代器
Vector
Vector大部分机制和ArrayList相同。下面介绍不一样的地方：
- 初始容量，扩容方式，扩容时机：初始容量与ArrayList相同，但在扩容方式上有更多的灵活性：Vector除了定义了基础容量外，还额外定义了一个扩容因子，如果扩容因子大于0，则每次扩容增加扩容因子的容量；如果未定义大小，也就是等于0，则每次扩容2倍。
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
public synchronized boolean add(E e){ // 线程安全
ensureCapacityHelper(elementCount + 1); // 首先判断大小，再添加元素
}
int newCapacity = oldCapacity + ((capacityIncrement > 0) ? // 如果扩容因子大于0，加上扩容因子的长度，否则按照2倍扩容
capacityIncrement : oldCapacity);
- 是否线程安全：vector大部分方法都是用了synchronized修饰符，所以它是线程安全的。
LinkedList
-
底层数据结构：基于链表实现
-
CRUD：常规的链表的CRUD
-
是否线程安全：非线程安全
-
是否允许空，是否允许重复，是否有序：允许为空，允许重复，有序
2. HashMap&HashTable&ConcurrentHashMap
1、相同点
初始数据结构相同：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//哈希值
final K key;//key
V value;//value
Node<K,V> next;//链表后置节点
相关参数相同：
//最大容量 2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//哈希桶，存放链表。 长度是2的N次方，或者初始化时为0.
transient Node<K,V>[] table;
//加载因子，用于计算哈希表元素数量的阈值。 threshold = 哈希桶.length * loadFactor;
final float loadFactor;
//哈希表内元素数量的阈值，当哈希表内元素数量超过阈值时，会发生扩容resize()。
int threshold;
都无序：
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; } // 根据key顺次返回，但是插入的元素的key并不是顺序的，因此遍历无序
}
hash方式本质相同：
hashcode+扰动函数
因为hashCode()是int类型，取值范围是40多亿，只要哈希函数映射的比较均匀松散，碰撞几率是很小的。
但就算原本的hashCode()取得很好，每个key的hashCode()不同，但是由于HashMap的哈希桶的长度远比hash取值范围小，默认是16，所以当对hash值以桶的长度取余，以找到存放该key的桶的下标时，由于取余是通过与操作完成的，会忽略hash值的高位。因此只有hashCode()的低位参加运算，发生不同的hash值，但是得到的index相同的情况的几率会大大增加，这种情况称之为hash碰撞。 即，碰撞率会增大。
扰动函数就是为了解决hash碰撞的。它会综合hash值高位和低位的特征，并存放在低位，因此在与运算时，相当于高低位一起参与了运算，以减少hash碰撞的概率。
//注意这里取下标 是用 哈希值 与 桶的长度-1 。 由于桶的长度是2的n次方，这么做其实是等于 一个模运算。但是效率更高
newTab[e.hash & (newCap - 1)] = e; // 通过取哈希和扰动函数使hash值更加均衡
int index = (hash & 0x7FFFFFFF) % tab.length; // hashtable的方式
int hash = spread(key.hashCode());
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
static final int HASH_BITS = 0x7fffffff; // concurrenthashmap的方式
CRUD相同
2、不同点
初始容量和扩容方式不同：
hashmap：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始容量16
newCap = oldCap << 1 // 新容量为旧容量2倍
// 保持容量为2的次方方便用与操作代替取余操作，优化速度
hashtable：
// 如果初始化是赋值，初始容量为所传入的值
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
// 默认初始化容量为11
public Hashtable() {
this(11, 0.75f);
}
int newCapacity = (oldCapacity << 1) + 1; // 扩容为2倍+1
// Hashtable之所以初始容量为11(质数)和扩容方式保证为奇数，是为了散列得更均匀，也就是减少碰撞发生的几率。
concurrentHashmap：
private static final int DEFAULT_CAPACITY = 16; // 初始容量为16
static final int MIN_TREEIFY_CAPACITY = 64; // 扩容上限为64
if ((n = tab.length) < MIN_TREEIFY_CAPACITY) // 如果当前容量小于扩容上限
tryPresize(n << 1); // 按2倍扩容
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { // 如果已经大于扩容上限
synchronized (b) { //使用synchronized同步器，将该节点处的链表转为树
进阶数据结构不同：
hashmap&&concurrenthashmap：
static final int TREEIFY_THRESHOLD = 8; // 当链表长度到达8时，转换为红黑树
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
hashtable：没有TREEIFY_THRESHOLD参数，始终为链表
转换为进阶数据结构的方式不同：
hashmap：
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
if ((e = oldTab[j]) != null) {
for (int j = 0; j < oldCap; ++j) {
oldTab[j] = null; // 释放旧数组中的对象引用
newTab[e.hash & (newCap - 1)] = e;// 创建新数组，将旧数组中的数一个一个移过去 通过扰动函数判断是保持在低位还是高位
concurrenthashmap：
private transient volatile int sizeCtl; // 该参数用来控制多线程共同参与对节点扩容
/*-1 代表table正在初始化
-N 表示有N-1个线程正在进行扩容操作
其余情况：
1、如果table未初始化，表示table需要初始化的大小。
2、如果table初始化完成，表示table的容量，默认是table大小的0.75倍*/
static final class ForwardingNode<K,V> extends Node<K,V> // 该节点会在头插的过程中最后插入，因此可以作为是否结束转移的标志
private transient volatile int transferIndex; // 表示下一个需要转移的节点下标
// 创建一个 fwd 节点，用于占位。当别的线程发现这个槽位中是 fwd 类型的节点，则跳过这个节点。
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
// CAS 修改 transferIndex，即 length - 区间值，留下剩余的区间值供后面的线程使用
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0)))
private transient volatile long baseCount; // 当前节点没有值时使用
private transient volatile int cellsBusy;
/*对于get读操作，如果当前节点有数据，还没迁移完成，此时不影响读，能够正常进行。
如果当前链表已经迁移完成，那么头节点会被设置成fwd节点，此时get线程会帮助扩容。
对于put/remove写操作，如果当前链表已经迁移完成，那么头节点会被设置成fwd节点，此时写线程会帮助扩容，如果扩容没有完成，当前链表的头节点会被锁住，所以写线程会被阻塞，直到扩容完成。
*/
空&重复不同：
hashmap：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // hash(key)允许key为null，hashcode不允许key为null，因此hashmap允许键值为null
}
hashtable：
if (value == null) { // 不允许value为null
throw new NullPointerException();
}
int hash = key.hashCode(); // 不允许key为null
ConcurrentHashmap：
if (key == null || value == null) throw new NullPointerException(); // 不允许key和value为null
基类不同：
HashMap&concurrenthashmap：派生于AbstractMap。AbstractMap中提供的基础方法更多，并且实现了多个通用的方法
HashTable：派生于Dictionary。Dictionary中只有少量的接口，并且都是abstract类型。
线程安全机制上不同：
hashmap：非线程安全，没有任何加锁操作
hashtable：线程安全，很多方法加上了synchronize关键字
public synchronized V get(Object key)
public synchronized V put(K key, V value)
// 读写都直接加上synchronize关键字
concurrenthashmap：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
// 用volatile关键字修饰的值和指针next保证了读操作不需要加锁
transient volatile Node<K,V>[] table; // 用volatile修饰Node数组是为了保证数组在扩容时对其他线程可见
synchronize(f) // 通过对节点加锁，对一些公共的参数使用cas操作来保证写和扩容的线程安全
在ConcurrentHashMap中，同步处理主要是通过Synchronized和unsafe两种方式来完成的。
在取得sizeCtl、某个位置的Node的时候，使用的都是unsafe的方法，来达到并发安全的目的
当需要在某个位置设置节点的时候，则会通过Synchronized的同步机制来锁定该位置的节点。
在数组扩容的时候，则通过处理的步长和fwd节点来达到并发安全的目的，通过设置hash值为MOVED
当把某个位置的节点复制到扩张后的table的时候，也通过Synchronized的同步机制来保证线程安全
3. HashMap&LinkedHashMap&TreeMap
LinkedHashMap的数据结构为散列表+双向链表，因此遍历LinkedHashMap可以实现按照插入顺序或者LRU的顺序遍历
TreeMap的数据结构为红黑树，并继承了Navigable接口，内部实现了Comparable接口，因此可以按照升序或者其他顺序进行打印
HashMap的打印既不按照一定的顺序也不按照插入顺序，因为是顺次打印每一个hash元素的所有链表元素，在一开始插入元素较少时，可能显示出来是升序打印，但是插入元素达到一定数量即显示无序
4.HashSet&TreeSet&LinkedHashSet
这三个Set类都基于HashMap实现，底层使用HashMap保存所有元素。
HashSet如何实现不重复：
public boolean add(E e) {
return map.put(e, PRESENT)==null; // HashSet的add操作的底层实现是map的put
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true); // 这里的OnlyIfAbsent默认是为false
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null; // 如果成功复写，返回旧值返回false，成功添加的话返回true
5. CopyOnWriteArraylist
内部持有一个ReentrantLock lock = new ReentrantLock();
底层是用volatile transient声明的数组 array
读写分离，写时复制出一个新的数组，完成插入、修改或者移除操作后将新数组赋值给array
基于以上机制，实现了高并发读，安全写，常用于读多写少的场景
6. Hashmap线程不安全可能导致的问题
数据丢失：如果两个线程要put值，key值相同，且探测到的位置为null，则两个线程都会new一个entry，那么后new的就会覆盖掉先new的值；有链表的情况也类似
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
数据重复：两个key相同的数据，如果首先判断数组中有无，然后进入之后顺序不同的话，就可能出现两个重复key都被插入的情况
死循环(JDK7)：因为是倒序扩容
扩容时取值失败&put值被覆盖：因为扩容时hashmap不会对新new的数组进行检测，所以这是插入的值可能会被覆盖；同时可能会出现指针转向新new的数组，导致查询失败的情况
put值和get值操作同时进行导致原来的值被覆盖