1、總體框架設(shè)計(jì)圖
image-20190423155946133.png
image-20190423160005487.png
2恕稠、具體實(shí)現(xiàn)類分析
2.1琅绅、ArrayList
2.1.1、屬性
// 默認(rèn)初始化大小
private static final int DEFAULT_CAPACITY = 10;
// 初始化時(shí)鹅巍，指定大小為0時(shí)千扶，使用該變量
private static final Object[] EMPTY_ELEMENTDATA = {};
// 初始化時(shí)料祠，沒有指定大小時(shí)，使用該變量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//真正存儲(chǔ)數(shù)據(jù)的地方
transient Object[] elementData; // non-private to simplify nested class access
//記錄當(dāng)前存儲(chǔ)了多少數(shù)據(jù)
private int size;
//記錄對(duì)當(dāng)前List操作的次數(shù)澎羞，在Iterator迭代時(shí)髓绽，刪除數(shù)據(jù)，會(huì)拋出異常就是根據(jù)該值進(jìn)行判斷的,
//該值是在AbstractList中定義的
private int modCount
2.1.2妆绞、new ArrayList的三種方式
//指定默認(rèn)大小
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
//不指定大小
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//使用collection子類初始化使用Arrays.copyOf(其實(shí)底層是System.arraycopy)
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
2.1.3顺呕、add方法
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
/**
* 該方法做了兩件事
* 1.檢查當(dāng)前elementData大小是否需要擴(kuò)容
* 2.擴(kuò)容
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
/**
* 計(jì)算最小容量大小，可以看到摆碉，如果使用的是new ArrayList()這個(gè)構(gòu)造函數(shù)塘匣，那么這里會(huì)返回最小默認(rèn)容量
* 10，這里minCapacity的值為size+1
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//操作次數(shù)+1巷帝，判斷是否需要擴(kuò)容
private void ensureExplicitCapacity(int minCapacity) {
modCount++; //操作次數(shù)+1
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity); //當(dāng)前容量小于前面函數(shù)calculateCapacity返回的最小容量是忌卤，擴(kuò)容處理
}
//擴(kuò)容處理
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; //獲取原來的容量大小
int newCapacity = oldCapacity + (oldCapacity >> 1); //新容量大小大概為老的1.5倍,這里使用的是位運(yùn)算。相對(duì)十進(jìn)制運(yùn)行比較快
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);// 會(huì)將所有的數(shù)據(jù)復(fù)制一份到新數(shù)組楞泼，所以ArrayList每次擴(kuò)容都會(huì)比較慢驰徊，特別是數(shù)據(jù)大的情況下
}
2.2、LinkedList
2.2.1堕阔、屬性
transient int size = 0; //記錄當(dāng)前數(shù)據(jù)量
transient Node<E> first;//頭指針
transient Node<E> last;//尾指針
/**私有的靜態(tài)內(nèi)部類棍厂，存儲(chǔ)數(shù)據(jù)
* 可以看到LinkedList是雙向指針
*/
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
2.2.2、add方法
public boolean add(E e) {
linkLast(e);
return true;
}
//尾插法
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
2.3超陆、HashMap
2.3.1牺弹、屬性
//默認(rèn)初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量，指的是數(shù)組大小
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認(rèn)的負(fù)載因子时呀，據(jù)說是根據(jù)泊松分布算出來的(不負(fù)責(zé)該說法的準(zhǔn)確性张漂，手動(dòng)狗頭)
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//鏈表的大小超過該值就會(huì)變?yōu)榧t黑樹
static final int TREEIFY_THRESHOLD = 8;
//紅黑的大小小于該值就會(huì)變?yōu)殒湵?static final int UNTREEIFY_THRESHOLD = 6;
//暫時(shí)不清楚該值的作用
static final int MIN_TREEIFY_CAPACITY = 64;
//實(shí)際存儲(chǔ)數(shù)據(jù)
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
//map的實(shí)際大小
transient int size;
// map被操作的次數(shù)
transient int modCount;
//The next size value at which to resize (capacity * load factor).
int threshold;
//用戶指定的負(fù)載因子
final float loadFactor;
2.3.2、put方法
/**
*實(shí)際是調(diào)私有方法putVal
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
*計(jì)算key的hash值
*
*一篇很詳細(xì)的文章介紹map的hash計(jì)算為什么這么設(shè)計(jì)：https://www.zhihu.com/question/20733617
*核心目的：為了提高 存儲(chǔ)key-value的數(shù)組下標(biāo)位置 的隨機(jī)性 & 分布均勻性谨娜，盡量避免出現(xiàn)hash值沖突航攒。
* 即：對(duì)于不同key，存儲(chǔ)的數(shù)組下標(biāo)位置要盡可能不一樣
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* 該函數(shù)主要做幾件事：
* 1.數(shù)組不存在時(shí)或者大小為0時(shí)趴梢，擴(kuò)容
* 2.尾插法插入數(shù)據(jù)
* 3.判斷是否需要(紅黑樹->鏈表漠畜，鏈表->紅黑樹)
*/
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; //數(shù)組不存在時(shí)或者大小為0時(shí)，重新計(jì)算大小
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); //數(shù)組下標(biāo)i沒有值時(shí)(也就是沒有沖突時(shí))坞靶，直接放入數(shù)據(jù)
else {
/**
*發(fā)生了hash沖突憔狞，分情況處理
*
*/
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //key是一樣的，直接返回
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);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
/**
*該函數(shù)實(shí)現(xiàn)map的擴(kuò)容操作
*1.每次擴(kuò)容為原來的兩倍大小
*2.重建hash表(耗時(shí)最多的部分)
*3.
*
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0; //新的容量彰阴，新的擴(kuò)容閾值
if (oldCap > 0) {
//最大值了躯喇，無法再擴(kuò)容了
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//擴(kuò)容兩倍，閾值變?yōu)閮杀? else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else {
//使用默認(rèn)值進(jìn)行初始化硝枉，newCap=16廉丽，newThr=12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
/**
*重頭戲：重建hash表
*
*/
@SuppressWarnings({"rawtypes","unchecked"})
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;
//沒有尾巴時(shí)，直接重新計(jì)算下標(biāo)妻味，放入新數(shù)組
if (e.next == null)
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è)if計(jì)算的原因：
*這里有兩個(gè)前提：
*1.hashMap計(jì)算數(shù)組下標(biāo)的公式：key.hash & (table.length-1)
*2.table.lenght的值一定是偶數(shù)
*
*這里我們假設(shè)oldCap = 16.則(table.lenght-1)=15
*那么newCap就=32正压，則(table.lenght-1)=31
*
*計(jì)算數(shù)組下標(biāo)就像下面這樣:
*x,????(數(shù)據(jù)的hash值)
*0,1111(15)
*1,1111(31)
*可以看出來，重hash時(shí)责球，完全取決于數(shù)據(jù)的hash多出來的一位(也就是x)是0還是
*1焦履。是0則在新數(shù)組的下標(biāo)就不變，是1則在新數(shù)組的下標(biāo)為oldCap+原下標(biāo)
*/
//還是原來的下標(biāo)
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//原來的下標(biāo)+oldCap
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;
}
//待續(xù)：鏈表轉(zhuǎn)紅黑樹
