集合汇总

ArrayList

注意事项

1. permits all elements, including null , ArrayList 可以加入null（空值）,并且可以是多个。
2. ArrayList是由数组来实现数据存储的
3. ArrayList基本等同于Vector，除了ArrayList是线程不安全(执行效率高)。在多线程情况下，不建议使用ArrayList。

底层操作机制源码分析

1. ArrayList中维护了一个Object类型的数组elementData

transient Object[] elementData; //transient表示瞬间,短暂的,表示该属性不会被序列号

2. 当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0，第1次添加，则扩容elementData为10，如需要再次扩容，则扩容elementData为1.5倍。
3. 如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容,则直接扩容elementData为1.5倍。

无参构造器

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {  
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  
}

add方法

public boolean add(E e) {  
    ensureCapacityInternal(size + 1);  // Increments modCount!!  
    elementData[size++] = e;  
    return true;  
}

ensureCapacityInternal —> calculateCapacity

private static final int DEFAULT_CAPACITY = 10;

private static int calculateCapacity(Object[] elementData, int minCapacity) {  
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  
        return Math.max(DEFAULT_CAPACITY, minCapacity);  
    }    return minCapacity;  
}

有参构造器

public ArrayList(int initialCapacity) {  
    if (initialCapacity > 0) {  
        this.elementData = new Object[initialCapacity]; //创建一个指定大小elementData数组
    } else if (initialCapacity == 0) {  
        this.elementData = EMPTY_ELEMENTDATA;  
    } else {  
        throw new IllegalArgumentException("Illegal Capacity: "+  
                                           initialCapacity);  
    }}

扩容流程

add

public boolean add(E e) {  
    ensureCapacityInternal(size + 1);  // Increments modCount!!  
    elementData[size++] = e;  
    return true;  
}

ensureCapacityInternal

calculateCapacity界定所需数组大小

private void ensureCapacityInternal(int minCapacity) {  
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));  
}

ensureExplicitCapacity

private void ensureExplicitCapacity(int minCapacity) {  
    modCount++;  
  
    //所需数组大于当前数组-> 扩容 
    if (minCapacity - elementData.length > 0)  
        grow(minCapacity);  
}

grow

最终调用Arrays.copyOf方法对原数组扩容

private void grow(int minCapacity) {  
	//原数组大小
    int oldCapacity = elementData.length;
    //扩容1.5倍（old + 0.5old)  
    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);  
}

并发替代方案

1. Vector（两倍扩容）

• Vector 用的不多，因为每次对添加的元素上锁，而且使用的是重量级锁synchronized是十分占用资源的，效率低下

2. Collections

List<String> list = Collections.synchronizedList(new ArrayList<>());

3. CopyOnWriteArrayList

• 写时复制技术
• 读的时候并发（多个线程操作）
• 写的时候独立，先复制相同的空间到某个区域，将其写到新区域，旧新合并，并且读新区域（每次加新内容都写到新区域，覆盖合并之前旧区域，读取新区域添加的内容）

List<String> list = new CopyOnWriteArrayList<>();

HashMap

注意事项

1. Map接口的常用实现类:HashMap、Hashtable和Properties。
2. HashMap是 Map 接口使用频率最高的实现类。
3. HashMap 是以key-val对的方式来存储数据(HashMap$Node类型)
4. key不能重复，但是值可以重复,允许使用null键和null值。
5. 如果添加相同的key，则会覆盖原来的key-val ,等同于修改.(key不会替换，val会替换)
6. 与HashSet一样，不保证映射的顺序，因为底层是以hash表的方式来存储的. (jdk8的hashMap底层数组+链表+红黑树)
7. HashMap没有实现同步，因此是线程不安全的,方法没有做同步互斥的操作,没有synchronized

底层机制及源码分析

1. HashMap底层维护了Node类型的数组table，默认为null
2. 当创建对象时，将加载因子(Ioadfactor)初始化为0.75
3. 当添加key-val时，通过key的哈希值得到在table的索引。然后判断该索引处是否有元素,如果没有元素直接添加。如果该索引处有元素，继续判断该元素的key和准备加入的key相是否等,如果相等，则直接替换val;如果不相等需要判断是树结构还是链表结构，做出相应处理。如果添加时发现容量不够，则需要扩容。
4. 第1次添加，则需要扩容table容量为16，临界值(threshold)为12 (16*0.75)
5. 以后再扩容，则需要扩容table容量为原来的2倍(32)，临界值为原来的2倍,即24,依次类推
6. 在Java8中,如果一条链表的元素个数超过 TREEIFY_THRESHOLD(默认是8)，并且table的大小>= MIN TREEIFY CAPACITY(默认64),就会进行树化(红黑树)

关于上图

1. （K,V）是一个node，实现了Map.Entry<K,V>
2. jdk7的HashMap底层实现[数组+链表]；jdk8底层实现[数组+链表+红黑树]

无参构造器

static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {  
    this.loadFactor = DEFAULT_LOAD_FACTOR; // 初始化加载因子
}

put方法

public V put(K key, V value) {  
    return putVal(hash(key), key, value, false, true);  
}

putVal方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,  
               boolean evict) {  
    Node<K,V>[] tab; Node<K,V> p; int n, i;  
     //如果底层的table 数组为null, 或者 length =0 , 就扩容到16
    if ((tab = table) == null || (n = tab.length) == 0)  
        n = (tab = resize()).length;  
    //取出hash值对应的table的索引位置的Node, 如果为null, 就直接把加入的k-v
    //创建成一个 Node ,加入该位置即可
    if ((p = tab[i = (n - 1) & hash]) == null)  
        tab[i] = newNode(hash, key, value, null);  
    else {
        Node<K,V> e; K k;  //辅助变量
        // 如果table的索引位置的key的hash相同和新的key的hash值相同，
        // 并 满足(table现有的结点的key和准备添加的key是同一个对象  || equals返回真)
        // 就认为不能加入新的k-v
        if (p.hash == hash &&  
            ((k = p.key) == key || (key != null && key.equals(k))))  
            e = p;  
        else if (p instanceof TreeNode)  //如果当前的table的已有的Node 是红黑树，就按照红黑树的方式处理
            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);
                    //加入后，判断当前链表的个数，是否已经到8个，到8个，后
                    //就调用 treeifyBin 方法进行红黑树的转换  
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);  
                    break;  
                }                if (e.hash == hash &&  //如果在循环比较过程中，发现有相同,就break,就只是替换value
                    ((k = e.key) == key || (key != null && key.equals(k))))  
                    break;  
                p = e;  
            }        }        if (e != null) {
            V oldValue = e.value;  
            if (!onlyIfAbsent || oldValue == null)  
                e.value = value;  //替换，key对应value
            afterNodeAccess(e);  
            return oldValue;  
        }   
    }   
    ++modCount;  //每增加一个Node ,就size++
    if (++size > threshold)  //如size > 临界值，就扩容
        resize();  
    afterNodeInsertion(evict);  
    return null; 
}

treeifyBin方法

//关于树化(转成红黑树)
//如果table 为null ,或者大小还没有到 64，暂时不树化，而是进行扩容.
//否则才会真正的树化 -> 剪枝
final void treeifyBin(Node<K,V>[] tab, int hash) {
     int n, index; Node<K,V> e;
     if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
       resize();
   }

并发替代方

ConcurrentHashMap

ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();