Collection浅析

一：Collection

二：List，有序, 可重复，有下标索引

1.ArrayList

底层动态数组，单线程，线程不安全，初始容量10，1.5倍扩容，查询效率高，增/删/改效率低

public class ArrayList<E>
{

    transient Object[] elementData; 

    private int size;
}

           

• 扩容：

private void grow(int minCapacity) {
       // overflow-conscious code
       int oldCapacity = elementData.length;
       //1.5倍扩容
       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);
   }
   private static int hugeCapacity(int minCapacity) {
       if (minCapacity < 0) // overflow
           throw new OutOfMemoryError();
       return (minCapacity > MAX_ARRAY_SIZE) ?
           Integer.MAX_VALUE :
           MAX_ARRAY_SIZE;
   }
           

2.LinkedList

双向链表实现，单线程，线程不安全，无限扩容，增删快，查询慢,

public class LinkedList<E>
{
    transient int size = 0;

    /**
     * 头节点
     */
    transient Node<E> first;

    /**
     * 尾节点
     */
    transient Node<E> last;

    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;
        }
    }
}
           

3.Vector

底层动态数组，多线程(Synchronized同步方法)，线程安全，初始容量10，2倍扩容，查询效率比LinkedList高，比ArrayList低(线程安全，消耗资源)

4.ArrayList比LinkedList查询效率高的原因:

ArrayList在内存中是连续、成块的，只需要根据首地址+偏移量即可快速计算出查找节点的内存地址，LinkedList在内存中是不连续的，每一个节点都需要2个指针分别指向上一个节点和下一个节点，只能通过遍历的方式获取元素(源码采用二分查找算法，以提高效率)

• ArrayList查找源码：

@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}
           

• LinkedList查找源码：

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);
	//二分查找，先定位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;
    }
}

           

5.ArrayList比LinkedList修改效率低的原因:

ArrayList在插入/删除元素时，该元素插入位置后的数据的内存地址要依次向后移动，而LinkedList是双向链表最多只会影响到插入/删除元素前后2个位置节点的信息

• LinkedList插入/删除源码：

/**
 * 节点尾部插入元素
 */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
}

/**
 * 删除元素
 */
E unlink(Node<E> x) {

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    return element;
}

           

• ArrayList插入/删除源码：

// ensureCapacityInternal() 方法内部会调用 System.arraycopy()
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  
    elementData[size++] = e;
    return true;
}

public void add(int index, E element) {
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

public E remove(int index) {
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; 

    return oldValue;
}

           

6.LinkedList比ArrayList占用更多的内存:

ArrayList每个节点存储的是实际数据内容，而LinkedList每个节点存储的是实际数据及前后节点的内存地址

7.扩容的目的:

减少链表的长度，元素分配更均匀

8.ArrayList是线程不安全的，请编写一个不安全的案例，并给出解决方案？

• 故障现象
• 导致原因
• 解决方案
• 优化建议

三：Set，无序, 不重复，无下标索引

1.HashSet

底层是HashMap，数组+链表结构，初始容量16，加载因子0.75，扩容1倍，存储元素时先计算该元素的HashCode值，根据HashCode值和集合的长度计算出该元素在集合中的下标，如果该下标处没有元素就直接存储，如果有通过equals方法比较是否是同一个对象，如果是不存储，如果不是通过链接的方式在该下标处存储元素

2.LinkedHashSet

HashSet的子类，比HashSet多了一个存储顺序的维护

3.TreeSet

• 底层是TreeMap，根据元素的compareTo()方法或者是根据指定的比较器对象的compare()来决定元素的存储的位置，数据结构使用树的结构，
• 存储到TreeSet的元素，要可比较的，要么元素本身是实现了Comparable接口的，要么为这个元素的类型单独指定一个比较器，这个比较器实现了Comparator接口
• 元素如果实现了Comparable接口，重写了compareTo()方法，那么按照逻辑角度，应该也重写equals方法，使得e1.compareTo(e2)==0，e1.equals(e2)==true保持一致，那么equals重写，往往hashcode方法也要重写

四：Map

1.HashMap

• 底层数组+链表结构，线程不安全，entry类型数组，初始容量16，加载因子0.75，扩容1倍，key、value允许为null值
• 存储过程：计算key的HashCode值，根据HashCode值计算出该元素在entry数组中对应的索引下标，如果该下标处没有元素就直接存储，如果有通过equal方法比较，如果相同就不存储，如果不相同就以链接的形式在该下标处存储元素
• 扩容：可能造成无效扩容，在插入元素后再判断是否需要扩容(有可能插入元素后扩容了，但不再有元素进来)
• index计算： hash & (tab.length – 1)

• 1.7和1.8区别

  1.7的数据结构为：动态数组+单链表，1.8的数据结构为：动态数组+(链表+红黑树)，链表长度>8转换为红黑树

2.LinkedHashMap

• HashMap的子类，用一个链表维护了元素的存储顺序，可以按照存储顺序遍历取出存储的元素

3.TreeMap

• 底层实现：红黑树

  线程非安全，不允许null，key不可以重复，value允许重复

• key类型必须是可排序的，

  （1）key类型本身或它的父类实现了Comparable接口，自然排序，实现了int compareTo(T t)；

  （2）为key类型实现了一个Comparator比较器，定制排序，实现了int compare(T t1,T t2)

• key调用compare或compareTo方法比较，决定存储的位置

4.ConcurrentHashMap

• JDK1.7 实现
• 数据结构：分段数组+链表
• 底层实现：

  分段锁机制

  ，Segment+ReentrantLock+HashEntyy

  将Map分为N个Segment，线程安全，但效率提升N倍，默认16倍

• 核心静态内部类：Segment、HashEntry

  1）Segment继承ReentrantLock充当锁的角色

  2）HashEntry封装表的键值对

• JDK1.8 实现
• 数据结构：接近HashMap的结构，动态数组+链表
• 底层实现：synchronized+cas+HashEntry+红黑树

• put 操作：

  1）如果没有初始化，就调用initTable()进行初始化

  2）如果没有Hash冲突，就直接cas插入

  3）如果存在hash冲突，synchronized加锁保证线程安全(锁住链表或红黑树的头节点)，有2种情况，一种是链表形式直接遍历尾端插入，一种是红黑树结构插入

  4）如果链表的长度>8，就先转换为红黑树

  5）添加成功，就调用addCount()方法，统计size()，并检查是否需要扩容

• get 操作：

  1）计算hash值，定位到在数组中的下标，如果是下标处链表的首节点就返回

  2）如果遇到扩容，会调用标志正在扩容节点ForwardingNode的find方法，查找该节点，匹配就返回

  3）以上都不符合，遍历链表，匹配就返回，不匹配返回null

• 区别：

• 锁的粒度

  1.7锁的粒度是segment，包含多个Hashentry，1.8只锁一个HashEntry，首节点

• 链表遍历效率

  1.8使用红黑树优化链表，当链表的长度>8，就转换为红黑树，链表的查询效率提高了

public V put(K key, V value) {
    return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode()); //两次hash，减少hash冲突，可以均匀分布
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) { //对这个table进行迭代
        Node<K,V> f; int n, i, fh;
        //这里就是上面构造方法没有进行初始化，在这里进行判断，为null就调用initTable进行初始化，属于懒汉模式初始化
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {//如果i位置没有数据，就直接无锁插入
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)//如果在进行扩容，则先进行扩容操作
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            //如果以上条件都不满足，那就要进行加锁操作，也就是存在hash冲突，锁住链表或者红黑树的头结点
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) { //表示该节点是链表结构
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            //这里涉及到相同的key进行put就会覆盖原先的value
                            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;
                            }
                        }
                    }
                    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;
                        }
                    }
                }
            }
            if (binCount != 0) { //如果链表的长度大于8时就会进行红黑树的转换
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);//统计size，并且检查是否需要扩容
    return null;
}
           

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode()); //计算两次hash
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {//读取首节点的Node元素
        if ((eh = e.hash) == h) { //如果该节点就是首节点就返回
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        //hash值为负值表示正在扩容，这个时候查的是ForwardingNode的find方法来定位到nextTable来
        //查找，查找到就返回
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {//既不是首节点也不是ForwardingNode，那就往下遍历
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}
           

5.HashTable

• 底层实现：数组+链表，线程安全(相比ConcurrentHashMap效率低，锁住整张表)，key和value不能为null，
• 扩容：初始容量11，2倍+1扩容
• index计算：(hash & 0x7FFFFFFF) % tab.length

6.HashTable与HashMap的区别

• 线程安全性

  HashTable线程安全(synchronized，1.5之后提供了ConcurrentHashMap，它是HashTable的替代，比HashTable扩展性更好)，HashMap线程不安全

• null值

  HashTable中key和value都不允许出现null值，HashMap中null可以作为主键(只有一个)，当使用get()方法返回null值，不一定表示该HashMap没有该值，需要用containsKey()方法来判断

• 性能

  当线程场景下，HashMap性能好于HashTable

• 哈希值的使用

  HashTable直接使用对象的HashCode值，HashMap重新计算

• 初始化大小和扩容方式不同，

  HashTable数组默认为11，old*2+1扩容，加载因子0.75，HashMap默认数组大小为16，2倍扩容，加载因子0.75