Java集合深入详解

之前对于Java的集合类仅仅只是一笔带过，现在我打算仔细地介绍一遍

ArrayList

实现原理

ArrayList是基于数组实现的，是一个动态数组，其容量能自动增长，默认容量是10。当容量不足时，就设置新的容量为旧的容量的1.5倍加1，如果还不够就直接令新容量设置为传入的参数。容量增加的方法是用System.arraycopy(oldArrays,old_start_index,newArrays,new_start_index,oldArrays.length)方法把原来的元素拷贝进一个新数组。

线程安全

ArrayList是非线程安全的，只能用在单线程环境下，多线程环境下可以考虑用Collections.synchronizedList(List list)函数返回一个线程安全的ArrayList类，也可以使用concurrent并发包下的CopyOnWriteArrayList类。

不安全性

ArrayList在添加一个元素的时候，它可能会有两步来完成：1. 在 Items[Size] 的位置存放此元素；2. 增大 Size 的值。在单线程运行的情况下，如果 Size = 0，添加一个元素后，此元素在位置 0，而且 Size=1；而如果是在多线程情况下，比如有两个线程，线程 A 先将元素存放在位置 0。但是此时 CPU 调度线程A暂停，线程 B 得到运行的机会。线程B也向此 ArrayList 添加元素，因为此时 Size 仍然等于 0 （注意哦，我们假设的是添加一个元素是要两个步骤哦，而线程A仅仅完成了步骤1），所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行，都增加 Size 的值。那好，我们来看看 ArrayList 的情况，元素实际上只有一个，存放在位置 0，而 Size 却等于 2。这就是“线程不安全”了

优势

因为基于数组，有下标索引，所以便于遍历查找

局限性

ArrayList不适合频繁插入或删除元素，因为这样会大量地移动元素
不是线程安全，如果两个线程同时插入，会导致size不一致情况

备注

ArrayList中允许元素为null

CopyOnWriteArrayList

实现原理

写时加锁，当添加一个元素的时候，将原来的容器进行copy，复制出一个新的容器，然后在新的容器里面写，写完之后再将原容器的引用指向新的容器，而读的时候是读旧容器的数据，所以可以进行并发的读，但这是一种共享锁的策略。

使用场景

CopyOnWriteArrayList适合使用在读操作远远大于写操作的场景里，比如缓存。

LinkedList

实现原理

LinkedList是基于双向循环链表实现的，且头结点中不存放数据，除了可以当做链表来操作外，它还可以当做栈、队列和双端队列来使用。

源码分析

//元素结点
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

//获取元素方法
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
//通过一次二分法的遍历
Node<E> node(int index) {
    // assert isElementIndex(index);
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
//源码中先将index与长度size的一半比较，如果index<size/2，就只从位置0往后遍历到位置index处，而如果index>size/2，就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历，从而提高一定的效率（实际上效率还是很低）。

线程安全

LinkedList是非线程安全的，只在单线程下适合使用。

不安全性

进队列操作

获取链表的链尾【断点】
插入元素
把链尾指向当前元素

出队列操作

获取头结点【断点】
获取头结点的下一个节结点
把头结点指针指向下一个节点
然后把之前的头结点置null，next指针也置null

多线程下，进队列操作会出现元素覆盖的问题
出队列会出现头结点没有后续元素，其实是因为头结点被置null了

优势

因为基于链表，所以方便增加和删除元素，也方便获取第一和最后元素

LinkedList实现了Queue接口，因此也可以作为栈、队列和双端队列来使用

局限性

不适合遍历查找

备注

LinkedList实现了Serializable接口，因此它支持序列化，能够通过序列化传输，实现了Cloneable接口，能被克隆。

LinkedList中允许元素为null

ArrayDeque

实现原理

ArrayDeque继承于AbstractCollection，底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组（circular array），也就是说数组的任何一点都可能被看作起点或者终点

线程安全

ArrayDeque是非线程安全的

方法

Queue是一个接口，当需要使用栈和队列时首选ArrayDeque（双端队列）了，次选是LinkedList，不推荐使用Stack

下表列出了Deque与Queue相对应的接口：

Queue Method	Equivalent Deque Method	说明
`add(e)`	`addLast(e)`	向队尾插入元素，失败则抛出异常
`offer(e)`	`offerLast(e)`	向队尾插入元素，失败则返回`false`
`remove()`	`removeFirst()`	获取并删除队首元素，失败则抛出异常
`poll()`	`pollFirst()`	获取并删除队首元素，失败则返回`null`
`element()`	`getFirst()`	获取但不删除队首元素，失败则抛出异常
`peek()`	`peekFirst()`	获取但不删除队首元素，失败则返回`null`

下表列出了Deque与Stack对应的接口：

Stack Method	Equivalent Deque Method	说明
`push(e)`	`addFirst(e)`	向栈顶插入元素，失败则抛出异常
无	`offerFirst(e)`	向栈顶插入元素，失败则返回`false`
`pop()`	`removeFirst()`	获取并删除栈顶元素，失败则抛出异常
无	`pollFirst()`	获取并删除栈顶元素，失败则返回`null`
`peek()`	`peekFirst()`	获取但不删除栈顶元素，失败则抛出异常
无	`peekFirst()`	获取但不删除栈顶元素，失败则返回`null`

备注

ArrayDeque不允许放入null元素

参考路径

https://zhuanlan.zhihu.com/p/24752167?refer=dreawer

Vector

实现原理

Vector也是基于数组实现的，是一个动态数组，其容量能自动增长。总体上和ArrayList一样，只是很多方法都加入了synchronized同步语句，来保证线程安全

线程安全

Vector是线程安全的

优势

因为很多方法加了synchronized，所以可以用于多线程环境

和ArrayList一样便于遍历查找

局限

和ArrayList一样，不适合频繁插入或删除元素

备注

Vector中允许元素为nul

HashSet

实现原理

HashSet是对HashMap的简单包装，对HashSet的函数调用都会转换成合适的HashMap方法

TreeSet

实现原理

TreeSet是对TreeMap的简单包装，对TreeSet的函数调用都会转换成合适的TreeMap方法

LinkedHashSet

实现原理

LinkedHashSet是对LinkedHashMap的简单包装，对LinkedHashSet的函数调用都会转换成合适的LinkedHashMap方法

HashMap

实现原理

HashMap是基于数组和链表实现的，每一个元素是一个key-value对，其内部通过单链表解决冲突问题，容量不足（超过了阀值）时，创建原来HashMap两倍大小的数组。默认初始容量是16，默认加载因子为0.75 。

HashMap的key做hash算法，并将hash值映射到内存地址（数组索引），直接取得key对应的value

HashMap把新元素放在链表的队首

源码分析

//数据结点
static class Node<K,V> implements Map.Entry<K,V> {
	final int hash;
	final K key;
	V value;
	Node<K,V> next;
	Node(int hash, K key, V value, Node<K,V> next) {
    	this.hash = hash;
    	this.key = key;
    	this.value = value;
    	this.next = next;
	}
}
//储存元素
public V put(K key, V value) {
    // 如果table为null，inflate 该table
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 当key为null，调用putForNullKey方法，保存null与table第一个位置中，这是HashMap允许为null的原因
    if (key == null)
        return putForNullKey(value);
    // 根据key的hashcode进行计算hash值。
    int hash = hash(key);
    // 根据指定hash值在找到对应的table中的索引。 
    int i = indexFor(hash, table.length);
    // 若 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 判断该条链上是否有hash值相同的(key相同)
        // 若存在相同，则直接覆盖value，返回旧value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    // 如果i索引处的Entry为null，表明此处还没有Entry。
    modCount++;
    // 将key、value添加到i索引处。
    addEntry(hash, key, value, i);
    return null;
}
//当我们向HashMap中put元素的时候，先根据key的hashCode的值计算hash值，根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。addEntry(hash, key, value, i)方法根据计算出的hash值，将key-value对放在数组table的i索引处。
void addEntry(int hash, K key, V value, int bucketIndex) {
 // 如果 Map 中的 key-value 对的数量超过了极限
    if ((size >= threshold) && (null!=table[bucketIndex])){
        // 把 table 对象的长度扩充到原来的2倍。 
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}
    
void createEntry(int hash, K key, V value, int bucketIndex) {
    // 根据bucketIndex 获取对应的 Entry  
    Entry<K,V> e = table[bucketIndex];
    // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry 
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}
//获取
public V get(Object key) {  
    // 如果key = null时，返回null对应的value值。
    if (key == null)  
        return getForNullKey(); 
    // 根据key的hashcode值做hash获取对应的值
    int hash = hash(key.hashCode()); 
    // 根据指定hash值在找到对应的table中的索引，并根据索引获取该处的Entry，通过循环不断遍历 e 元素的下一个元素。
    for (Entry<K,V> e = table[indexFor(hash, table.length)];  e != null;  e = e.next) {  
        Object k;  
        // 判断e元素的hash与hash是否相等，如果相等并且e元素与key相等则返回e的原则的value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
            return e.value;  
    }  
    // 如果指定hash值在找到对应的table中的索引，并根据索引获取该处的Entry的为null，则返回null。
    return null;  
} 
//从HashMap中get元素时，首先计算key的hashCode，通过IndexFor(hash,table.length)找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。

线程安全

HashMap是非线程安全的

HashMap 在并发时可能出现的问题主要是两方面,首先如果多个线程同时使用put方法添加元素，而且假设正好存在两个 put 的 key 发生了碰撞(根据 hash 值计算的 bucket 一样)，那么根据 HashMap 的实现，这两个 key 会添加到数组的同一个位置，这样最终就会发生其中一个线程的 put 的数据被覆盖。第二就是如果多个线程同时检测到元素个数超过数组大小* loadFactor ，这样就会发生多个线程同时对 Node 数组进行扩容，都在重新计算元素位置以及复制数据，但是最终只有一个线程扩容后的数组会赋给 table，也就是说其他线程的都会丢失，并且各自线程 put 的数据也丢失。

可以以下三种方法来实现线程安全

1
2
3

Map<String, String> hashtable = new Hashtable<>();
Map<String, String> synchronizedHashMap = Collections.synchronizedMap(new HashMap<String, String>());
Map<String, String> concurrentHashMap = new ConcurrentHashMap<>();

1.8实现

采用数组+链表+红黑树，如果链表长度超过8，则改为红黑树

先判断当前位置有没有值，没有则新建node插入
如果有值，则判断是否为同一个key，若是则更新，如不是再判断是否是红黑树
若还不是同一个key，遍历链表更新节点或在链表最后插入新节点

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

备注

key最好是不可变的final对象，因为如果key可变，那下次获取键值对的时候，key的hashcode会和之前的不一样，而导致无法取出，如果一定要用可变对象的话，那就要重写这个对象的hashcode方法

HashMap可以key和value均可以为null

Hashtable

实现原理

HashMap和Hashtable采用的是相同的存储机制，因此两者的实现基本一致。

与HashMap区别

HashMap可以key和value均可以为null，而HashTable则不可以。Hashtable不允许null的值，Hashtable的key为null的时候，HashTable调用put方法时，直接抛出NullPointerException。其它细微的差别还有，比如初始化Entry数组的大小等等。
Hashtable是线程安全的，内部的方法基本都是synchronized。HashMap则不是线程安全的。
Hashtable中的hash数组默认是11，增加方式old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。
哈希值的使用不同，HashTable直接使用对象的hashCode，而HashMap重新实现哈hash方法
HashMap继承的是AbstractMap，Hashtable继承的是Dictionary

线程安全

Hashtable是线程安全的，因为方法上加了synchronized

局限

因为加了synchronized同步锁，获得的是对象锁，所以没有得到锁的其他线程会一直等待，影响效率

备注

Hashtable不能有null值

ConcurrentHashMap

实现原理

1.7实现

ConcurrentHashMap是使用了分段锁技术来保证线程安全的，底层采用数组+链表+红黑树的存储结构。分段锁技术：它相当于把一个数组分成好几段，每一段是一个 segment ，里面包含了一小段的hash table。segment继承了ReentrantLock，所以有自己的锁。当一个线程占用锁来访问其中一段数据的时候，其他段的数据也能被其他线程访问。但是如果有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。这里的按顺序是为了避免死锁。

在ConcurrentHashMap内部，段数组是final的，并且其成员变量实际上也是final的，但是，仅仅是将数组声明为final的并不保证数组成员也是final的，这需要实现上的保证。这可以确保不会出现死锁，因为获得锁的顺序是固定的。

如果不是final，则有可能一段数据里包含了另一段数据的引用

Segment继承ReentrantLock用来充当锁的角色，每个 Segment 对象守护每个散列映射表的若干个桶。

HashEntry 用来封装映射表的键 / 值对；

每个桶是由若干个 HashEntry 对象链接起来的链表。

源码分析

static final class HashEntry<K,V> {  
     final K key;  
     final int hash;  
     volatile V value;    //为了确保读操作能够看到最新的值，将value设置成volatile，这避免了加锁
     final HashEntry<K,V> next;  
}

1.8实现

1.8中放弃了Segment臃肿的设计，取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现，底层依然采用数组+链表+红黑树的存储结构。当一个链表中的元素达到8个时，会调用treeifyBin()方法把链表结构转化成红黑树结构

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
}

static final class TreeNode<K,V> extends Node<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;
}

put实现

当执行put方法插入数据时，根据key的hash值，在Node数组中找到相应的位置，实现如下：

1、如果相应位置的Node还未初始化，则通过CAS插入相应的数据；

else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
    if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
        break;                   // no lock when adding to empty bin
}

2、如果相应位置的Node不为空，且当前该节点不处于移动状态，则对该节点加synchronized锁，如果该节点的hash不小于0，则遍历链表更新节点或插入新节点；

if (fh >= 0) {
    binCount = 1;
    for (Node<K,V> e = f;; ++binCount) {
        K ek;
        if (e.hash == hash &&
            ((ek = e.key) == key ||
             (ek != null && key.equals(ek)))) {
            oldVal = e.val;
            if (!onlyIfAbsent)
                e.val = value;
            break;
        }
        Node<K,V> pred = e;
        if ((e = e.next) == null) {
            pred.next = new Node<K,V>(hash, key, value, null);
            break;
        }
    }
}

3、如果该节点是TreeBin类型的节点，说明是红黑树结构，则通过putTreeVal方法往红黑树中插入节点；

else if (f instanceof TreeBin) {
    Node<K,V> p;
    binCount = 2;
    if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
        oldVal = p.val;
        if (!onlyIfAbsent)
            p.val = value;
    }
}

4、如果binCount不为0，说明put操作对数据产生了影响，如果当前链表的个数达到8个，则通过treeifyBin方法转化为红黑树，如果oldVal不为空，说明是一次更新操作，没有对元素个数产生影响，则直接返回旧值；

if (binCount != 0) {
    if (binCount >= TREEIFY_THRESHOLD)
        treeifyBin(tab, i);
    if (oldVal != null)
        return oldVal;
    break;
}

5、如果插入的是一个新节点，则执行addCount()方法尝试更新元素个数baseCount；

区别

与Hashtable的区别

Hashtable的synchronized是针对整张Hash表的，即每次锁住整张表让线程独占

ConcurrentHashMap分段锁是针对一部分数据的，segment数组里的每个元素单独加锁

与Collections.synchronizedMap()的区别

Collections.synchronizedMap()和Hashtable一样，实现上在调用map所有方法时，都对整个map进行同步，而ConcurrentHashMap的实现却更加精细，它对map中的所有桶加了锁。

TreeMap

实现原理

TreeMap实现了SortedMap接口，底层通过红黑树实现，也就是说会按照key的大小顺序对Map中的元素进行排序，key大小的评判可以通过其本身的自然顺序，也可以通过构造时传入的比较器（Comparator）

get(Object key)方法根据指定的key值返回对应的value，该方法调用了getEntry(Object key)得到相应的entry，然后返回entry.value。因此getEntry()是算法的核心。算法思想是根据key的自然顺序（或者比较器顺序）对二叉查找树进行查找，直到找到满足k.compareTo(p.key) == 0的entry。

put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找，看是否包含该元组，如果已经包含则直接返回，查找过程类似于getEntry()方法；如果没有找到则会在红黑树中插入新的entry，如果插入之后破坏了红黑树的约束条件，还需要进行调整（旋转，改变某些节点的颜色）。

线程安全

TreeMap是非线程安全的

1	SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

红黑树

红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一倍。具体来说，红黑树是满足如下条件的二叉查找树（binary search tree）：

每个节点要么是红色，要么是黑色。
根节点必须是黑色
红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。
每个空叶子节点必须是黑色的；

LinkedHashMap

实现原理

LinkedHashMap是HashMap的直接子类，二者唯一的区别是LinkedHashMap在HashMap的基础上，采用双向链表的形式将所有entry连接起来，这样是为保证元素的迭代顺序跟插入顺序相同。

优势

迭代LinkedHashMap时不需要像HashMap那样遍历整个table，而只需要直接遍历header指向的双向链表即可

该双向链表的迭代顺序就是entry的插入顺序

备注

LinkedHashMap允许null值

本文参考：

https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/0-Introduction.md

http://www.jianshu.com/u/90ab66c248e6