一 、list set map的關(guān)系圖
List,Set都是繼承自Collection接口，map沒有如圖
set和list的對(duì)比
List特點(diǎn)：元素有放入順序，元素可重復(fù)
Set特點(diǎn)：元素?zé)o放入順序，元素不可重復(fù)，重復(fù)元素會(huì)覆蓋掉，（由HashCode決定）
set只能用迭代，因?yàn)樗麩o序，無法用下標(biāo)來取得想要的值。
Set：檢索元素效率低下，刪除和插入效率高，插入和刪除不會(huì)引起元素位置改變。
List：和數(shù)組類似，List可以動(dòng)態(tài)增長，查找元素效率高，插入刪除元素效率低，因?yàn)闀?huì)引起其他元素位置改變。
HashSet hashMap關(guān)系
Map適合儲(chǔ)存鍵值對(duì)的數(shù)據(jù)
1 HashSet是set的一個(gè)實(shí)現(xiàn)類,hashMap是Map的一個(gè)實(shí)現(xiàn)類,同時(shí)hashMap是hashTable的替代品
2 HashSet以對(duì)象作為元素(不重復(fù)）,而HashMap以(key-value)的一組對(duì)象作為元素
HashMap可以看作三個(gè)視圖：key的Set，value的Collection，Entry的Set。
HashSet內(nèi)部就是使用Hashmap實(shí)現(xiàn)的，和Hashmap不同的是它不需要Key和Value兩 值。
Arraylist：
優(yōu)點(diǎn)：ArrayList是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu),因?yàn)榈刂愤B續(xù)，一旦數(shù)據(jù)存儲(chǔ)好了，查詢操作效率會(huì)比較高（在內(nèi)存里是連著放的）。
缺點(diǎn)：因?yàn)榈刂愤B續(xù)， ArrayList要移動(dòng)數(shù)據(jù),所以插入和刪除操作效率比較低。
LinkedList：
優(yōu)點(diǎn)：LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu),地址是任意的，所以在開辟內(nèi)存空間的時(shí)候不需要等一個(gè)連續(xù)的地址，對(duì)于新增和刪除操作add和remove，LinedList比較占優(yōu)勢(shì)。LinkedList 適用于要頭尾操作或插入指定位置的場(chǎng)景
缺點(diǎn)：因?yàn)長inkedList要移動(dòng)指針,所以查詢操作性能比較低。
TreeSet 是二差樹（紅黑樹的樹據(jù)結(jié)構(gòu)）實(shí)現(xiàn)的,Treeset中的數(shù)據(jù)是自動(dòng)排好序的，不允許放入null值
HashSet 是哈希表實(shí)現(xiàn)的,HashSet中的數(shù)據(jù)是無序的，可以放入null，但只能放入一個(gè)null，兩者中的值都不能重復(fù)，就如數(shù)據(jù)庫中唯一約束
HashSet要求放入的對(duì)象必須實(shí)現(xiàn)HashCode()方法，放入的對(duì)象，是以hashcode碼作為標(biāo)識(shí)的，而具有相同內(nèi)容的String對(duì)象，hashcode是一樣，所以放入的內(nèi)容不能重復(fù)。但是同一個(gè)類的對(duì)象可以放入不同的實(shí)例
HashMap：基于哈希表實(shí)現(xiàn)。優(yōu)化HashMap空間的使用，您可以調(diào)優(yōu)初始容量和負(fù)載因子。
適用場(chǎng)景
當(dāng)需要對(duì)數(shù)據(jù)進(jìn)行對(duì)此訪問的情況下選用ArrayList，當(dāng)需要對(duì)數(shù)據(jù)進(jìn)行多次增加刪除修改時(shí)采用LinkedList。
Vector是線程同步的，所以它也是線程安全的，而ArrayList是線程異步的，是不安全的。如果不考慮到線程的安全因素，一般用ArrayList效率比較高。
如果集合中的元素的數(shù)目大于目前集合數(shù)組的長度時(shí)，在集合中使用數(shù)據(jù)量比較大的數(shù)據(jù)，用Vector有一定的優(yōu)勢(shì)。
HashSet是基于Hash算法實(shí)現(xiàn)的，其性能通常都優(yōu)于TreeSet。為快速查找而設(shè)計(jì)的Set，我們通常都應(yīng)該使用HashSet，在我們需要排序的功能時(shí)，我們才使用TreeSet。
LinkHashMap的源碼分析
繼承自HashMap，一個(gè)有序的Map接口實(shí)現(xiàn)，這里的有序指的是元素可以按插入順序或訪問順序排列；
與HashMap的異同：同樣是基于散列表實(shí)現(xiàn)，區(qū)別是，LinkedHashMap內(nèi)部多了一個(gè)雙向循環(huán)鏈表的維護(hù)，該鏈表是有序的，可以按元素插入順序或元素最近訪問順序(LRU)排列，
LinkedHashMap=散列表+循環(huán)雙向鏈表
第一張圖是LinkedHashMap的數(shù)據(jù)結(jié)構(gòu)，包含散列表和循環(huán)雙向鏈表，由于循環(huán)雙向鏈表線條太多了，不好畫，簡(jiǎn)單的畫了一個(gè)節(jié)點(diǎn)(黃色圈出來的)示意一下，注意左邊的紅色箭頭引用為Entry節(jié)點(diǎn)對(duì)象的next引用(散列表中的單鏈表)，綠色線條為Entry節(jié)點(diǎn)對(duì)象的before, after引用(循環(huán)雙向鏈表的前后引用)；
第二張圖專門把循環(huán)雙向鏈表抽取出來，直觀一點(diǎn)，注意該循環(huán)雙向鏈表的頭部存放的是最久訪問的節(jié)點(diǎn)或最先插入的節(jié)點(diǎn)，尾部為最近訪問的或最近插入的節(jié)點(diǎn)，迭代器遍歷方向是從鏈表的頭部開始到鏈表尾部結(jié)束，在鏈表尾部有一個(gè)空的header節(jié)點(diǎn)，該節(jié)點(diǎn)不存放key-value內(nèi)容，為LinkedHashMap類的成員屬性，循環(huán)雙向鏈表的入口；
插入刪除、操作如下圖，應(yīng)該挺好理解的，鏈表的操作
源碼
package java.util;
import java.io.*;
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
private static final long serialVersionUID = 3801124242820219131L;
/**
* 雙向循環(huán)鏈表， 頭結(jié)點(diǎn)(空節(jié)點(diǎn))
*/
private transient Entry<K,V> header;
/**
* accessOrder為true時(shí)，按訪問順序排序，false時(shí)，按插入順序排序
*/
private final boolean accessOrder;
/**
* 生成一個(gè)空的LinkedHashMap,并指定其容量大小和負(fù)載因子，
* 默認(rèn)將accessOrder設(shè)為false，按插入順序排序
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
/**
* 生成一個(gè)空的LinkedHashMap,并指定其容量大小，負(fù)載因子使用默認(rèn)的0.75，
* 默認(rèn)將accessOrder設(shè)為false，按插入順序排序
*/
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
/**
* 生成一個(gè)空的HashMap,容量大小使用默認(rèn)值16，負(fù)載因子使用默認(rèn)值0.75
* 默認(rèn)將accessOrder設(shè)為false，按插入順序排序.
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
/**
* 根據(jù)指定的map生成一個(gè)新的HashMap,負(fù)載因子使用默認(rèn)值，初始容量大小為Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY)
* 默認(rèn)將accessOrder設(shè)為false，按插入順序排序.
*/
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super(m);
accessOrder = false;
}
/**
* 生成一個(gè)空的LinkedHashMap,并指定其容量大小和負(fù)載因子，
* 默認(rèn)將accessOrder設(shè)為true，按訪問順序排序
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
/**
* 覆蓋HashMap的init方法，在構(gòu)造方法、Clone、readObject方法里會(huì)調(diào)用該方法
* 作用是生成一個(gè)雙向鏈表頭節(jié)點(diǎn)，初始化其前后節(jié)點(diǎn)引用
*/
@Override
void init() {
header = new Entry<>(-1, null, null, null);
header.before = header.after = header;
}
/**
* 覆蓋HashMap的transfer方法，性能優(yōu)化，這里遍歷方式不采用HashMap的雙重循環(huán)方式
* 而是直接通過雙向鏈表遍歷Map中的所有key-value映射
*/
@Override
void transfer(HashMap.Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//遍歷舊Map中的所有key-value
for (Entry<K,V> e = header.after; e != header; e = e.after) {
if (rehash)
e.hash = (e.key == null) ? 0 : hash(e.key);
//根據(jù)新的數(shù)組長度，重新計(jì)算索引，
int index = indexFor(e.hash, newCapacity);
//插入到鏈表表頭
e.next = newTable[index];
//將e放到索引為i的數(shù)組處
newTable[index] = e;
}
}
/**
* 覆蓋HashMap的transfer方法，性能優(yōu)化，這里遍歷方式不采用HashMap的雙重循環(huán)方式
* 而是直接通過雙向鏈表遍歷Map中的所有key-value映射,
*/
public boolean containsValue(Object value) {
// Overridden to take advantage of faster iterator
if (value==null) {
for (Entry e = header.after; e != header; e = e.after)
if (e.value==null)
return true;
} else {
for (Entry e = header.after; e != header; e = e.after)
if (value.equals(e.value))
return true;
}
return false;
}
/**
* 通過key獲取value，與HashMap的區(qū)別是：當(dāng)LinkedHashMap按訪問順序排序的時(shí)候，會(huì)將訪問的當(dāng)前節(jié)點(diǎn)移到鏈表尾部(頭結(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn))
*/
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
/**
* 調(diào)用HashMap的clear方法，并將LinkedHashMap的頭結(jié)點(diǎn)前后引用指向自己
*/
public void clear() {
super.clear();
header.before = header.after = header;
}
/**
* LinkedHashMap節(jié)點(diǎn)對(duì)象
*/
private static class Entry<K,V> extends HashMap.Entry<K,V> {
// 節(jié)點(diǎn)前后引用
Entry<K,V> before, after;
//構(gòu)造函數(shù)與HashMap一致
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
/**
* 移除節(jié)點(diǎn)，并修改前后引用
*/
private void remove() {
before.after = after;
after.before = before;
}
/**
* 將當(dāng)前節(jié)點(diǎn)插入到existingEntry的前面
*/
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
/**
* 在HashMap的put和get方法中，會(huì)調(diào)用該方法，在HashMap中該方法為空
* 在LinkedHashMap中，當(dāng)按訪問順序排序時(shí)，該方法會(huì)將當(dāng)前節(jié)點(diǎn)插入到鏈表尾部(頭結(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn))，否則不做任何事
*/
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//當(dāng)LinkedHashMap按訪問排序時(shí)
if (lm.accessOrder) {
lm.modCount++;
//移除當(dāng)前節(jié)點(diǎn)
remove();
//將當(dāng)前節(jié)點(diǎn)插入到頭結(jié)點(diǎn)前面
addBefore(lm.header);
}
}
void recordRemoval(HashMap<K,V> m) {
remove();
}
}
//迭代器
private abstract class LinkedHashIterator<T> implements Iterator<T> {
//初始化下個(gè)節(jié)點(diǎn)引用
Entry<K,V> nextEntry = header.after;
Entry<K,V> lastReturned = null;
/**
* 用于迭代期間快速失敗行為
*/
int expectedModCount = modCount;
//鏈表遍歷結(jié)束標(biāo)志，當(dāng)下個(gè)節(jié)點(diǎn)為頭節(jié)點(diǎn)的時(shí)候
public boolean hasNext() {
return nextEntry != header;
}
//移除當(dāng)前訪問的節(jié)點(diǎn)
public void remove() {
//lastReturned會(huì)在nextEntry方法中賦值
if (lastReturned == null)
throw new IllegalStateException();
//快速失敗機(jī)制
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
LinkedHashMap.this.remove(lastReturned.key);
lastReturned = null;
//迭代器自身刪除節(jié)點(diǎn)，并不是其他線程修改Map結(jié)構(gòu)，所以這里要修改expectedModCount
expectedModCount = modCount;
}
//返回鏈表下個(gè)節(jié)點(diǎn)的引用
Entry<K,V> nextEntry() {
//快速失敗機(jī)制
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//鏈表為空情況
if (nextEntry == header)
throw new NoSuchElementException();
//給lastReturned賦值，最近一個(gè)從迭代器返回的節(jié)點(diǎn)對(duì)象
Entry<K,V> e = lastReturned = nextEntry;
nextEntry = e.after;
return e;
}
}
//key迭代器
private class KeyIterator extends LinkedHashIterator<K> {
public K next() { return nextEntry().getKey(); }
}
//value迭代器
private class ValueIterator extends LinkedHashIterator<V> {
public V next() { return nextEntry().value; }
}
//key-value迭代器
private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() { return nextEntry(); }
}
// 返回不同的迭代器對(duì)象
Iterator<K> newKeyIterator() { return new KeyIterator(); }
Iterator<V> newValueIterator() { return new ValueIterator(); }
Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }
/**
* 創(chuàng)建節(jié)點(diǎn)，插入到LinkedHashMap中，該方法覆蓋HashMap的addEntry方法
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
super.addEntry(hash, key, value, bucketIndex);
// 注意頭結(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)即header.after，存放于鏈表頭部，是最不經(jīng)常訪問或第一個(gè)插入的節(jié)點(diǎn)，
//有必要的情況下(如容量不夠,具體看removeEldestEntry方法的實(shí)現(xiàn)，這里默認(rèn)為false，不刪除)，可以先刪除
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
/**
* 創(chuàng)建節(jié)點(diǎn)，并將該節(jié)點(diǎn)插入到鏈表尾部
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
//將該節(jié)點(diǎn)插入到鏈表尾部
e.addBefore(header);
size++;
}
/**
* 該方法在創(chuàng)建新節(jié)點(diǎn)的時(shí)候調(diào)用，
* 判斷是否有必要?jiǎng)h除鏈表頭部的第一個(gè)節(jié)點(diǎn)(最不經(jīng)常訪問或最先插入的節(jié)點(diǎn)，由accessOrder決定)
*/
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
}
