- ArrayList
1.初始化：
List<Long> list = new ArrayList<>();
List<Long> list2 = new ArrayList<>(9);
第一種初始化方式的源碼：
/**
* 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
/**
* 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用于真正存儲數(shù)據(jù)，雖然說Constructs an empty list with an initial capacity of ten但是我們可以看到其實DEFAULTCAPACITY_EMPTY_ELEMENTDATA是空的數(shù)組，按照注釋說的，來看看來添加第一個元素后是否容量變?yōu)榱?0：
private int size;
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
發(fā)現(xiàn)size沒有初始化，默認為0，從名字可以看出ensureCapacityInternal是用來確定容量大小的方法：
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
還記得當時無參構(gòu)造方法this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;的操作么？這里就用于區(qū)分初始化是否定義了集合長度，這里返回了DEFAULT_CAPACITY為10，繼續(xù)：
protected transient int modCount = 0;
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
modCount是個啥？通過看源碼的注釋了解到，原來是記錄一下結(jié)構(gòu)變化次數(shù)的，例如list的size變化，以及迭代過程中的快速失敗。接下來看看這個grow方法：
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
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);
}
擴容方法，可以看到oldCapacity + (oldCapacity >> 1)操作，將原來容量擴至1.5倍,elementData = Arrays.copyOf(elementData, newCapacity);將elementData擴容至newCapacity大小，其余擴容的元素為null。
第二種初始化在執(zhí)行構(gòu)造方法時稍有不同：
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);
}
}
之后的集合操作和之前就一樣了。
2.add方法
插入隊尾的上文已有解析，直接看插入特定位置的add方法，rangeCheckForAdd方法就是檢查一下和size的關(guān)系，如果超出size大小拋出IndexOutOfBoundsException異常，ensureCapacityInternal方法上文已有解析，重點來看System.arraycopy方法，點擊一看是個native方法，作用是將原數(shù)組前index和后面的斷開，由elementData[index] = element;插入index位置的元素，remove方法和add方法類似不再細述。
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
trimToSize方法去掉預(yù)留位置
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
- LinkedList
先來看看LinkedList
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
原來底層使用Node來實現(xiàn),雙向鏈表
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;
}
}
1.初始化
有參構(gòu)造函數(shù)將集合作為入?yún)ⅲㄟ^addAll()方法
/**
* Constructs an empty list.
*/
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//構(gòu)建雙向鏈表
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
index表示目前節(jié)點個數(shù)，默認0，checkPositionIndex檢查index是否超過節(jié)點數(shù)，不通過拋出IndexOutOfBoundsException異常，Node<E> pred, succ;構(gòu)造局部變量，一個用來指向當前操作的節(jié)點，這相當于一個游標。另一個用來標識插入的位置的點。最后修改size長度以及修改次數(shù)加一。
2.添加元素
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++;
}
修改last節(jié)點，構(gòu)建新節(jié)點并賦值給last，增加size和修改次數(shù)。
3.刪除元素
不管是刪除指定元素內(nèi)容還是index，都會調(diào)用unlink方法：
/**
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
可以看到將前一個節(jié)點prev的后一個節(jié)點直接定義成next，跳過了當前的節(jié)點，這也是為什么進行元素的插入、刪除效率比ArrayList高的原因。
- HashSet/HashMap
1.HashSet初始化
HashSet有5種初始化方式：
private transient HashMap<E,Object> map;
public HashSet() {
map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
// 對HashSet的操作其實都是對HashMap中Key的操作，如添加方法就是放進去一個map，Key對應(yīng)值，value就放個空的對象。
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
既然底層都是HashMap，先拋出一些結(jié)論：
- HashMap 初始容量是16,擴容方式為2N;
- 裝載因子0.75是提高空間利用率和減少查詢成本的折中，主要是泊松分布，發(fā)生hash碰撞概率最?。?br> 那我們來看一下HashMap無參構(gòu)造函數(shù)：
final float loadFactor;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
2.添加元素put方法
裝載因子0.75，但是沒有定義容量，繼續(xù)看是否在put方法中會重新定義:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
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);
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;
}
果然，注意如果節(jié)點數(shù)組為空的話有個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;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
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 { // zero initial threshold signifies using defaults
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;
@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;
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;
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;
}
一開始table的size為0，所以會執(zhí)行newCap = DEFAULT_INITIAL_CAPACITY;并計算下次需要擴容的容量（每次都會變?yōu)樵瓉泶笮〉?倍）：
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
threshold = newThr;
再回到put方法，可知HashMap的結(jié)構(gòu)底層是Node<K,V>[] tab即鏈表+數(shù)組，其中if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);可以翻譯為如果沒有Hash沖突就將Node對象創(chuàng)建出來，如果數(shù)組最大下標為15,那么不管Hash(key)是多少都不會大于15，也就不會數(shù)組越界，再來看一下Node結(jié)構(gòu)：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
... ...
}
一個節(jié)點由key的hash值，key，value，下一個node組成，如果put一個元素，先會根據(jù)key的hash值取到Node<K,V>[] table中的位置，如果為null就保存，如果有，則通過key.equals(k)判斷，如果是更新value，不是則在此node的next新建node：
image.png
如果Node<K,V>[] table中存放的元素超過容量（默認的負載因子大小為0.75）當一個map填滿了75%的bucket時候，將會創(chuàng)建原來HashMap大小的兩倍的Node<K,V>[]，來重新調(diào)整map的大小，并將原來的對象放入新的Node<K,V>[]中，稱為rehashing。
3.獲取元素get方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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;
}
首先根據(jù)hash(key)找到Node<K,V>[] tab中的node，再根據(jù)key遍歷鏈表，取出對應(yīng)node，獲取node，再獲取value。移除也類似，不再贅述。
另外說HashMap不是線程安全的，主要原因就在擴容（resize）方法上，擴容時機：
- 總桶數(shù)*加載因子的時候會觸發(fā)擴容；
- 當某個桶中的鏈表長度達到8進行鏈表扭轉(zhuǎn)為紅黑樹的時候，會檢查總桶數(shù)是否小于64，如果總桶數(shù)小于64也會進行擴容；
- 當new完HashMap之后，第一次往HashMap進行put操作的時候；
4.線程不安全問題
HashMap 在并發(fā)時可能出現(xiàn)的問題主要是兩方面：
- put的時候?qū)е碌亩嗑€程數(shù)據(jù)不一致
比如有兩個線程A和B，首先A希望插入一個key-value對到HashMap中，首先計算記錄所要落到的 hash桶的索引坐標，然后獲取到該桶里面的鏈表頭結(jié)點，此時線程A的時間片用完了，而此時線程B被調(diào)度得以執(zhí)行，和線程A一樣執(zhí)行，只不過線程B成功將記錄插到了桶里面，假設(shè)線程A插入的記錄計算出來的 hash桶索引和線程B要插入的記錄計算出來的 hash桶索引是一樣的，那么當線程B成功插入之后，線程A再次被調(diào)度運行時，它依然持有過期的鏈表頭但是它對此一無所知，以至于它認為它應(yīng)該這樣做，如此一來就覆蓋了線程B插入的記錄，這樣線程B插入的記錄就憑空消失了，造成了數(shù)據(jù)不一致的行為。 - resize而引起死循環(huán)（JDK1.8已經(jīng)不會出現(xiàn)該問題）
這種情況發(fā)生在JDK1.7 中HashMap自動擴容時，當2個線程同時檢測到元素個數(shù)超過 數(shù)組大小 × 負載因子。此時2個線程會在put()方法中調(diào)用了resize()，兩個線程同時修改一個鏈表結(jié)構(gòu)會產(chǎn)生一個循環(huán)鏈表（JDK1.7中，會出現(xiàn)resize前后元素順序倒置的情況）。接下來再想通過get()獲取某一個元素，就會出現(xiàn)死循環(huán)。
- HashTable
和HashMap不同，它是線程安全的，讓我們一起來看一下：
1.初始化
無參的初始化默認容量11，裝載因子0.75，new Entry數(shù)組，設(shè)置容量閾值，裝載因子
public Hashtable() {
this(11, 0.75f);
}
public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
2.添加元素
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
從這里可以看到和HashMap的區(qū)別其中之一就是這里是synchronized方法，這也是它線程安全的原因。和HashMap相比，key和value都不能為null，且在put過程中會鎖住table，所以效率低下。
2.擴容
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}
可以看到，這里容量擴大為原來的兩倍+1int newCapacity = (oldCapacity << 1) + 1;
現(xiàn)在基本都用ConcurrentHashMap代替HashTable,因為其具有更好的同步性能更好，因為它僅僅根據(jù)同步級別對map的一部分進行上鎖，但是HashTable提供更強的線程安全性。
- ConcurrentHashMap
1.初始化
public ConcurrentHashMap() {
}
/**
* Creates a new, empty map with an initial table size
* accommodating the specified number of elements without the need
* to dynamically resize.
*
* @param initialCapacity The implementation performs internal
* sizing to accommodate this many elements.
* @throws IllegalArgumentException if the initial capacity of
* elements is negative
*/
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}
private static final int tableSizeFor(int c) {
int n = c - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
這里指定大小的初始化有些迷，分析過后發(fā)現(xiàn)，不管你長度初始化為多少，初始化的長度都會變?yōu)楸饶阍O(shè)置值的2倍最近的2的次冪。如16->32,62->128
2.put元素
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
// onlyIfAbsent:如果當前位置已存在一個值，是否替換，false是替換，true是不替換
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
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);
else {
V oldVal = null;
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;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
分析一下：如果tab為空的話，會調(diào)用initTable初始化方法，默認容量16；else if ((f = tabAt(tab, i = (n - 1) & hash)) == null)如果新增元素放入的目標節(jié)點為空（位置通過"數(shù)組長度減一的數(shù)值"和"key的哈希值"相與得到），進行CAS判斷、創(chuàng)建節(jié)點，這樣可以省去加鎖的操作，優(yōu)化性能（調(diào)用native方法實現(xiàn)原子性操作CAS操作，用來通過無鎖的方式線程安全地修改屬性的值。）。else if ((fh = f.hash) == MOVED)表示如果節(jié)點是forwarding nodes節(jié)點的話(這種節(jié)點只用在resize的過程中)，進行協(xié)助擴容操作。else后為數(shù)組的目標位置已存在節(jié)點，此時需要把目標節(jié)點放入目標位置的鏈表或者紅黑樹中?？梢钥吹?，synchronized (f)這里只鎖了table的一個位置，因此和HashTable相比效率明顯要高。if (tabAt(tab, i) == f) {再次判斷這個節(jié)點在判斷和加鎖期間沒有被修改過。else if (f instanceof TreeBin) {如果是紅黑樹，則按紅黑樹插入值的方式進行插入。if (binCount != 0) {如果binCount不為0（表示已經(jīng)進行插入操作了），static final int TREEIFY_THRESHOLD = 8;如果鏈表深度大于8，觸發(fā)擴容或者紅黑樹的轉(zhuǎn)化。
/**
* Replaces all linked nodes in bin at given index unless table is
* too small, in which case resizes instead.
*/
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) {
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
synchronized (b) {
if (tabAt(tab, index) == b) {
TreeNode<K,V> hd = null, tl = null;
for (Node<K,V> e = b; e != null; e = e.next) {
TreeNode<K,V> p =
new TreeNode<K,V>(e.hash, e.key, e.val,
null, null);
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
紅黑樹結(jié)構(gòu)：
static final class TreeNode<K,V> extends Node<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next,
TreeNode<K,V> parent) {
super(hash, key, val, next);
this.parent = parent;
}
...
(持續(xù)更新、、、)
