摘要：包提供了兩種比常用很多，原因是查找更容易封裝了一個數(shù)組數(shù)組的初始化封裝一個空數(shù)組封裝一個大小為的數(shù)組數(shù)組如何實現(xiàn)擴容都需要先進行擴容檢查，類似，對象調(diào)用方法，要進行對象判空，操作之前要進行，線程檢查擴容檢查增加的大小與數(shù)組比較計算數(shù)組擴容的

java.util包提供了兩種

ArrayList
LinkedList

ArrayList比LinkedList常用很多，原因是:
ArrayList查找更容易

ArrayList封裝了一個數(shù)組Object[]

數(shù)組的初始化

ArrayList array = new ArrayList();

封裝一個空數(shù)組, {}

ArrayList array = new ArrayList(10);

封裝一個大小為10的數(shù)組 new Object[10];

數(shù)組如何實現(xiàn)擴容

ArrayList.add/addAll都需要先進行擴容檢查，
類似，

 對象調(diào)用方法，要進行對象判空，
 UI操作之前要進行，線程檢查
 

擴容檢查: size+增加的大小 與 數(shù)組.length 比較
計算數(shù)組擴容的數(shù)組長度：

??首先，擴容至原數(shù)組大小的一倍，size+增加的大 小與其比較：
???????如果大于，擴容至原數(shù)組大小的一倍
???????如果小于，擴容至size+增加的大小;

private void grow(int minCapacity) {
       // overflow-conscious code
       int oldCapacity = elementData.length;
       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);
   }

擴容使用的是: Array.copyof(array, newLen)

removeAll如何實現(xiàn)

與remove()不同，remove使用System.copy完成數(shù)組的 部分移動

而removeAll,使用的算法：

ArrayList array1 = new ArrayList();
array1.addAll({0,3,5,7,3,6});
int[] array2 = {3,5,4};
array1.removeAll(array2);

首先，遍歷array1中每個元素，若元素 不在array2內(nèi)，將計數(shù)位置的值設(shè)置為元素的值并將計 數(shù)+1;

遍歷完成后，計數(shù)為數(shù)組剩余元素的個 數(shù)，將計數(shù)之后的元素清空.

算法詳細:

     0,3,5,7,3,6 ;

     遍歷之后，計數(shù)為2，數(shù)組為0,7,6,7,3,6;

     清空之后，0,7,6,null,null,null;

trimToSize()

數(shù)組擴容后即使刪除元素，數(shù)組的length也不會該改變，

意味著即使刪除了某些元素數(shù)組占用的內(nèi)存大小不會改變;

數(shù)組只會不斷的增大,且出現(xiàn)大量null的元素.

trimToSize()方法用于改變數(shù)組的length,將為null的元素釋放掉，等待GC

這也是防止內(nèi)存浪費的一種方式，當ArrayList經(jīng)歷了多次刪除操作之后，使用trimToSize(),避免內(nèi)存浪費.

trimToSize()使用Array.copyof()來改變數(shù)組的length

總結(jié)

ArrayList本質(zhì)上維護了一個數(shù)組，也就意味者它具有數(shù)組的優(yōu)缺點：增刪難，查找易

Node的數(shù)據(jù)結(jié)構(gòu)

Node {
    E element;
    Node prev;
    Node next;
}

基本結(jié)構(gòu)

    Node first, last

Linked是雙向鏈表,first,last指向表頭，表尾

總結(jié)

LinkedList是一個Deque,雙向鏈表，

增刪易，查找難，造成在編碼中很少使用

java.util包提供了兩種Map:

1.HashMap

2.TreeMap

Android為了性能優(yōu)化，提供了HashMap的替代品:

1.ArrayMap

2.SparseMap

它倆可以在數(shù)據(jù)量都在千級以內(nèi)的情況下，

??如果key的類型為int，使用SparseMap,

??如果key的類型為其它類型，使用ArrayMap

HashMap相比TreeMap更常用

數(shù)據(jù)結(jié)構(gòu)

Node的數(shù)據(jù)結(jié)構(gòu):

Node {
    int hash;
    K key;
    V value;
    Node next;
}

基本數(shù)據(jù)結(jié)構(gòu):

Node[] table;
float loadFoctor;//默認值0.75f
int threshold;

可以看出HashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表

擴容

什么時候擴容

當調(diào)用put/putAll時,實際上都是調(diào)用putVal方法

??先創(chuàng)建Node,再查看新的Node放入數(shù)組，還是鏈表;

??當++size>threshold，則需要擴容

table如何擴容

它的擴容包含兩個步驟:

1. 確定擴容的大小;
2. 如何移動元素，包含數(shù)組中的元素與鏈表中的元素;

??確定擴容的大小:

????threshold默認值 = 16*0.75f=12

???? 每次擴容，

????先創(chuàng)建一個threadhold大小的數(shù)組，賦給tble,也就是擴容至threadhold

????再，threadhold = threadhold <<1，擴大一倍

??如何移動元素，包含數(shù)組中的元素與鏈表中的元素:

????1.如果元素只在數(shù)組里，而沒有鏈表:

??????新的位置是 e.hash&(newCap-1)

????2.元素在鏈表上:

??????根據(jù)(e.hash & oldCap) == 0 決定是在原位置還是在原位置+oldCap上

??????鏈表可能會分為兩部分

數(shù)據(jù)結(jié)構(gòu)

TreeMapEntry的數(shù)據(jù)結(jié)構(gòu)

TreeMapEntry {
    K key;
    V value;
    TreeMapEntry left;
    TreeMapEntry right;
    TreeMapEntry parent;
}

TreeMap的數(shù)據(jù)結(jié)構(gòu)：

TreeMapEntry root;
Comparator comparator;

TreeMap實際上是紅黑二叉樹

數(shù)據(jù)結(jié)構(gòu)

int[] mKeys;
Object[] mValues;

總結(jié)

官方推薦去使用SparseArray去替換HashMap,
犧牲了部分效率換來內(nèi)存

可以看作HashMap+LinkedList，用于保證插入順序

一般用于作為緩存

Vector

HashTable

用于讀寫分離，實現(xiàn)讀并發(fā)，寫同步

并發(fā)的不同策略:

??1.Blocking容器

??2.CopyOnWrite容器

??3.Concurrent容器

并發(fā)策略:

??用于解決限制容量的容器的存取問題

??類似生產(chǎn)者-消費者

??容器為空時，阻塞取線程

??容器滿時，阻塞存線程

并發(fā)策略:

??寫時賦值，即添加元素時，先復(fù)制整個容器，添加到復(fù)制的容器中,
??再將容器引用指向復(fù)制的容器，達到讀的最大并發(fā);
?? 適用于讀多寫少的情況;

并發(fā)策略:

??使用分段鎖，首先將容器分成多段，每段使用不同的鎖，對不同段達到讀寫并發(fā),相同段讀并發(fā)，寫同步