摘要：底層實(shí)現(xiàn)是對(duì)象數(shù)組，優(yōu)點(diǎn)是時(shí)間為，缺點(diǎn)是和時(shí)間為，需要留意的是擴(kuò)容的過程以及的算法本節(jié)參考源碼中放最新的源碼為，組成鏈表或紅黑樹定義從整體上看，底層的存儲(chǔ)結(jié)構(gòu)是基于數(shù)組和鏈表實(shí)現(xiàn)的。實(shí)現(xiàn)了所謂的線程安全，在很多方法上都加上了。
ArrayList
ArrayList底層實(shí)現(xiàn)是對(duì)象數(shù)組，優(yōu)點(diǎn)是set、get時(shí)間為O(1)，缺點(diǎn)是add和remove時(shí)間為O(n)，需要留意的是擴(kuò)容的過程以及remove的算法
public class MyArrayList{
private static final int DEFAULT_CAPACITY = 10;
Object[] elementData;
int size;
public int size(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
public boolean contains(Object o){
return indexOf >= 0;
}
public E remove(int index){
rangeCheck(index);
E oldValue = elementData[index];
int numMoved = size - index - 1;
if(numMoved > 0){
System.copyarray(elementData, index + 1, elementData, index, numMoved);
}
elementData[--size] = null;
return oldValue;
}
public boolean remove(Object o){
if(o == null){
for(int i = 0; i < size; i++){
fastRemove(i);
return true;
}
}else{
for(int i = 0; i < size; i++){
fastRemove(i);
return true;
}
}
return false;
}
public void fastRemove(int index){
int numMoved = size - index - 1;
if(numMoved > 0){
System.copyarray(elementData, index + 1, elementData, index, numMoved);
}
elementData[--size] = null;
}
public boolean add(E e){
ensureCapacity(size + 1);
elementData[size++] = e;
return true;
}
public E get(int index){
rangeCheck(index);
return elementData[index];
}
public E set(int index, E element){
rangeCheck(index);
E oldValue = elementData[index];
elementData[index] = element;
return oldValue;
}
public void ensureCapacity(int minCapacity){
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
if(minCapacity - elementData.length > 0){
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);
}
private int hugeCapacity(int minCapacity){
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(index){
return "Size:" + size + ", Index:" + index;
}
public int indexOf(Object o){
if(o == null){
for(int i = 0; i < size; i++){
if(elementData[i] == null){
return i;
}
}
}else{
for(int i = 0; i < size; i++){
if(elementData[i].equals(o)){
return i;
}
}
}
return -1;
}
}
本節(jié)參考 jdk1.8 源碼
HashMap
table中放Entry（最新的JDK源碼為Node），Entry組成鏈表或紅黑樹
Entry(Node定義)
static class Node implements Map.Entry{
final int hash;
final K key;
V value;
Node next;
Node(int hash, K key, V value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
從整體上看，HashMap底層的存儲(chǔ)結(jié)構(gòu)是基于數(shù)組和鏈表實(shí)現(xiàn)的。對(duì)于每一個(gè)要存入HashMap的鍵值對(duì)（Key-Value Pair），通過計(jì)算Key的hash值來決定存入哪個(gè)數(shù)組單元（bucket），為了處理hash沖突，每個(gè)數(shù)組單元實(shí)際上是一條Entry單鏈表的頭結(jié)點(diǎn)，其后引申出一條單鏈表。
存取過程
取值過程大致如下：先檢查table中的頭結(jié)點(diǎn)，table中如果是樹，從樹中找；不然從鏈表中找
public V get(Object key){
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node getNode(int hash, Object key){
Node[] tab; Node first, e; int n; K k;
//桶中頭結(jié)點(diǎn)不為空，檢查頭結(jié)點(diǎn)
if((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null){
if(first.hash == hash &&
((k = first.key)) == key || (key != null && key.equals(k))))
return first;
if((e = first.next) != null){
//如果為紅黑樹，按樹遍歷
if(first instanceof TreeNode)
return ((treeNode) 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;
}
添加鍵值對(duì)put(key,value)的過程：
1，判斷鍵值對(duì)數(shù)組tab[]是否為空或?yàn)閚ull，否則以默認(rèn)大小resize()；
2，根據(jù)鍵值key計(jì)算hash值得到插入的數(shù)組索引i，如果tab[i]==null，直接新建節(jié)點(diǎn)添加，否則轉(zhuǎn)入3
3，判斷當(dāng)前數(shù)組中處理hash沖突的方式為鏈表還是紅黑樹(check第一個(gè)節(jié)點(diǎn)類型即可),分別處理
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[] tab;
Node 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)
tab[i] = newNode(hash, key, value, null);
/*表示有沖突,開始處理沖突*/
else {
Node 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)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的長度，如果不足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，就是key的Value存在
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;//返回存在的Value值
}
}
++modCount;
/*如果當(dāng)前大小大于門限，門限原本是初始容量*0.75*/
if (++size > threshold)
resize();//擴(kuò)容兩倍
afterNodeInsertion(evict);
return null;
}
擴(kuò)容機(jī)制resize()
構(gòu)造hash表時(shí)，如果不指明初始大小，默認(rèn)大小為16（即Node數(shù)組大小16），如果Node[]數(shù)組中的元素達(dá)到（填充比*Node.length）重新調(diào)整HashMap大小 變?yōu)樵瓉?倍大小,擴(kuò)容很耗時(shí),需要重新計(jì)算bucket的位置。
為什么通過計(jì)算h & (length-1)來獲得bucket的位置，而不是通過計(jì)算h % length？
實(shí)際上，在HashMap中，h & (length-1) == h % length，但是需要一個(gè)前提：length必須滿足是2的冪。這也正是在解釋DEFAULT_INITIAL_CAPACITY和HashMap構(gòu)造方法時(shí)強(qiáng)調(diào)的HashMap的bucket容量必須是2的冪。當(dāng)length是2的冪，那么length的二進(jìn)制數(shù)可以表示為1000...000，因此length - 1的二進(jìn)制數(shù)為0111...111，當(dāng)h與length - 1位與時(shí)，除了h的最高位的被修改為0，其余位均保持不變，這也正是實(shí)現(xiàn)了h % length的效果。只是相比于h % length，h & (length-1)的效率會(huì)更高。
HashMap的bucket容量必須為2的冪的另一個(gè)重要原因是一旦滿足此條件，那么length即為偶數(shù)，length - 1便為奇數(shù)，所以length - 1的最后一位必為1。因此，h & (length - 1)得到的值既可能是奇數(shù)，也可能是偶數(shù)，這確保了散列的均勻性。如果length - 1是偶數(shù)，那么h & (length - 1)得到的值必為偶數(shù)，那么HashMap的空間便浪費(fèi)了一半。
final Node[] resize() {
Node[] 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;
}
/*把新表的長度設(shè)置為舊表長度的兩倍，newCap=2*oldCap*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
/*把新表的門限設(shè)置為舊表門限的兩倍，newThr=oldThr*2*/
newThr = oldThr << 1; // double threshold
}
/*如果舊表的長度的是0，就是說第一次初始化表*/
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"})
/*下面開始構(gòu)造新表，初始化表中的數(shù)據(jù)*/
Node[] newTab = (Node[])new Node[newCap];
table = newTab;//把新表賦值給table
if (oldTab != null) {//原表不是空要把原表中數(shù)據(jù)移動(dòng)到新表中
/*遍歷原來的舊表*/
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)//說明這個(gè)node沒有鏈表直接放在新表的e.hash & (newCap - 1)位置
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
/*如果e后邊有鏈表,到這里表示e后面帶著個(gè)單鏈表，需要遍歷單鏈表，將每個(gè)結(jié)點(diǎn)重*/
else { // preserve order保證順序
////新計(jì)算在新表的位置，并進(jìn)行搬運(yùn)
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node 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) {//lo隊(duì)不為null，放在新表原位置
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {//hi隊(duì)不為null，放在新表j+oldCap位置
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
HashMap的總結(jié)
本節(jié)參考
HashMap的默認(rèn)大小為16，即桶數(shù)組的默認(rèn)長度為16；
HashMap的默認(rèn)裝載因子是0.75；
HashMap內(nèi)部的桶數(shù)組存儲(chǔ)的是Entry對(duì)象，也就是鍵值對(duì)對(duì)象。
構(gòu)造器支持指定初始容量和裝載因子，為避免數(shù)組擴(kuò)容帶來的性能問題，建議根據(jù)需求指定初始容量。裝載因子盡量不要修改，0.75是個(gè)比較靠譜的值。
桶數(shù)組的長度始終是2的整數(shù)次方（大于等于指定的初始容量），這樣做可以減少?zèng)_突概率，提高查找效率。（可以從indexfor函數(shù)中看出，h&(length-1),若length為奇數(shù)，length-1為偶數(shù)那么h&(length-1)結(jié)果的最后一位必然為0，也就是說所有鍵都被散列到數(shù)組的偶數(shù)下標(biāo)位置,這樣會(huì)浪費(fèi)近一半空間。另外，length為2的整數(shù)次方也保證了h&(length-1)與h%length等效）.
HashMap接受null鍵；
HashMap不允許鍵重復(fù)，但是值是可以重復(fù)的。若鍵重復(fù)，那么新值會(huì)覆蓋舊值。
HashMap通過鏈表法解決沖突問題，每個(gè)Entry都有一個(gè)next指針指向下一個(gè)Entry，沖突元素（不是鍵相同，而是hash值相同）會(huì)構(gòu)成一個(gè)鏈表。并且最新插入的鍵值對(duì)始終位于鏈表首部。
當(dāng)容量超過閾值（threshold）時(shí),會(huì)發(fā)生擴(kuò)容，擴(kuò)容后的數(shù)組是原數(shù)組的兩倍。擴(kuò)容操作需要開辟新數(shù)組，并對(duì)原數(shù)組中所有鍵值對(duì)重新散列，非常耗時(shí)。我們應(yīng)該盡量避免HashMap擴(kuò)容。
HashMap非線程安全。
線程安全與HashTable
HashMap是一個(gè)非線程安全的，因此適合運(yùn)用在單線程環(huán)境下。如果是在多線程環(huán)境，可以通過Collections的靜態(tài)方法synchronizedMap獲得線程安全的HashMap，如下代碼所示。
Map map = Collections.synchronizedMap(new HashMap());
HashTable和HashMap底層采用相同的存儲(chǔ)結(jié)構(gòu)，在很多方法的實(shí)現(xiàn)上二者的思路基本一致。最主要的區(qū)別主要有兩點(diǎn)。
HashTable實(shí)現(xiàn)了所謂的線程安全，在HashTable很多方法上都加上了synchronized。
在HashMap的分析中，我們發(fā)現(xiàn)當(dāng)我們新增鍵值對(duì)時(shí)，HashMap是允許Key和Value均為null。但是HashTable不允許Key或Value為null，關(guān)于這一點(diǎn)我們可以通過查看HashTable源碼得知。
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) { // 若value為空則拋出NullPointerException。
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
int hash = key.hashCode(); // 若key為空則拋出NullPointerException。
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry entry = (Entry)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;
}
關(guān)于HashSet
HashSet基于HashMap實(shí)現(xiàn)；而Map是鍵值對(duì)形式的，因此構(gòu)造一個(gè)PRESENT假裝為值。
private static final Object PRESENT = new Object();
另外，
HashSet無序；允許值為null；非線程安全；底層增刪等操作基于HashMap實(shí)現(xiàn)；
LinkedHashSet有序；允許值為null；非線程安全；依賴于HashSet，底層增刪等操作基于LinkedHashMap實(shí)現(xiàn)；
TreeSet有序；不允許為null；非線程安全；底層增刪等操作基于TreeMap實(shí)現(xiàn)。
本節(jié)參考 https://segmentfault.com/a/11...
http://blog.csdn.net/tuke_tuk...
