ArrayList

1.动态数组

2.线程不安全

3.存储空间连续

4.查询快，添加删除慢

• 构造方法

/** + Shared empty array instance used for default sized empty instances. We + distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when + first element is added. */private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};/** + Constructs an empty list with an initial capacity of ten. */public ArrayList() {    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

这个构造方法很简单，初始化了一个空的elementData,并没有赋予数组长度

• 元素添加

/** + Default initial capacity. */private static final int DEFAULT_CAPACITY = 10;/** + The array buffer into which the elements of the ArrayList are stored. + The capacity of the ArrayList is the length of this array buffer. Any + empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA + will be expanded to DEFAULT_CAPACITY when the first element is added. */transient Object[] elementData; // non-private to simplify nested class access/** + The size of the ArrayList (the number of elements it contains). * + @serial */private int size;/** + Appends the specified element to the end of this list. * + @param e element to be appended to this list + @return true (as specified by {@link Collection#add}) */public boolean add(E e) {    // 首先进行扩充    ensureCapacityInternal(size + 1);  // Increments modCount!!     // 将元素追加到最后    elementData[size++] = e;     return true;}// 扩充private void ensureCapacityInternal(int minCapacity) {    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}// 计算数组大小 第一次调用此处的elementData={}，所以返回值为DEFAULT_CAPACITY=10，也就是默认的数组长度是10private static int calculateCapacity(Object[] elementData, int minCapacity) {    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        return Math.max(DEFAULT_CAPACITY, minCapacity);    }    return minCapacity;}private void ensureExplicitCapacity(int minCapacity) {    modCount++;    // overflow-conscious code    if (minCapacity - elementData.length > 0) // 当加上当前元素后的集合长度（size）大于现在数组长度（elementData.length）在进行扩充        grow(minCapacity);}// 真正的扩充操作private void grow(int minCapacity) {    // overflow-conscious code    int oldCapacity = elementData.length; // 此处oldCapacity=0    int newCapacity = oldCapacity + (oldCapacity >> 1); // 此处newCapacity=0     if (newCapacity - minCapacity < 0) // 此处minCapacity=10        newCapacity = minCapacity; // 此处newCapacity=10    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); //数组拷贝}

真正的数组长度是在第一次添加的时候进行初始化的,默认为10

最主要的消耗是在扩容(数组拷贝)

当集合长度大于数组长度的时候进行扩充，扩充的标准是1.5倍[oldCapacity + (oldCapacity >> 1)]

• 查询

public E get(int index) {    rangeCheck(index);// 校验    return elementData(index);}E elementData(int index) {    return (E) elementData[index];}

Vector

1.动态数组，类似于ArrayList

2.线程安全

3.消耗大

• 构造方法

public Vector() {    this(10); // initialCapacity初始容量}

• 元素添加

/** * Appends the specified element to the end of this Vector. * * @param e element to be appended to this Vector * @return {@code true} (as specified by {@link Collection#add}) * @since 1.2 */public synchronized boolean add(E e) {    modCount++;    ensureCapacityHelper(elementCount + 1);    elementData[elementCount++] = e;    return true;}

被synchronized修饰，线程安全，但是效率较低

• 在指定位置添加元素

public void add(int index, E element) {    insertElementAt(element, index);}public synchronized void insertElementAt(E obj, int index) {    modCount++;    if (index > elementCount) {        throw new ArrayIndexOutOfBoundsException(index                                                 - " > " + elementCount);    }    ensureCapacityHelper(elementCount + 1);    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);    elementData[index] = obj;    elementCount++;}

LinkedList

1.双向链表:jdk1.7/8以后

2.插入快,查询慢

• 构造函数

/** * Constructs an empty list. */public LinkedList() {}

空的构造方法

• 元素添加

public boolean add(E e) {    linkLast(e);    return true;}void linkLast(E e) {        final Node
    
      l = last;        final Node
     
       newNode = new Node<>(l, e, null);        last = newNode;        if (l == null)            first = newNode;        else            l.next = newNode;        size++;        modCount++;    }
     
    

默认添加到链表结尾，prev指向原结尾元素，原结尾元素next指针指向新添加元素，并记录结尾元素为新添加元素。只有指针移动，并没有数组拷贝，所以插入效率较快

• 查询

public E get(int index) {    checkElementIndex(index);    return node(index).item;}Node
    
      node(int index) {    // assert isElementIndex(index);    if (index < (size >> 1)) {        Node
     
       x = first;        for (int i = 0; i < index; i++)            x = x.next;        return x;    } else {        Node
      
        x = last;        for (int i = size - 1; i > index; i--)            x = x.prev;        return x;    }}
      
     
    

查询采用二分法查找，先将数组拆分成一半，然后进行遍历。所以查询较慢。当index值接近二分之一size时，更慢。

HashMap

1.存储结构：数组+链表/数组+红黑树

2.线程不安全

• 构造方法

static final float DEFAULT_LOAD_FACTOR = 0.75f;public HashMap() {    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}

没有初始化数组，负载因子为0.75

• 添加元素

public V put(K key, V value) {    return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {    Node
    
     [] tab; Node
     
       p; int n, i;    if ((tab = table) == null || (n = tab.length) == 0) //[1]        n = (tab = resize()).length; // [2]    if ((p = tab[i = (n - 1) & hash]) == null) [// [3]        tab[i] = newNode(hash, key, value, null); // [4]    else {        Node
      
        e; K k;        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))// [5]            e = p; // [6]        else if (p instanceof TreeNode) // [7]            e = ((TreeNode
       
        )p).putTreeVal(this, tab, hash, key, value);  //[8]        else { //[9]            for (int binCount = 0; ; ++binCount) {                 if ((e = p.next) == null) { // [10]                    p.next = newNode(hash, key, value, null); // [11]                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st [12]                        treeifyBin(tab, hash); // [13]                    break;                }                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k)))) // [14]                    break;                p = e;            }        }        if (e != null) { // existing mapping for key  [15]            V oldValue = e.value;            if (!onlyIfAbsent || oldValue == null) // [16]                e.value = value;            afterNodeAccess(e);            return oldValue;        }    }    ++modCount;    if (++size > threshold) // [17]        resize();    afterNodeInsertion(evict);    return null;}
       
      
     
    

[1]判断table是否为null,长度是否为0，table用于扩充时记录扩充后的新数组

[2]进行数组扩充，将新数组赋值给tab,n为新数组的长度

[3]判断新key需要存储的数组节点是否有值

[4]如果没有值，直接存储于该节点，如果当前数组节点有值

[5]判断新key与当前存储的key是否相同

[6]记录当前存储元素到e

[7]判断当前节点是否为数节点

[8]进行树节点操作

[9]当前节点存储的key与新key不同，并且不是树形结构（链表结构）

[10]循环遍历，找到链表的尾节点

[11]将新元素追加到链表的末尾，即原尾节点的next指针指向新元素

[12]当链表的长度达到8时，转为树形结构[13]

[14]循环过程中如果发现存储的key与新key相同，则中断循环

[15]如果存在匹配的key，则替换value

[16]返回旧值

[17]能走到这里说明是新增元素，并不是更新元素，判断当前集合长度是否大于threshold（threshold=当前集合长度*0.75）,如果大于需要进行扩充

// 扩容final Node
    
     [] resize() {    Node
     
      [] oldTab = table; // [1]    int oldCap = (oldTab == null) ? 0 : oldTab.length; //[2]    int oldThr = threshold; // [3]    int newCap, newThr = 0;    if (oldCap > 0) {        if (oldCap >= MAXIMUM_CAPACITY) { // [4]            threshold = Integer.MAX_VALUE;            return oldTab;        }        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                 oldCap >= DEFAULT_INITIAL_CAPACITY) // [5]            newThr = oldThr << 1;     }    else if (oldThr > 0) // [6]        newCap = oldThr;    else { // [7]                      newCap = DEFAULT_INITIAL_CAPACITY;         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);     }    if (newThr == 0) { // [8]        float ft = (float)newCap * loadFactor;        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                  (int)ft : Integer.MAX_VALUE);    }    threshold = newThr;  // [9]    @SuppressWarnings({"rawtypes","unchecked"})        Node
      
       [] newTab = (Node
       
        [])new Node[newCap];     table = newTab;  // [10]    if (oldTab != null) {        for (int j = 0; j < oldCap; ++j) {// [11]            Node
        
          e;            if ((e = oldTab[j]) != null) {// [12]                oldTab[j] = null;                if (e.next == null)                     newTab[e.hash & (newCap - 1)] = e;                else if (e instanceof TreeNode) // [13]                    ((TreeNode
         
          )e).split(this, newTab, j, oldCap); else { // preserve order [14] Node
          
            loHead = null, loTail = null; Node
           
             hiHead = null, hiTail = null; Node
            
              next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab;}
            
           
          
         
        
       
      
     
    

[1]oldTab用来记录上次扩充的table

[2]oldCap用来记录上次扩充table的长度

[3]oldThr用来记录上次扩充的阈值

[4]如果oldCap大于等于最大值（2^30）,threshold等于2^30-1,直接返回，不在进行扩充

[5]newCap等于（oldCap*2），如果newCap小于最大值（2^30）并且oldCap大于初始值（2^4）,则newThr=oldThr*2

[6]如果oldThr大于0，则newCap等于oldThr,上次扩充的阈值

[7]如果oldCap和oldThr都不大于0，则newCap等于2^4,newThr等于2^4*0.75(首次扩充)

[8]当oldCap小于2^4的时，newThr等于0，newThr=2*oldCap*0.75

[9]threshold等于newThr，记录下次需要扩充的阈值

[10]创建新的Node数字，长度为newCap

[11]如果oldTab不为空，则遍历这个数组

[12]将原数组的元素散列到新数组中

[13]以红黑树的结构重新散列元素

[14]以链表的结构重新散列元素

• get方法，先根据key计算出对应的数组指针位置，然后遍历链表或者红黑树获取相同key的元素

Iterator
    
     
      > entryIterator = map.entrySet().iterator();    while (entryIterator.hasNext()) {        Map.Entry
      
        next = entryIterator.next();        System.out.println("key=" + next.getKey() + " value=" + next.getValue());    }
      
     
    

Iterator
    
      iterator = map.keySet().iterator();    while (iterator.hasNext()){        String key = iterator.next();        System.out.println("key=" + key + " value=" + map.get(key));    }
    

map.forEach((key,value)->{    System.out.println("key=" + key + " value=" + value);});

hashmap只能在单线程中使用，并尽量减少扩容，循环链表的时间复杂度是O(n),O(logn)

多线程场景下推荐使用ConcurrentHashMap

ConcurrentHashMap

Object put(Object key, int hash, Object value, boolean onlyIfAbsent) {    lock();    try {        int c = count;        if (c++ > threshold) // ensure capacity            rehash();        HashEntry[] tab = table;        int index = hash & (tab.length - 1);        HashEntry first = tab[index];        HashEntry e = first;        while (e != null && (e.hash != hash || !key.equals(e.key)))            e = e.next;        Object oldValue;        if (e != null) {            oldValue = e.value;            if (!onlyIfAbsent)                e.value = value;        }        else {            oldValue = null;            ++modCount;            tab[index] = new HashEntry(key, hash, first, value);            count = c; // write-volatile        }        return oldValue;    } finally {        unlock();    }}

ConcurrentHashMap之所以是线程安全的是因为在添加元素的时候先上了一个锁，操作完成在解锁。

HashSet

1.hashmap存储数据

2.不允许存储重复元素的集合

• 构造方法

public HashSet() {    map = new HashMap<>();}

• 添加元素

private static final Object PRESENT = new Object();public boolean add(E e) {    return map.put(e, PRESENT)==null;}

此方法将添加的元素e作为hashmap的key,value都是相同的PRESENT,因为hashmap的key是不允许重复的，所以相同的元素添加进来，后添加的会覆盖先添加的，这就是不允许重复的原因