- 分析常用集合的底層的原理：
ArrayList、Vector、LinckedList、HashMap、HashSet、LinkedHashMap、LruCache、SparseArray、ConcurrentHashMap
一、ArrayList
最佳的做法是將
ArrayList作為默認(rèn)的首選，當(dāng)你需要而外的功能的時(shí)候，或者是當(dāng)程序性能由于經(jīng)常需要從表中間插入和刪除而變差的時(shí)候，才會(huì)去選擇LinkedList來(lái)源于THinking in Java-
源碼分析
- 最重要的兩個(gè)屬性分別是:
elementData數(shù)組size的大小
transient Object[] elementData; /** * The size of the ArrayList (the number of elements it contains). * * @serial */ //以及 size 大小 private int size;-
transient:java:語(yǔ)言的關(guān)鍵字，變量修飾符，如果用transient聲明一個(gè)實(shí)例變量，當(dāng)對(duì)象存儲(chǔ)時(shí)，它的值不需要維持。換句話來(lái)說(shuō)就是，用transient關(guān)鍵字標(biāo)記的成員變量不參與序列化過(guò)程。 - 構(gòu)造函數(shù):
new ArrayList()的時(shí)候，會(huì)指定一個(gè)Object[]
private static final Object[] EMPTY_ELEMENTDATA = {}; public ArrayList() { super(); this.elementData = EMPTY_ELEMENTDATA; }- 指定長(zhǎng)度
public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; }-
new Collection()添加一個(gè)集合
public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); size = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }- 添加元素
add()將指定的元素追加到列表的末尾
public boolean add(E e) { // 比如說(shuō)加了一個(gè)元素 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e;//這里的推算是 elementData[0]=e return true; }-
ensureCapacityInternal()方法詳情，如果是add一個(gè)元素，那么就會(huì)走到ensureExplicitCapacity()的方法中！同時(shí)第一次擴(kuò)容的最小的值為DEFAULT_CAPACITY=10;
private void ensureCapacityInternal(int minCapacity) { // 如果 是直接new ArrayList的話，那么擴(kuò)容的最小的值為10 if (elementData == EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } //開(kāi)始擴(kuò)展 ensureExplicitCapacity(minCapacity); }-
ensureExplicitCapacity(minCapacity),其中minCapacity是最小的長(zhǎng)度，如果是使用的new ArrayList<E>()然后add(E),那么這個(gè)minCapacity=10.具體請(qǐng)看代碼的邏輯
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }-
grow(minCapactity)增加容量以確保它至少能容納由最小容量參數(shù)指定的元素?cái)?shù)量。
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //(oldCapacity >> 1)等于 oldCapacity%2 意思就是除以2，取整數(shù) 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: //最小容量通常接近大小，所以這是一個(gè)勝利： elementData = Arrays.copyOf(elementData, newCapacity); }- 分析上面的問(wèn)題，假如第一次添加數(shù)據(jù)，那么
oldCapacity =0;0>>2=0;newCapacity - minCapacity < 0就是 ：0-10肯定小于0的,所以newCapacity = minCapacity;，根據(jù)前面的分析，minCapacity=10! -
minCapacity is usually close to size, so this is a win:翻譯為：最小容量通常接近大小，所以這是一個(gè)勝利： 最后調(diào)用等到一個(gè)容器長(zhǎng)度為10的elementData: - 最后一步在
elementData[size++] = e;就是把elementData[0] = e;賦值完成了，size才會(huì)++ ，等于size=1 - 關(guān)于
>>代表右移;2的二進(jìn)制是10，>>代表右移，10右移1位是二進(jìn)制的1，<<代表左移，10左移1位是二進(jìn)制的100，也就是十進(jìn)制的4。
- 最重要的兩個(gè)屬性分別是:
往指定角標(biāo)中添加元素 ,過(guò)程和添加一個(gè)元素一樣，只不過(guò)這個(gè)方法更加的高效
System.arraycopy()
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
// 首先擴(kuò)容校驗(yàn)。
ensureCapacityInternal(size + 1); // Increments modCount!!
// TODO: 2018/8/16 使用了 native的方法
// 復(fù)制，向后移動(dòng) 接著對(duì)數(shù)據(jù)進(jìn)行復(fù)制，目的是把 index 位置空出來(lái)放本次插入的數(shù)據(jù)，并將后面的數(shù)據(jù)向后移動(dòng)一個(gè)位置。
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
- 在
ArrayList中自定義了writeObject和readObject,目的是為了：JVM會(huì)調(diào)用這兩個(gè)自定義方法來(lái)實(shí)現(xiàn)序列化與反序列化ArrayList只序列化(序列化 (Serialization)將對(duì)象的狀態(tài)信息轉(zhuǎn)換為可以存儲(chǔ)或傳輸?shù)男问降倪^(guò)程。在序列化期間，對(duì)象將其當(dāng)前狀態(tài)寫入到臨時(shí)或持久性存儲(chǔ)區(qū)。以后，可以通過(guò)從存儲(chǔ)區(qū)中讀取或反序列化對(duì)象的狀態(tài)，重新創(chuàng)建該對(duì)象)了被使用的數(shù)據(jù)。
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
...
}
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
...
}
-
ArrayList的線程不安全,通過(guò)下面的方式證明
final ArrayList<String> lists=new ArrayList<>();
Thread t1= new Thread(){
@Override
public void run() {
super.run();
for (int i=0;i<25;i++){
lists.add("我是i="+i);
}
}
};
Thread t2= new Thread(){
@Override
public void run() {
super.run();
for (int i=25;i<50;i++){
lists.add("我是i="+i);
}
}
};
//主線程休眠1秒鐘，以便t1和t2兩個(gè)線程將lists填裝完畢。
t1.start();
t2.start();
try {
Thread.sleep(1000);
// 即使睡完覺(jué)了，但是也有可能長(zhǎng)度不對(duì)
for(int l=0;l<lists.size();l++){
// todo 兩個(gè)線程不斷的插入的話，就會(huì)導(dǎo)致插入的是null 我是i=34 我是i=10 我是i=35 我是i=11 null null 我是i=12 我是i=38 我是i=13 我是i=39
System.out.print(lists.get(l)+" ");
}
} catch (InterruptedException e) {
e.printStackTrace();
}
- 兩個(gè)線程不斷的插入的話，就會(huì)導(dǎo)致插入的是
null我是i=34 我是i=10 我是i=35 我是i=11 null null 我是i=12 我是i=38 我是i=13 我是i=39- 如果要使用安全的線程的話，可以通過(guò)
List<String> data=Collections.synchronizedList(new ArrayList<String>());得到線程安全的集合，
*Collections.synchronizedList的原理,如下代碼
public static <T> List<T> synchronizedList(List<T> list) { return (list instanceof RandomAccess ? new SynchronizedRandomAccessList<>(list) : new SynchronizedList<>(list)); }- 可以在
SynchronizedList類中方法加入了關(guān)鍵字synchronized
public E get(int index) { synchronized (mutex) {return list.get(index);} } public E set(int index, E element) { synchronized (mutex) {return list.set(index, element);} } public void add(int index, E element) { - 如果要使用安全的線程的話，可以通過(guò)
- 關(guān)于原型模式，
ArrayList實(shí)現(xiàn)了接口Cloneable;這個(gè)接口只有一個(gè)作用，就是在運(yùn)行時(shí)候通知虛擬機(jī)可以安全的實(shí)現(xiàn),在java的虛擬機(jī)中，只有實(shí)現(xiàn)了這個(gè)接口的類才可以被拷貝，否者會(huì)拋出CloneNotSupportedException
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);transient
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
-
我們可以看到這里有個(gè)深拷貝和 淺拷貝,幸運(yùn)的是
java中大部分都容器都實(shí)現(xiàn)了Cloneable這個(gè)接口，所以在程度上去實(shí)現(xiàn)深入拷貝不太難。- 深拷貝：就是需要拷貝的類中，所有的東西，比如說(shuō)：原型類中的數(shù)組，容器，飲用對(duì)象等
- 淺拷貝：就是只拷貝基本東西，容器這些不拷貝
- 更多的設(shè)計(jì)模式 二十三種設(shè)計(jì)模式
ArrayList遍歷的速度快，插入刪除速度慢，隨機(jī)訪問(wèn)的速度快
二、Vector
- 關(guān)注
add get方法:可以得出：使用synchronized進(jìn)行同步寫數(shù)據(jù)，但是開(kāi)銷較大，所以Vector是一個(gè)同步容器并不是一個(gè)并發(fā)容器。
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
- 應(yīng)該避免使用
Vector，它只存在支持遺留代碼的類中（它能正常的工作的唯一原因是：因?yàn)闉榱讼蚯凹嫒荩贿m配成為了List） - 其他的不想多說(shuō)，浪費(fèi)電！
三、LinckedList
- 變量: 集合元素?cái)?shù)量;鏈表頭節(jié)點(diǎn);鏈表尾節(jié)點(diǎn)
//集合元素?cái)?shù)量
transient int size = 0;
//鏈表頭節(jié)點(diǎn)
transient Node<E> first;
//鏈表尾節(jié)點(diǎn)
transient Node<E> last;
-
Node類，數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵類，每一個(gè)元素值，都存在兩個(gè)結(jié)點(diǎn)，前一個(gè)，后一個(gè)
private static class Node<E> {
E item;//元素值
Node<E> next;//后置節(jié)點(diǎn)
Node<E> prev;//前置節(jié)點(diǎn)
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
- 構(gòu)造方法
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
- 關(guān)注
add(E)方法,可以看到這個(gè)返回值永遠(yuǎn)為true; 每次插入都是移動(dòng)指針，和ArrayList的拷貝數(shù)組來(lái)說(shuō)效率要高上不少
public boolean add(E e) {
linkLast(e);
return true;
}
-
linkLast(E)方法:生成新節(jié)點(diǎn) 并插入到 鏈表尾部， 更新last/first節(jié)點(diǎn)。
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null) //若原鏈表為空鏈表，需要額外更新頭結(jié)點(diǎn)
first = newNode;
else//否則更新原尾節(jié)點(diǎn)的后置節(jié)點(diǎn)為現(xiàn)在的尾節(jié)點(diǎn)（新節(jié)點(diǎn)）
l.next = newNode;
size++;
modCount++;
}
如果說(shuō)，最后的一個(gè)結(jié)點(diǎn)為
null;那么我們新加入的元素，就是最后一個(gè)結(jié)點(diǎn)，如果最后一個(gè)結(jié)點(diǎn)不為null,那么我們插入的新的值就是最后結(jié)點(diǎn)的l.next = newNode.get()方法
public E get(int index) {
// ?？磾?shù)組角標(biāo)是否越界
checkElementIndex(index);
return node(index).item;
}
-
node(index)的方法
Node<E> node(int index) {
//二分查找來(lái)看 index 離 size 中間距離來(lái)判斷是從頭結(jié)點(diǎn)正序查還是從尾節(jié)點(diǎn)倒序查
// assert isElementIndex(index);
//通過(guò)下標(biāo)獲取某個(gè)node 的時(shí)候，（增、查 ），會(huì)根據(jù)index處于前半段還是后半段 進(jìn)行一個(gè)折半，以提升查詢效率
if (index < (size >> 1)) {
Node<E> x = first;
//不斷的往前面找 ，如果查找的角標(biāo)比linkedList的size的取余還小的話，就通過(guò)不斷的循環(huán)去得到相對(duì)應(yīng)的值
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;
}
}
- 可以看出這是一個(gè)二分查找，如果
index < (size >> 1),>>代表右移,其實(shí)就是%2,這里查找下去，知道找到為止 - 如果假如，我們查找的
index約接近size的一半，那么我們需要的次數(shù)就會(huì)越低，總結(jié)一句話：效率是非常低的，特別是當(dāng)index越接近size的中間值。 - 來(lái)源于
gitHub
Linckedlist底層的原理.jpg
四、HashMap
- 在 1.6 1.7
hashmap的類的代碼一共1500行左右，在1.8一共有2000行左右! 這里直接看的是JDK1.8的代碼。 - 關(guān)于變量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//左移運(yùn)算符，num << 1,相當(dāng)于num乘以2 最大的長(zhǎng)度
static final int MAXIMUM_CAPACITY = 1 << 30;// 相當(dāng)于把1 位移30為等于 1 + 30個(gè)0的長(zhǎng)度
// 填充比 因?yàn)槿绻畛浔群艽?，說(shuō)明利用的空間很多，如果一直不進(jìn)行擴(kuò)容的話，鏈表就會(huì)越來(lái)越長(zhǎng)，這樣查找的效率很低，因?yàn)殒湵淼拈L(zhǎng)度很大（當(dāng)然最新版本使用了紅黑樹后會(huì)改進(jìn)很多），擴(kuò)容之后，將原來(lái)鏈表數(shù)組的每一個(gè)鏈表分成奇偶兩個(gè)子鏈表分別掛在新鏈表數(shù)組的散列位置，這樣就減少了每個(gè)鏈表的長(zhǎng)度，增加查找效率
// hashMap本來(lái)是以空間換時(shí)間，所以填充比沒(méi)必要太大。但是填充比太小又會(huì)導(dǎo)致空間浪費(fèi)。如果關(guān)注內(nèi)存，填充比可以稍大，如果主要關(guān)注查找性能，填充比可以稍小。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//當(dāng)add一個(gè)元素到某個(gè)位桶，其鏈表長(zhǎng)度達(dá)到8時(shí)將鏈表轉(zhuǎn)換為紅黑樹
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
-
關(guān)于
Node內(nèi)部類static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; //todo 構(gòu)造函數(shù) hash值 key 和value 和 下一個(gè)結(jié)點(diǎn) Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } // 是去key的hash值和 value的hash值 然后做位異運(yùn)算 轉(zhuǎn)為二進(jìn)制 相同為0，不同為1 public final int hashCode() { // todo 位異或運(yùn)算（^） // 運(yùn)算規(guī)則是：兩個(gè)數(shù)轉(zhuǎn)為二進(jìn)制，然后從高位開(kāi)始比較，如果相同則為0，不相同則為1 return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } // todo 判斷兩個(gè) node 結(jié)點(diǎn)是否相等，一個(gè)比較自身相等，一個(gè)是比較key和value public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }-
Node類的中存儲(chǔ)了hashkeyvalue和下一個(gè)結(jié)點(diǎn)Node,后面解釋 -
Node類的hashCode是Objects.hashCode(key) ^ Objects.hashCode(value);位異或運(yùn)算（^）: 運(yùn)算規(guī)則是兩個(gè)數(shù)轉(zhuǎn)為二進(jìn)制，然后從高位開(kāi)始比較，如果相同則為0，不相同則為1 - 判斷兩個(gè)
node是否相等：一個(gè)比較自身相等，一個(gè)是比較key和value
-
HashMap的構(gòu)造方法,指定容量和擴(kuò)展因子！
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果最大的長(zhǎng)度大于最大的話，就默認(rèn)最大的
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//填充比為正
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 加入指定的容量為 10 那么新的擴(kuò)容的臨界值為 13
this.threshold = tableSizeFor(initialCapacity);
}
- 關(guān)于
tableSizeFor(initialCapacity)方法，說(shuō)白了就是算法，給你一個(gè)接近的值，設(shè)置hashmap的長(zhǎng)度為10，那么他的新的擴(kuò)容的臨界值=16
int cap=10;
int n = cap - 1;//9
n |= n >>> 1;//9的二進(jìn)制=1001 >>>表示無(wú)符號(hào)的右移 100 =十進(jìn)制 4 n= 1001 |= 100
System.out.println("n="+n); // n=13; 其實(shí)就是等于 n= 1001 |= 100 也就是n=1101 換成十進(jìn)制等于13
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
int i= (n < 0) ? 1 : (n >= 1000000) ? 1000000 : n + 1;
無(wú)符號(hào)的右移（
>>>）:按照二進(jìn)制把數(shù)字右移指定數(shù)位，高位直接補(bǔ)零，低位移除！a=a|b等于a|=b的意思就是把a(bǔ)和b按位或然后賦值給a 按位或的意思就是先把a(bǔ)和b都換成2進(jìn)制，然后用或操作比如：
9的二進(jìn)制1001>>>表示無(wú)符號(hào)的右移 得到100等于十進(jìn)制4n=1001 |= 100，最后n=1101轉(zhuǎn)化為十進(jìn)制等于n=13。-
上面函數(shù)的運(yùn)算過(guò)程
- n |= n >>> 1;//9的二進(jìn)制=1001 >>>表示無(wú)符號(hào)的右移 100 =十進(jìn)制 4 n= 1001 |= 100
- n |= n >>> 2; // 1101 移動(dòng)兩位 0011 |1101 等于1111
- n |= n >>> 4;// 1111 移動(dòng)4為 0000 |1111 =1111
- n |= n >>> 8;// 1111 移動(dòng)8為 0000 |1111 =1111
- n |= n >>> 16;// 1111 移動(dòng)16為 0000 |1111 =1111
HashMap的構(gòu)造方法,設(shè)置容器的長(zhǎng)度 但是指定的默認(rèn)的擴(kuò)展因子為0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
-
HashMap的構(gòu)造方法,什么都不指定 都給默認(rèn)的,我們自己最常用的。
//什么都不指定 都給默認(rèn)的
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
*HashMap的構(gòu)造方法, 也可以new一個(gè) map進(jìn)去，這種的方式 我們使用的比較少
public HashMap(Map<? extends K, ? extends V> m) {
//默認(rèn)指定了擴(kuò)展的因子
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
-
putMapEntries()方法,如果是構(gòu)造函數(shù)到這里來(lái)的話，就會(huì)進(jìn)入到threshold = tableSizeFor(t);這里來(lái)，然后遍歷m,然后一個(gè)個(gè)元素去添加，如果裝載進(jìn)來(lái)的map集合過(guò)于巨大，建議使用源map的原型模式clone方法克隆一個(gè)。
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
// 如果是hashmap中填充了一個(gè)map 就會(huì)走到這里來(lái) table == null =true
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// t=ft
if (t > threshold)
//也就會(huì)走到這里來(lái)
threshold = tableSizeFor(t);
} else if (s > threshold) {
// 擴(kuò)容機(jī)制
resize();
}
// copy的過(guò)程 遍歷hashmap的話，這個(gè)應(yīng)該是最高效的方式
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
- 關(guān)鍵方法
put，了解如何儲(chǔ)存的數(shù)據(jù)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
-
putVal方法的詳情，假裝put數(shù)據(jù)去分析。// 在構(gòu)造函數(shù)中，也調(diào)用了這個(gè)方法，唯一不同的地方就是 evict=fasle final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; /*如果table的在（n-1）&hash的值是空，就新建一個(gè)節(jié)點(diǎn)插入在該位置*/ if ((p = tab[i = (n - 1) & hash]) == null) // todo LinkedHashMap 重新重寫了這個(gè)方法，然后使用了 LinkedHashMap.Entry 里面多了兩個(gè)結(jié)點(diǎn) Entry<K,V> before, after; tab[i] = newNode(hash, key, value, null); ///*表示有沖突,開(kāi)始處理沖突*/ else { Node<K,V> e; K k; /*檢查第一個(gè)Node，p是不是要找的值*/ if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) 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); //如果沖突的節(jié)點(diǎn)數(shù)已經(jīng)達(dá)到8個(gè)，看是否需要改變沖突節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)， //treeifyBin首先判斷當(dāng)前hashMap的長(zhǎng)度，如果不足64，只進(jìn)行 //resize，擴(kuò)容table，如果達(dá)到64，那么將沖突的存儲(chǔ)結(jié)構(gòu)為紅黑樹 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } /*如果有相同的key值就結(jié)束遍歷*/ if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } /*就是鏈表上有相同的key值*/ if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; // todo LinkedHashMap 對(duì)其重寫 afterNodeAccess(e); return oldValue; } } ++modCount; /*如果當(dāng)前大小大于門限，門限原本是初始容量*0.75*/ if (++size > threshold) resize(); // todo LinkedHashMap 對(duì)其重寫 afterNodeInsertion(evict); return null; }-
1、可以發(fā)現(xiàn)
table肯定為null,沒(méi)有初始化，所以第一個(gè)判斷條件肯定成立tab = table) == null || (n = tab.length) == 0,這里有個(gè)小小的問(wèn)題，當(dāng)tab = table) == null成立的時(shí)候，后面||的代碼是不會(huì)執(zhí)行的，所以不會(huì)拋出空指針的異常。也就會(huì)執(zhí)行n = (tab = resize()).length;的代碼transient Node<K,V>[] table;// 第一次table沒(méi)有去初始化，肯定為null -
2、關(guān)于
resize()的方法，其實(shí)這個(gè)也是很關(guān)鍵的方法，擴(kuò)容// 擴(kuò)容機(jī)制 HasMap的擴(kuò)容機(jī)制resize(); final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; /*如果舊表的長(zhǎng)度不是空*/ if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } /*把新表的長(zhǎng)度設(shè)置為舊表長(zhǎng)度的兩倍，newCap=2*oldCap*/ else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) /*把新表的門限設(shè)置為舊表門限的兩倍，newThr=oldThr*2*/ newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; /*如果舊表的長(zhǎng)度的是0，就是說(shuō)第一次初始化表*/ else { // zero initial threshold signifies using defaults // todo 在new hashMap中的長(zhǎng)度 ，然后調(diào)用了 put的方法的時(shí)候，就會(huì)發(fā)生一次擴(kuò)容 ，長(zhǎng)度為16 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor;//新表長(zhǎng)度乘以加載因子 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) /*下面開(kāi)始構(gòu)造新表，初始化表中的數(shù)據(jù)*/ Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null)//說(shuō)明這個(gè)node沒(méi)有鏈表直接放在新表的e.hash & (newCap - 1)位置 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; //記錄下一個(gè)結(jié)點(diǎn) //新表是舊表的兩倍容量，實(shí)例上就把單鏈表拆分為兩隊(duì)， //e.hash&oldCap為偶數(shù)一隊(duì)，e.hash&oldCap為奇數(shù)一對(duì) 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; }- 擴(kuò)容方法也比較復(fù)雜，帶著問(wèn)題來(lái)分析，第一次，
put數(shù)據(jù)的時(shí)候，可以得出oldCap=0、oldThr=0;那么新的長(zhǎng)度newCap = DEFAULT_INITIAL_CAPACITY=16;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)=0.75*16=12,把新的長(zhǎng)度賦值給threshold = newThr; - 然后
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];,根據(jù)上面我們可以的得出newCap=16; - 由于
oldTab==null，所以，這幾返回一個(gè)newTab這是一個(gè)長(zhǎng)度為16的Node的數(shù)組
- 擴(kuò)容方法也比較復(fù)雜，帶著問(wèn)題來(lái)分析，第一次，
3、回到
putVal的方法中，那么n = (tab = resize()).length;也就是n=16-
4、那么
(p = tab[i = (n - 1) & hash]) == null是否成立呢，其實(shí)我們可以猜測(cè)下，第一次肯定是成立的，這里有個(gè)運(yùn)算符，位與運(yùn)算符&,把做運(yùn)算的兩個(gè)數(shù)都轉(zhuǎn)化為二進(jìn)制的，然后從高位開(kāi)始比較，如果兩個(gè)數(shù)都是1則為1，否者為0.如下面的HashMap中的算法int newHash=hash("test"); // 1的hash值=1 test :hash值=3556516 System.out.println( "newHash 1的hash值="+newHash); i = (16 - 1) & newHash; // i值=1 test值=4 System.out.println("newHash的 i值="+i); int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } -
5、這樣就是走到這里來(lái)
tab[i] = newNode(hash, key, value, null);，也就是tab[0]=newNode。這里有個(gè)面試，面試經(jīng)常問(wèn)，這里注意到tab是resize()方法返回的，在resize()方法中，又把table = newTab;,那么我們改動(dòng)tab能否去改變table呢？其實(shí)是能夠的，這里傳遞是地址值，如下面的DemoString[] newS=setTest(); newS[0]="16"; // newS =[Ljava.lang.String;@1e0b9a System.out.println("newS ="+newS); //newS =[Ljava.lang.String;@1e0b9a System.out.println("test ="+test); System.out.println("test="+test.length); System.out.println("test="+test[0]); } String[] test; public String[] setTest(){ String[] newS=new String[10]; test=newS; return newS; } 以上就是
HashMap第一次put數(shù)據(jù)的完整過(guò)程。
-
當(dāng)多次的
put數(shù)據(jù)的時(shí)候，如果 某個(gè)位置上的hash值相同的話，準(zhǔn)確的講i = (n - 1) & hash是這個(gè)值，取出來(lái)的tab不為null，那么儲(chǔ)存的結(jié)構(gòu)轉(zhuǎn)化為鏈表
for (int binCount = 0; ; ++binCount) {
/*指針為空就掛在后面*/
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果沖突的節(jié)點(diǎn)數(shù)已經(jīng)達(dá)到8個(gè)，看是否需要改變沖突節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)，
//treeifyBin首先判斷當(dāng)前hashMap的長(zhǎng)度，如果不足64，只進(jìn)行
//resize，擴(kuò)容table，如果達(dá)到64，那么將沖突的存儲(chǔ)結(jié)構(gòu)為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
/*如果有相同的key值就結(jié)束遍歷*/
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
- 當(dāng)一個(gè)位置上的大于
TREEIFY_THRESHOLD - 1也就是7的話，看是否需要改變沖突節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu).treeifyBin首先判斷當(dāng)前hashMap的長(zhǎng)度，如果不足64，只進(jìn)行resize，擴(kuò)容table，如果達(dá)到64，那么將沖突的存儲(chǔ)結(jié)構(gòu)為紅黑樹.如下圖的結(jié)構(gòu)
HashMap
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();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
- 是所有鏈表上的數(shù)據(jù)結(jié)構(gòu)都會(huì)轉(zhuǎn)，不可能在一個(gè)鏈表上，即存在紅黑樹，也存在鏈表
-
get方法相對(duì)應(yīng)就簡(jiǎn)單了
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// 不斷的去取結(jié)點(diǎn)，是紅黑樹就去找紅黑樹，是聊邊就去找鏈表
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) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
-
HashMap是一個(gè)線程不安全的容器，發(fā)生擴(kuò)容時(shí)會(huì)出現(xiàn)環(huán)形鏈表從而導(dǎo)致死循環(huán) -
HashMap是一個(gè)無(wú)序的Map，因?yàn)槊看胃鶕?jù)key的hashCode映射到Entry數(shù)組上，所以遍歷出來(lái)的順序并不是寫入的順序。 -
HashMap遍歷的速度慢，底層決定了，插入刪除的速度快，隨機(jī)訪問(wèn)的速度也比較快
五、ConcurrentHashMap
- 支持線程安全的并發(fā)容器
ConcurrentHashMap,原理和HashMap差不多，區(qū)別就是采用了CAS + synchronized來(lái)保證并發(fā)安全性 -
putVal加了同步鎖synchronized
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
//根據(jù) key 計(jì)算出 hashcode
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// 判斷是否需要進(jìn)行初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//f 即為當(dāng)前 key 定位出的 Node，如果為空表示當(dāng)前位置可以寫入數(shù)據(jù)，利用 CAS 嘗試寫入，失敗則自旋保證成功
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
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); //如果當(dāng)前位置的 hashcode == MOVED == -1,則需要進(jìn)行擴(kuò)容
else {
//如果都不滿足，則利用 synchronized 鎖寫入數(shù)據(jù)
V oldVal = null;
// todo put 數(shù)據(jù)的時(shí)候 加入了鎖
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
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;
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
if (binCount != 0) {
//如果數(shù)量大于 TREEIFY_THRESHOLD 則要轉(zhuǎn)換為紅黑樹
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
-
get方法
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
//根據(jù)計(jì)算出來(lái)的 hashcode 尋址，如果就在桶上那么直接返回值
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//如果是紅黑樹那就按照樹的方式獲取值
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
// 就不滿足那就按照鏈表的方式遍歷獲取值
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
- 基本上的變量都是被
volatile關(guān)鍵字修飾
transient volatile Node<K,V>[] table;
private transient volatile Node<K,V>[] nextTable;
private transient volatile long baseCount;
...
volatile關(guān)鍵字 Java多線程的三大核心
1、 原子性 :java原子性和數(shù)據(jù)庫(kù)事務(wù)的原子性差不多，一個(gè)操作要么是全部執(zhí)行成功或者是失敗.
- JVM 只保證了基本的原子性，但是類似 i++ 之類的操作，看著好像是原子的操作，其實(shí)里面涉及到了三個(gè)步驟
- 獲取 i 的值
- 自增
- 在賦值給 i
- 這三個(gè)步驟 要實(shí)現(xiàn)
i++這樣的原子操作就需要用到synchronized或者是 了lock進(jìn)行加鎖處理。 - 如果是基礎(chǔ)類的自增操作可以使用
AtomicInteger這樣的原子類來(lái)實(shí)現(xiàn)(其本質(zhì)是利用了CPU級(jí)別的 的CAS指令來(lái)完成的)。AtomicInteger是線程安全的 - 其中用的最多的方法就是: incrementAndGet() 以原子的方式自增
AtomicInteger atomicInteger=new AtomicInteger(); int i = atomicInteger.incrementAndGet(); System.out.println("i="+i); public final int incrementAndGet() { return U.getAndAddInt(this, VALUE, 1) + 1; }
2、可見(jiàn)性
現(xiàn)在的計(jì)算機(jī)，由于
cpu直接從 主內(nèi)存中讀取數(shù)據(jù)的效率不高。所以都會(huì)對(duì)應(yīng)的cpu高速緩存，先將主內(nèi)存中的數(shù)據(jù)讀取到緩存中，線程修改數(shù)據(jù)之后首先更新到緩存中，之后才會(huì)更新到主內(nèi)存。如果此時(shí)還沒(méi)有將數(shù)據(jù)更新到主內(nèi)存其他的線程此時(shí)讀取就是修改之前的數(shù)據(jù)volatile關(guān)鍵字就是用于保存內(nèi)存的可見(jiàn)性，當(dāng)線程A更新了volatite的修飾的變量的話，他會(huì)立即刷新到主線程，并且將其余緩存中該變量的值清空，導(dǎo)致其余線程只能去主內(nèi)存讀取最新的值
*synchronized 和加鎖也能保證可見(jiàn)性，實(shí)現(xiàn)原理就是在釋放鎖之前其余線程是訪問(wèn)不到這個(gè)共享變量的。但是和volatile 相比較起來(lái)開(kāi)銷比較大 ！
- 但是
volatile不能夠替換synchronized因?yàn)?code>volatile 不能夠保證原子性 (要么執(zhí)行成功或者失敗，沒(méi)有中間的狀態(tài))
3、順序性
int a = 100 ; //1
int b = 200 ; //2
int c = a + b ; //3
正常的代碼的執(zhí)行順序應(yīng)該是
1》》2》》3。但是有時(shí)候JVM為了提高整體的效率會(huì)進(jìn)行指令重排導(dǎo)致執(zhí)行順序可能是2》》1》》3。但是JVM也不能是 什么都進(jìn)行重排，是在保證最終結(jié)果和代碼順序執(zhí)行結(jié)果是一致的情況下才可能會(huì)進(jìn)行重排重排在單線程中不會(huì)出現(xiàn)問(wèn)題，但是在多線程中就會(huì)出現(xiàn)順序不一致的問(wèn)題
java中可以使用volatile關(guān)鍵字來(lái)保證順序性，synchronized和lock也可以來(lái)保證有序性，和保證 原子性的方式一樣，通過(guò)同一段時(shí)間只能一個(gè)線程訪問(wèn)來(lái)實(shí)現(xiàn)的除了
volatile關(guān)鍵字顯式的保證順序之外，jvm HIA通過(guò)happen-before原則來(lái)隱式來(lái)保證順序性。-
volitle的應(yīng)用，主要是在單利，個(gè)人感覺(jué)這是常用的在移動(dòng)端的開(kāi)發(fā)!當(dāng)然可以使用內(nèi)部類或者是單利去實(shí)現(xiàn)，更多的設(shè)計(jì)模式- 1、
volatile實(shí)現(xiàn)一個(gè)雙重檢查鎖的單例模式
public class Singleton { private static volatile Singleton singleton; private Singleton() { } public static Singleton getInstance() { if (singleton == null) { synchronized (Singleton.class) { if (singleton == null) { singleton = new Singleton(); } } } return singleton; } }- 這里的
volatile關(guān)鍵字主要是為了防止指令重排。 如果不用volatile，singleton = new Singleton();，這段代碼其實(shí)是分為三步：- 分配內(nèi)存空間。(1)
- 初始化對(duì)象。(2)
- 將 singleton 對(duì)象指向分配的內(nèi)存地址。(3)
- 加上
volatile是為了讓以上的三步操作順序執(zhí)行，反之有可能第三步在第二步之前被執(zhí)行就有可能導(dǎo)致某個(gè)線程拿到的單例對(duì)象還沒(méi)有初始化，以致于使用報(bào)錯(cuò)。
- 1、
2、控制停止線程的標(biāo)記
private volatile boolean flag ;
private void run(){
new Thread(new Runnable() {
@Override
public void run() {
doSomeThing();
}
});
}
private void stop(){
flag = false ;
}
- 如果沒(méi)有用
volatile來(lái)修飾flag，就有可能其中一個(gè)線程調(diào)用了stop()方法修改了flag的值并不會(huì)立即刷新到主內(nèi)存中，導(dǎo)致這個(gè)循環(huán)并不會(huì)立即停止.這里主要利用的是volatile的內(nèi)存可見(jiàn)性 .
六、HashSet
-
HashSet是一個(gè)不允許存儲(chǔ)重復(fù)元素的集合。 -
HashSet的源碼只有三百多行，原理非常簡(jiǎn)單，主要底層還是HashMap。 -
map和PERSENT:
// map ：用于存放最終數(shù)據(jù)的。
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
// PRESENT ：是所有寫入 map 的 value 值。
private static final Object PRESENT = new Object();
- 構(gòu)造方法:底層一個(gè)hashMap
public HashSet() {
map = new HashMap<>();
}
- 關(guān)鍵的就是這個(gè)
add()方法。 可以看出它是將存放的對(duì)象當(dāng)做了HashMap的健，value都是相同的RESENT。由于HashMap的key是不能重復(fù)的，所以每當(dāng)有重復(fù)的值寫入到HashSet時(shí)，value會(huì)被覆蓋，但key不會(huì)受到影響，這樣就保證了HashSet中只能存放不重復(fù)的元素。
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
七、LinkedHashMap
-
HashMap是一個(gè)無(wú)序的Map，每次根據(jù)key的hashcode映射到Entry數(shù)組上，所以遍歷出來(lái)的順序并不是寫入的順序。 因此JDK推出一個(gè)基于HashMap但具有順序的LinkedHashMap來(lái)解決有排序需求的場(chǎng)景。它的底層是繼承于HashMap實(shí)現(xiàn)的，由一個(gè)雙向鏈表所構(gòu)成。 -
LinkedHashMap的排序方式有兩種：- 根據(jù)寫入順序排序。
- 根據(jù)訪問(wèn)順序排序(LRU底層的原理)。 其中根據(jù)訪問(wèn)順序排序時(shí)，每次
get都會(huì)將訪問(wèn)的值移動(dòng)到鏈表末尾，這樣重復(fù)操作就能得到一個(gè)按照訪問(wèn)順序排序的鏈表。
-
LinkedHashMap中的Entry:利用了頭節(jié)點(diǎn)和其余的各個(gè)節(jié)點(diǎn)之間通過(guò)Entry中的after和before指針進(jìn)行關(guān)聯(lián)static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } } - 變量
// 用于指向雙向鏈表的頭部
transient LinkedHashMap.Entry<K,V> head;
//用于指向雙向鏈表的尾部
transient LinkedHashMap.Entry<K,V> tail;
// LinkedHashMap 如何達(dá)到有序的關(guān)鍵
// todo 還有一個(gè) accessOrder 成員變量，默認(rèn)是 false，默認(rèn)按照插入順序排序，為 true 時(shí)按照訪問(wèn)順序排序，也可以調(diào)用
final boolean accessOrder;
- 構(gòu)造方法，
LRUchace最近最少使用的緩存底層就是這個(gè)構(gòu)造函數(shù)。
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
-
側(cè)重關(guān)注
put，會(huì)走父類HashMap中的put方法，具體請(qǐng)看HashMapput方法的解釋- 1、 在
LinkedHashMap重寫了,newNode的方法。 使用了LinkedHashMap.Entry里面多了兩個(gè)結(jié)點(diǎn)Entry<K,V> before, after;
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e); //秘密就在于 new的是自己的Entry類，然后調(diào)用了linkedNodeLast linkNodeLast(p); return p; }- 2、實(shí)現(xiàn)了
afterNodeAccess()方法，void afterNodeAccess(Node<K,V> p) { }！此函數(shù)執(zhí)行的效果就是將最近使用的Node，放在鏈表的最末尾。特別說(shuō)明一下，這里是顯示鏈表的修改后指針的情況，實(shí)際上在桶里面的位置是不變的，只是前后的指針指向的對(duì)象變了！
// 此函數(shù)執(zhí)行的效果就是將最近使用的Node，放在鏈表的最末尾 void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.Entry<K,V> last; //僅當(dāng)按照LRU原則且e不在最末尾，才執(zhí)行修改鏈表，將e移到鏈表最末尾的操作 if (accessOrder && (last = tail) != e) { //將e賦值臨時(shí)節(jié)點(diǎn)p， b是e的前一個(gè)節(jié)點(diǎn)， a是e的后一個(gè)節(jié)點(diǎn) LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; //設(shè)置p的后一個(gè)節(jié)點(diǎn)為null，因?yàn)閳?zhí)行后p在鏈表末尾，after肯定為null p.after = null; //p前一個(gè)節(jié)點(diǎn)不存在，情況一 if (b == null) head = a; else b.after = a; if (a != null) a.before = b; //p的后一個(gè)節(jié)點(diǎn)不存在，情況二 else last = b; if (last == null) head = p; else { //正常情況，將p設(shè)置為尾節(jié)點(diǎn)的準(zhǔn)備工作，p的前一個(gè)節(jié)點(diǎn)為原先的last，last的after為p p.before = last; last.after = p; } //將p設(shè)置為將p設(shè)置為尾節(jié)點(diǎn) tail = p; ++modCount; // 修改計(jì)數(shù)器+1 } }- 3、
put方法 執(zhí)行的第二個(gè)步驟 ，這個(gè)方法沒(méi)什么用盡可能刪除最老的 插入后把最老的Entry刪除，不過(guò)removeEldestEntry總是返回false，所以不會(huì)刪除，估計(jì)又是一個(gè)方法給子類用的
void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry<K,V> first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; // todo hashmap中移除 Node結(jié)點(diǎn) removeNode(hash(key), key, null, false, true); } } // 如果映射表示緩存，這是有用的：它允許通過(guò)刪除過(guò)時(shí)條目來(lái)減少內(nèi)存消耗的映射。 protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; }- 4 、
afterNodeRemoval()移除結(jié)點(diǎn)也會(huì)重寫，因?yàn)榻Y(jié)點(diǎn)都不一樣
void afterNodeRemoval(Node<K,V> e) { // unlink //與afterNodeAccess一樣，記錄e的前后節(jié)點(diǎn)b，a LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; //p已刪除，前后指針都設(shè)置為null，便于GC回收 p.before = p.after = null; //與afterNodeAccess一樣類似，一頓判斷，然后b，a互為前后節(jié)點(diǎn) if (b == null) head = a; else b.after = a; if (a == null) tail = b; else a.before = b; } - 1、 在
-
get()方法詳情,然后調(diào)用父類HashMap的getNode()去找結(jié)點(diǎn)public V get(Object key) { Node<K,V> e; //調(diào)用HashMap的getNode的方法， if ((e = getNode(hash(key), key)) == null) return null; if (accessOrder) afterNodeAccess(e); return e.value; }-
HashMap中的getNode()方法
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) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; } -
關(guān)于訪問(wèn)順序排序的Demo,我只想說(shuō)明了一下，等于用了的數(shù)據(jù)，就會(huì)放在鏈表的末尾，這個(gè)類也是安卓中
LruCache的底層原理
LinkedHashMap<String, Integer> map1 = new LinkedHashMap<String, Integer>(10, (float) 0.75,true);
map1.put("1",1) ;
map1.put("2",2) ;
map1.put("3",3) ;
map1.put("4",4) ;
map1.put("5",5) ;
map1.put("6",6) ;
map1.put("7",7) ;
map1.put("8",8) ;
map1.put("9",9) ;
map1.put("10",10) ;
map1.get("6");
// {1=1, 2=2, 3=3, 4=4, 5=5, 7=7, 8=8, 9=9, 10=10, 6=6}
System.out.println("map1=="+map1);
LinkedHashMap的原理.png
八、LruCache
-
Android中提供了一種基本的緩存策略，即LRU（least recently used）?；谠摲N策略，當(dāng)存儲(chǔ)空間用盡時(shí)，緩存會(huì)清除最近最少使用的對(duì)象 -
LRU（Least Recently Used）最近最少使用的，看了源碼才知道核心是LRUCache類，這個(gè)類的核心其實(shí)是LinkedHashMap類. - Demo 如下
LruCache<Integer,String> lruCache=new LruCache<>(5);
lruCache.put(1,"1");
lruCache.put(2,"2");
lruCache.put(3,"3");
lruCache.put(4,"4");
lruCache.put(5,"5");
lruCache.get(1);
lruCache.get(2);
lruCache.get(3);
lruCache.get(4);
Map<Integer, String> snapshot = lruCache.snapshot();
//lruCache={5=5, 1=1, 2=2, 3=3, 4=4} 5最少使用到
System.out.println("lruCache="+snapshot.toString());
//當(dāng)多添加一個(gè)的話，那么5就會(huì)被刪除，加入6上去
lruCache.put(6,"6");
// new lruCache={1=1, 2=2, 3=3, 4=4, 6=6}
Map<Integer, String> snapshot1 = lruCache.snapshot();
System.out.println(" new lruCache="+snapshot1.toString());
- 構(gòu)造方法,可以明顯看出，底層使用的是
LinkedHashMap.
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
// 初始化這里 就是 new的 true的 所以使用的順序排序
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}
-
put方法 :重要的就是在添加過(guò)緩存對(duì)象后，調(diào)用trimToSize()方法，來(lái)判斷緩存是否已滿，如果滿了就要?jiǎng)h除近期最少使用的算法.同時(shí)線程也是安全的。
public final V put(K key, V value) {
//不可為空，否則拋出異常
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
// 多線程 可以使用
synchronized (this) {
//插入的緩存對(duì)象值加1
putCount++;
//增加已有緩存的大小
size += safeSizeOf(key, value);
//向map中加入緩存對(duì)象
previous = map.put(key, value);
if (previous != null) {
//如果已有緩存對(duì)象，則緩存大小恢復(fù)到之前
size -= safeSizeOf(key, previous);
}
}
//entryRemoved()是個(gè)空方法，可以自行實(shí)現(xiàn)
if (previous != null) {
entryRemoved(false, key, previous, value);
}
//調(diào)整緩存大小(關(guān)鍵方法)
trimToSize(maxSize);
return previous;
}
- 1、
safeSizeOf方法,這個(gè)sizeof的方法，就是我們自己需要重寫的，記得圖片加載框架的設(shè)計(jì)，就會(huì)運(yùn)用到他
private int safeSizeOf(K key, V value) {
// 每一個(gè)的需要緩存的大小
int result = sizeOf(key, value);
if (result < 0) {
throw new IllegalStateException("Negative size: " + key + "=" + value);
}
return result;
}
protected int sizeOf(K key, V value) {
return 1;
}
- 2、調(diào)整緩存大小(關(guān)鍵方法)
trimToSize(maxSize);maxSize也就是指定的大小，當(dāng)if (size <= maxSize) { break; }這個(gè)判斷不成立的時(shí)候，就會(huì)往下走，迭代器就會(huì)去獲取第一個(gè)對(duì)象，即隊(duì)尾的元素，近期最少訪問(wèn)的元素。然后把它刪除該對(duì)象，并更新緩存大小map.remove(key);
private void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(getClass().getName()
+ ".sizeOf() is reporting inconsistent results!");
}
if (size <= maxSize) {
break;
}
//迭代器獲取第一個(gè)對(duì)象，即隊(duì)尾的元素，近期最少訪問(wèn)的元素
Map.Entry<K, V> toEvict = null;
for (Map.Entry<K, V> entry : map.entrySet()) {
toEvict = entry;
}
if (toEvict == null) {
break;
}
key = toEvict.getKey();
value = toEvict.getValue();
//刪除該對(duì)象，并更新緩存大小
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++;
}
// 空實(shí)現(xiàn)
entryRemoved(true, key, value, null);
}
}
- 關(guān)于
get方法！也是一個(gè)同步的方法。
public final V get(K key) {
//key為空拋出異常
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
//獲取對(duì)應(yīng)的緩存對(duì)象
//get()方法會(huì)實(shí)現(xiàn)將訪問(wèn)的元素更新到隊(duì)列頭部的功能
// todo LinkedHashMap 里面已經(jīng)實(shí)現(xiàn)了 如果 添加到頭部去
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
...
}
-
LruCache使用的Demo,這個(gè)Demo就看看，沒(méi)吊用。
public class ImageCache {
//定義LruCache，指定其key和保存數(shù)據(jù)的類型
private LruCache<String, Bitmap> mImageCache;
ImageCache() {
//獲取當(dāng)前進(jìn)程可以使用的內(nèi)存大小，單位換算為KB
final int maxMemory = (int)(Runtime.getRuntime().maxMemory() / 1024);
//取總內(nèi)存的1/4作為緩存
final int cacheSize = maxMemory / 4;
//初始化LruCache
mImageCache = new LruCache<String, Bitmap>(cacheSize) {
//定義每一個(gè)存儲(chǔ)對(duì)象的大小
@Override
protected int sizeOf(String key, Bitmap bitmap) {
return bitmap.getRowBytes() * bitmap.getHeight() / 1024;
}
};
}
//獲取數(shù)據(jù)
public Bitmap getBitmap(String url) {
return mImageCache.get(url);
}
//存儲(chǔ)數(shù)據(jù)
public void putBitmap(String url, Bitmap bitmap) {
mImageCache.put(url, bitmap);
}
}
九、SparseArray
SparseArray是android里為<Interger,Object>這樣的Hashmap而專門寫的類,目的是提高效率，其核心是折半查找函數(shù)（binarySearch）。SparseArray僅僅提高內(nèi)存效率，而不是提高執(zhí)行效率，所以也決定它只適用于android系統(tǒng)（內(nèi)存對(duì)android項(xiàng)目有多重要）SparseArray不需要開(kāi)辟內(nèi)存空間來(lái)額外存儲(chǔ)外部映射，從而節(jié)省內(nèi)存。變量,核心就是兩個(gè)數(shù)組:
mKeysmValues
//是否可以回收，即清理mValues中標(biāo)記為DELETED的值的元素
private boolean mGarbage = false;
private int[] mKeys; //保存鍵的數(shù)組
private Object[] mValues; //保存值的數(shù)組
private int mSize; //當(dāng)前已經(jīng)保存的數(shù)據(jù)個(gè)數(shù)
- 構(gòu)造方法 ：如果
initialCapacity=0那么mKeys,mValuse都初始化為size=0的數(shù)組，當(dāng)initialCapacity>0時(shí)，系統(tǒng)生成length=initialCapacity的value數(shù)組，同時(shí)新建一個(gè)同樣長(zhǎng)度的key數(shù)組。
public SparseArray() {
this(10);
}
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {
/* ArrayUtils.newUnpaddedObjectArray 的源碼
public static Object[] newUnpaddedObjectArray(int minLen) {
return (Object[])VMRuntime.getRuntime().newUnpaddedArray(Object.class, minLen);
}
*/
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
mSize = 0;
}
- 關(guān)于
put方法,關(guān)鍵是通過(guò)二分查找，查找相對(duì)應(yīng)的i角標(biāo),如果存在的話，直接賦值新的值，如果不存在的話，取~i位非運(yùn)算符（~）: 十進(jìn)制變二進(jìn)制：原碼--反碼--加一（補(bǔ)碼），相當(dāng)于 value +1 然后 取反 就可以了.然后就會(huì)走到mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);和mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);中，這樣就完成了賦值的過(guò)程。
public void put(int key, E value) {
// 二分查找，這個(gè)i的值,
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//如果找到了，就把這個(gè)值給替換上去 ，或者是賦值上去
// 這里 也就可以解釋出為啥 替換為最新的值
if (i >= 0) {
mValues[i] = value;
} else {
//這里就是key要插入的位置，上面二分查找方法提到過(guò)
//位非運(yùn)算符（~）
i = ~i;
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
if (mGarbage && mSize >= mKeys.length) {
gc();
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
// 一個(gè)新的值 ，就會(huì)把key 和 value 和 i值插入到兩個(gè)數(shù)組中
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
// todo 然后長(zhǎng)度 加上 1 nice
mSize++;
}
}
-
get方法:通過(guò)二分查找法，在mKeys數(shù)組中查詢key的位置，然后返回mValues數(shù)組中對(duì)應(yīng)位置的值，找不到則返回默認(rèn)值
public E get(int key, E valueIfKeyNotFound) {
// 二分查找 感覺(jué)不像啊 臥槽
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i < 0 || mValues[i] == DELETED) {
return valueIfKeyNotFound;
} else {
return (E) mValues[i];
}
}
-
delete其實(shí)就是把這個(gè)mValues[i]標(biāo)記為DELETED.
public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
/*
i>0表示，找到了key對(duì)應(yīng)的下標(biāo)，否則應(yīng)該是負(fù)數(shù)。同時(shí)判斷mValues[i] 是不是Object這個(gè)對(duì)象，如果不是，直接替換為Object（DELETE起到標(biāo)記刪除位置的作用）,并標(biāo)記 mGarbage=true，注意：這里delete只操作了values數(shù)組，并沒(méi)有去操作key數(shù)組;
*/
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage = true;
}
}
}
-
removeReturnOld其實(shí)就是多了一步，把要?jiǎng)h除的值返回，其余同delete一樣
public E removeReturnOld(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {
final E old = (E) mValues[i];
mValues[i] = DELETED;
mGarbage = true;
return old;
}
}
return null;
}
-
clear這里要留意，clear只是清空了values數(shù)組，并沒(méi)有操作keys數(shù)組,這里也是傳遞的地址值，然后通過(guò)for循環(huán)，把每個(gè)元素清空！
public void clear() {
int n = mSize;
Object[] values = mValues;
for (int i = 0; i < n; i++) {
values[i] = null;
}
mSize = 0;
mGarbage = false;
}
- 其實(shí)還有個(gè)方法
append,添加數(shù)據(jù)的時(shí)候最好去使用它，因?yàn)樗鼤?huì)判斷下mSize != 0 && key <= mKeys[mSize - 1]、如果滿足了才會(huì)調(diào)用put方法，不滿足，直接添加數(shù)據(jù)，而不是一上來(lái)就開(kāi)始進(jìn)行二分查找。
// 要使用這個(gè)方法 好點(diǎn) 。
public void append(int key, E value) {
// 判斷了是否 需要 二分查找，還是直接插入
if (mSize != 0 && key <= mKeys[mSize - 1]) {
put(key, value);
return;
}
if (mGarbage && mSize >= mKeys.length) {
// 通過(guò)gc的方法，把DELETED值的 values 清空
gc();
}
// 可以直接都要這里來(lái) ，是最節(jié)約能量
mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
mValues = GrowingArrayUtils.append(mValues, mSize, value);
mSize++;
}
- 關(guān)于原型模式中的深拷貝的實(shí)現(xiàn)，這里也幫我指明了，一定要記得拷貝類中的容器
@Override
@SuppressWarnings("unchecked")
public SparseArray<E> clone() {
SparseArray<E> clone = null;
try {
clone = (SparseArray<E>) super.clone();
// 原型模式的深拷貝 兩個(gè)容器的拷貝的過(guò)程----?。?！
clone.mKeys = mKeys.clone();
clone.mValues = mValues.clone();
} catch (CloneNotSupportedException cnse) {
/* ignore */
}
return clone;
}
其他的
SparseBooleanArray SparseIntArray SparseLongArray的原理一樣SparseArray與HashMap無(wú)論是怎樣進(jìn)行插入,數(shù)據(jù)量相同時(shí),前者都要比后者要省下一部分內(nèi)存,但是效率呢？----在倒序插入的時(shí)候,SparseArray的插入時(shí)間和HashMap的插入時(shí)間遠(yuǎn)遠(yuǎn)不是一個(gè)數(shù)量級(jí).由于SparseArray每次在插入的時(shí)候都要使用二分查找判斷是否有相同的值被插入.因此這種倒序的情況是SparseArray效率最差的時(shí)候.附贈(zèng)一個(gè)二分查找
/**
* 二分查找
* @param ints 需要被查找的數(shù)組
* @param length 數(shù)組的長(zhǎng)度
* @param value 查找的值
*/
private int binarySearch(int[] ints, int length, int value) {
int i = 0;
int h = length - 1;
while (i <= h) {
/**
* >>>與>>唯一的不同是它無(wú)論原來(lái)的最左邊是什么數(shù)，統(tǒng)統(tǒng)都用0填充。
* —比如你的例子，byte是8位的，-1表示為byte型是11111111(補(bǔ)碼表示法）
* b>>>4就是無(wú)符號(hào)右移4位，即00001111，這樣結(jié)果就是15。
* 這里相當(dāng)移動(dòng)一位，除以二
*/
//中間的角標(biāo)
final int mid = (i + h) >>> 1;// 第一次 2 第二次 mid=3 第三次mid=4
final int midVal = ints[mid];// 第一次 3 第二次 midVal=4 第三次mid=5
if (midVal < value) {
i = mid + 1;// 第一次 3 第二次 i=4
} else if (value < midVal) {
h = mid - 1;
} else if (value == midVal) {
return mid; //第三次mid=5 返回了
}
}
// 這個(gè)取反 ，相當(dāng)于 value +1 然后 取反 就可以了
return ~value;
}
- 附贈(zèng)
System.arraycopy()的用法
int[] mKeys={10,5,14,5,46};
int[] newKeys=new int[5];
/*
* @param src 源數(shù)組。
* @param srcPos 表示源數(shù)組要復(fù)制的起始位置，
* @param dest 目的地?cái)?shù)組。
* @param destPos 在目標(biāo)數(shù)據(jù)中的起始位置。
* @param length 要復(fù)制的數(shù)組元素的數(shù)目。
*/
// todo source of type android.util.SparseArray is not an array
// destPsot +length 不能超過(guò) 新的數(shù)組的長(zhǎng)度
System.arraycopy(mKeys,0, newKeys, 2, 3);
for (Integer str : newKeys) {
System.out.print("newKeys="+str+" ");
}
最后說(shuō)明幾點(diǎn)
-
ArrayList的主要消耗是數(shù)組擴(kuò)容以及在指定位置添加數(shù)據(jù)，在日常使用時(shí)最好是指定大小，盡量減少擴(kuò)容。更要減少在指定位置插入數(shù)據(jù)的操作。 -
ArrayList遍歷的速度快，插入刪除速度慢，隨機(jī)訪問(wèn)的速度快 -
LinkedList插入，刪除都是移動(dòng)指針效率很高。查找需要進(jìn)行遍歷查詢，效率較低。二分查找，如果查找的index的越接近size的一半的話，這樣查找的效率很低 -
HashMap是一個(gè)線程不安全的容器，發(fā)生擴(kuò)容時(shí)會(huì)出現(xiàn)環(huán)形鏈表從而導(dǎo)致死循環(huán) -
HashMap是一個(gè)無(wú)序的Map，因?yàn)槊看胃鶕?jù)key的hashCode映射到Entry數(shù)組上，所以遍歷出來(lái)的順序并不是寫入的順序。 -
HashMap遍歷的速度慢，底層決定了，插入刪除的速度快，隨機(jī)訪問(wèn)的速度也比較快 -
ConcurrentHashMap并發(fā)容器，區(qū)別就是采用了CAS + synchronized 來(lái)保證并發(fā)安全性 - 位與運(yùn)算符
&,把做運(yùn)算的兩個(gè)數(shù)都轉(zhuǎn)化為二進(jìn)制的，然后從高位開(kāi)始比較，如果兩個(gè)數(shù)都是1則為1，否者為0 - 無(wú)符號(hào)的右移（
>>>）:按照二進(jìn)制把數(shù)字右移指定數(shù)位，高位直接補(bǔ)零，低位移除！ -
a=a|b等于a|=b的意思就是把a和b按位或然后賦值給a按位或的意思就是先把a和b都換成2進(jìn)制，然后用或操作 - 位異或運(yùn)算（
^）: 運(yùn)算規(guī)則是兩個(gè)數(shù)轉(zhuǎn)為二進(jìn)制，然后從高位開(kāi)始比較，如果相同則為0，不相同則為1 -
HashSet底層其實(shí)就是HashMap，只不過(guò)是一個(gè)value都一樣的HashSet. -
LRU（Least Recently Used）最近最少使用的，看了源碼才知道核心是LRUCache類，這個(gè)類的核心其實(shí)是LinkedHashMap類. -
~i位非運(yùn)算符（~）: 十進(jìn)制變二進(jìn)制：原碼--反碼--加一（補(bǔ)碼），相當(dāng)于 value +1 然后 取反 就可以了 -
SparseArraySparseBooleanArray SparseIntArray SparseLongArray的原理一樣 -
SparseArray與HashMap無(wú)論是怎樣進(jìn)行插入,數(shù)據(jù)量相同時(shí),前者都要比后者要省下一部分內(nèi)存,但是效率呢？----在倒序插入的時(shí)候,SparseArray的插入時(shí)間和HashMap的插入時(shí)間遠(yuǎn)遠(yuǎn)不是一個(gè)數(shù)量級(jí).由于SparseArray每次在插入的時(shí)候都要使用二分查找判斷是否有相同的值被插入.因此這種倒序的情況是SparseArray效率最差的時(shí)候. - 二分查找，是當(dāng)角標(biāo)越接近數(shù)組長(zhǎng)度的一半，效率越低
- 臥槽，剛看了一下總共將近一萬(wàn)字，光寫的過(guò)程用了16個(gè)小時(shí)，整理資料大概是10個(gè)小時(shí)。
