集合框架

概览

参考这里

List

• ArrayList 实现了RandomAccess，可随机读取。可指定初始空间大小，默认为10，超过此空间，数组空间增加以前的一半

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
        
  //数组的定义
  transient Object[] elementData; 
  //初始化 默认大小 是10
  private static final int DEFAULT_CAPACITY = 10;
  //有意思的是  也定义了最大值
  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  
  //初始化
   public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
        
          //实现原理是 创建一个Object类型的数组
            this.elementData = new Object[initialCapacity];
            
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
        }
    }
   
    

transient 一个对象只要实现了Serilizable接口，这个对象就可以被序列化,某个属性不需要序列化，就可以用这个关键字

image

• 扩容

      private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        
        //扩容大小是右移一位，比如初始化是10 即1010(10)右移一位变成0101(5)
        //新的容量=old容量+old/2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 然后把原来的数据复制到
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

• 其他方法比较简单，这里不写了。

• LinkedList：通过实现AbstractSequentialList来实现随机的索引读取。每个节点是Node,存有两个指针Next，Prev,是个双向链表。初始size=0，动态增加，不需预先分配空间，且实现了queue接口，可以查看首（first）尾(last)元素.

public class LinkedList<E> extends AbstractSequentialList<E>
//实现了deque接口
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
//初始化为0
    transient int size = 0;

• 比较一下两个

0	ArrayList	LinkedList
算法	数组	链表
优势	随机读取效率高	头尾节点插入、删除效率高
内存占用	需要预留空间和扩容，内存占用大	内存占用小
遍历	效率接近	需要用iterator遍历

• 获取线程安全的list
  • 普通版

/**
 * 获取一个线程安全的LinkedList
 */
List synLinkedList = Collections.synchronizedList(new LinkedList());
/**
 * 获取一个线程安全的ArrayList
 */
List synArrayList = Collections.synchronizedList(new ArrayList());

或者

• Vector (ArrayList线程安全低配版 )
  • 效率比arrayList差，一般不用，大部分方法都用synchronized修饰
• CopyOnWriteArrayList (ArrayList线程安全高配版 )

  public class CopyOnWriteArrayList<E>
     implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

    /** 加锁 */
    final transient ReentrantLock lock = new ReentrantLock();

    /** 数组定义 用 volatile */
    private transient volatile Object[] array;

• 插入

   public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        //加锁
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            
            //先复制一个新的数组 然后插入到新的数组中
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            
            return true;
        } finally {
            lock.unlock();
        }
    }

• 对比
  • 读没有加锁，所以不是绝对线程安全的。类似读写分离
  • 读性能比vector高，所以适合读多写少的场景。

Map

HashMap

• 理想状态的hash算法是哈希表中的元素都是正常分布(不存在冲突)的,get,put操作时间复杂度都是O(1)
• K,V都可为null，所以get() 为null,不能判断k为null，有可能是v为null,所以需要用containskey判断
• 支持fail-fast
  • 当集合迭代时，其他线程修改了该线程，会抛出这个错误。
• 迭代器 Iterator
• 结构图
  • HashMap采用数组链表的结构<拉链法>来处理冲突，将散列到同一位置的数据头插法插入一个链表。
  • 在java8中，当链表的长度大于8的时候将这个链表重构成红黑树。

image

• 两个影响性能的重要因素。初始容量initial capacity:16和负载因子local Factor:0.75：两个影响性能的重要因素。

    /** 
     * 默认初始容量16，指的是桶的数量(数组的长度)，必须是2的N次幂
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //  16

    /**
     * 最大的容量，可以在构造的时候传入参数，但是必需是小于2的30次幂=1073741824
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 默认的负载因子0.75，即使用容量超过初始容量*0.75必须扩容
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 链表转红黑树的阈值，大于这个值转换
     */
    static final int TREEIFY_THRESHOLD = 8; 
    /**
     * 红黑树转链表的阈值，小于这个值转换
     */
    static final int UNTREEIFY_THRESHOLD = 6;
   

• hashMap结构

  /**
   *  哈希表，每个节点是Node<K,V>结构，容量总是保持2的N次幂。
   */
transient Node<K,V>[] table;

• 节点 Node<K,V>

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
    /**
     * 1 这个Next仍然是个Node 这种结构决定了头插法来链接链表的节点。
     * 2 也说明了get()时它连K，V一起存**储的，碰撞的时候hash值相同，我们也可以比较K的值来确定要返回的Value
     */
        Node<K,V> next;
        ……
    
}

• 扩容

final Node<K,V>[] resize() {
       ……
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {//容量达到最大值
            //把扩展阈值修改为最大，这样以后就不能扩容了
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                     //容量翻倍
                newThr = oldThr << 1; 
        }
        ……

• get()

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 每次都需要一直检查 first node
            if (first.hash == hash && 
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) { //如果不是 则往下找
                if (first instanceof TreeNode) //如果是树形Node，则调用TreeNode的get方法
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {//否则直接查询Next比较Key值。
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

hashTable

• 线程安全

• K,V都不允许为null

• 迭代器：Enumeration（枚举类）

• 定义

  //类型
  private transient Entry<?,?>[] table;
  //Entry<K,V>定义
   private static class Entry<K,V> implements Map.Entry<K,V> {
   // hashMap是node<>  但是结构都是一样的
   static class Node<K,V> implements Map.Entry<K,V> {

• 初始化

//初始容量：11，负载因子：0.75f
public Hashtable() {
        this(11, 0.75f);
    }

• get()

  //是线程安全的
    public synchronized V get(Object key) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        //索引位置计算
        int index = (hash & 0x7FFFFFFF) % tab.length;
        //实现方式和hashMap有很大的不同
        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }

ConcurrentHashMap

• HashMap的线程安全版

 static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        //与hashMap不同的地方  用了volatile修饰 
        //保证了val被修改时线程可见性,无需加锁便能实现线程安全的读操作。
        volatile V val;
        volatile Node<K,V> next;

• 比Hashtable更高效的并发性能

  • 使用分离锁的思路解决并发性能，其将Entry数组拆分至16个Segment中，以哈希算法决定Entry应该存储在哪个Segment。在写操作时只对一个Segment加锁（hashMap对整个Entry加锁），大幅提升了并发写的性能。

• 缺点 :不能保证读操作的绝对 一致性

  • 如果写操作在创建一个Entry,在写操作完成之前(会加锁)，读操作不一定可以读到这个Entry。

对比	HashMap	Hashtable	Hashtable
线程安全	否	是	是(不能保证数据绝对一致)
性能	最好	最差	中间

TreeMap

• TreeMap是基于红黑树实现的Map结构，其Entry类拥有到左/右叶子节点和父节点的引用，同时还记录了自己的颜色

  static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;    

• 适合需要对key进行有序操作的场景。
  • 提供了一系列方便的功能，比如获取以升序或降序排列的KeySet()、获取在指定key()之前/之后的key()等等

TreeSet

• 基于TreeMap构造的Set，基本操作都是TreeMap的操作

HashSet 基本上就是用了hashTable

• 结构

 public HashSet() {
       //直接就用了HashMap  真省事
        map = new HashMap<>();
    }

• add() 就是做了不能存储重复value的操作

 // Dummy value to associate with an Object in the backing Map 这个是不会重复的
    private static final Object PRESENT = new Object();

  public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

• 存储单值选hashSet（前提是数据不重复，否则就会丢失数据）查找速度理想是O(1)

结构类似 只是简单封装

graph LR
HashMap-->HashSet

graph LR
TreeMap-->HashSet