Map
- 類圖
TreeMap實現(xiàn)
TreeMap是通過紅黑樹進行的,紅黑樹能夠保證在最壞的情況,基本的動態(tài)集合操作的時間復(fù)雜度為O(lgn);
TreeMap是根據(jù)鍵的自然順序進行排序的,或者根據(jù)創(chuàng)建映射時提供的 Comparator 進行排序摇锋，具體取決于使用的構(gòu)造方法胆建。
TreeMap的基本操作 containsKey雕拼、get钠至、put 和 remove 的時間復(fù)雜度是 log(n) 房铭。另外荆残，TreeMap是非同步的蛛枚。 它的iterator 方法返回的迭代器是fail-fastl的暖哨。
jdk里邊的實現(xiàn)分析請看這篇文章Java提高篇（二七）-----TreeMap, Java 集合系列12之 TreeMap詳細介紹(源碼解析)和使用示例由于紅黑樹這部分太過復(fù)雜,需要好好研究之后再給大家分享.
HashMap實現(xiàn)
- 它是基于哈希表的Map接口的實現(xiàn).了解hashMap前先看下hashcode的定義:
hashcode方法返回該對象的哈希碼值。支持該方法是為哈希表提供一些優(yōu)點墨状，例如，java.util.Hashtable 提供的哈希表菲饼。
hashCode 的常規(guī)協(xié)定是：
在 Java 應(yīng)用程序執(zhí)行期間肾砂，在同一對象上多次調(diào)用 hashCode 方法時，必須一致地返回相同的整數(shù)宏悦，前提是對象上 equals 比較中所用的信息沒有被修改镐确。從某一應(yīng)用程序的一次執(zhí)行到同一應(yīng)用程序的另一次執(zhí)行，該整數(shù)無需保持一致饼煞。
如果根據(jù) equals(Object) 方法源葫，兩個對象是相等的，那么在兩個對象中的每個對象上調(diào)用 hashCode 方法都必須生成相同的整數(shù)結(jié)果砖瞧。
以下情況不 是必需的：如果根據(jù) equals(java.lang.Object) 方法息堂，兩個對象不相等，那么在兩個對象中的任一對象上調(diào)用 hashCode 方法必定會生成不同的整數(shù)結(jié)果块促。但是储矩，程序員應(yīng)該知道，為不相等的對象生成不同整數(shù)結(jié)果可以提高哈希表的性能褂乍。
實際上持隧，由 Object 類定義的 hashCode 方法確實會針對不同的對象返回不同的整數(shù)。（這一般是通過將該對象的內(nèi)部地址轉(zhuǎn)換成一個整數(shù)來實現(xiàn)的逃片，但是 JavaTM 編程語言不需要這種實現(xiàn)技巧屡拨。）
當(dāng)equals方法被重寫時，通常有必要重寫 hashCode 方法褥实，以維護 hashCode 方法的常規(guī)協(xié)定呀狼，該協(xié)定聲明相等對象必須具有相等的哈希碼。
- 總結(jié)來說:
如果兩個對象相同貌踏，就是適用于equals(java.lang.Object) 方法，那么這兩個對象的hashCode一定要相同窟勃；
如果對象的equals方法被重寫祖乳，那么對象的hashCode也盡量重寫，并且產(chǎn)生hashCode使用的對象秉氧，一定要和equals方法中使用的一致眷昆，否則就會違反上面提到的第2點；
兩個對象的hashCode相同，并不一定表示兩個對象就相同亚斋，也就是不一定適用于equals(java.lang.Object) 方法作媚，只能夠說明這兩個對象在散列存儲結(jié)構(gòu)中，如Hashtable帅刊，他們“存放在同一個籃子里”纸泡。
- HashMap有幾個重要的屬性:table, size, threshold, loadFactor, modCount。
table:
存儲Entry對象的數(shù)組,Node對象實現(xiàn)了Entry.在必要的時候,會進行擴容.Node對象本身是一個內(nèi)嵌鏈表.
transient Node<K,V>[] table;
size:
map包含數(shù)據(jù)的個數(shù)
transient int size;
modcount:
map被修改的次數(shù),用來實現(xiàn)fail-fast機制
transient int modCount;
threshold:
閾值厚掷，用于判斷是否需要調(diào)整HashMap的容量弟灼。threshold的值="容量*加載因子"级解，當(dāng)HashMap中存儲數(shù)據(jù)的數(shù)量達到threshold時冒黑，就需要將HashMap的容量加倍。
int threshold;
loadFactor:
map的負載因子
final float loadFactor;
看一下Node的定義:它繼承了Map中的Entry接口,定義了key,value,下一個節(jié)點的引用,以及hash值.由此及上文的Node數(shù)組,HashMap底層是一個數(shù)組,每一個數(shù)組的元素都是一個單向鏈表.
class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
那么問題來了:數(shù)組下表對應(yīng)的Key的hash值,hash值一般都很大,那數(shù)組也要那么大嗎?
Key的hash算法如下:納莫,通過下文中的擾動函數(shù)得到一個hash,再通過數(shù)組大小邏輯與hash:
(n - 1) & hash
得到數(shù)組下標(biāo).
參考文章JDK 源碼中 HashMap 的 hash 方法原理是什么勤哗？
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
設(shè)計理念:
HashMap進行存儲的時候,將key進行hash散列為一個int值,將int值設(shè)為底層數(shù)組的下標(biāo),將key的hash值相同的Entry存入到該元素的鏈表上.
那么通過key進行查找的時候,就可以通過key的hash值,先去數(shù)組找到對應(yīng)元素,再通過元素尋找Entry;HashMap 擴容方法
final Node<K,V>[] resize() {
//原始的table
Node<K,V>[] oldTab = table;
//原始table的大小
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//原始table的閾值
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
//如果原來table的大小大于定義的最大容量1 << 30(2^30),將閾值設(shè)為計算機能標(biāo)識的最大整數(shù)
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果原始table的大小的二倍小于默認的最大容量,并且大于默認的最小容量,則將閾值翻倍并返回
newThr = oldThr << 1; // double threshold
}else if (oldThr > 0)
//如果原來的table大小等于0且原始閾值大于0,那么,table的大小賦值為原始閾值
newCap = oldThr;
else {
// 如果原始閾值不大于0,且原始table容量不大于0
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"})
//通過新的table容量創(chuàng)建table
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//將原來的table數(shù)據(jù)copy到新建的table中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
//如果當(dāng)前節(jié)點沒有下一個元素
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//如果當(dāng)前節(jié)點是TreeNode,那么就通過紅黑樹存入.
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//循環(huán)copy
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;
}
LinkedHashMap實現(xiàn)
LinkedHashMap在邏輯關(guān)系上是通過外層的鏈表控制,空間關(guān)系上仍然是通過和HashMap一樣的hash桶進行存儲,
LinkedHashMap是基于HashMap的一個實現(xiàn),它保證了HashMap元素沒有的有序性,LinkedHashMap可以讓元素實現(xiàn)兩種有序的方式:當(dāng)AccessOrder=true時,元素按照訪問的先后順序進行排序,AccessOrder=false時,元素按照插入的順序進行排序.它是由雙向鏈表+hashmap實現(xiàn)的.
/**
* Constructs an empty <tt>LinkedHashMap</tt> instance with the
* specified initial capacity, load factor and ordering mode.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @param accessOrder the ordering mode - <tt>true</tt> for
* access-order, <tt>false</tt> for insertion-order
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
-
LinkedHashMap如何基于HashMap進行的擴展?
通過查看源碼,LinkedHashMap進行的時候,并沒有重寫hashMap的put,remove等方法,那么怎么保證LinkedHashMap的put和remove操作不同于HashMap.原因就是這三個方法:
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
HashMap在實現(xiàn)putVal,remove等方法的時候,調(diào)用了這幾個空方法.這樣LinkedHashMap通過重載這幾個方法,來實現(xiàn)了自己的一些邏輯.
- 從afterNodeInsertion(boolean evict)看出的LinkedHashMap對外提供的擴展的接口.
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
- 外部通過重載方法removeEldestEntry(),可以自定義移除老元素的規(guī)則.如LruCache一樣的擴展實現(xiàn)
public class LRUCache2<K, V> extends LinkedHashMap<K, V> {
private final int MAX_CACHE_SIZE;
public LRUCache2(int cacheSize) {
super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
MAX_CACHE_SIZE = cacheSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_CACHE_SIZE;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (Map.Entry<K, V> entry : entrySet()) {
sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
}
return sb.toString();
}
}
參考來源:java之LinkedHashMap實現(xiàn)原理
- LinkedHashMap的迭代
LinkedHashMap是對Array與Link的折衷處理抡爹，Array與Link可以說是兩個速度方向的極端，Array注重于數(shù)據(jù)的獲取芒划，而處理修改（添加/刪除）的效率非常低冬竟；Link由于是每個對象都保持著下一個對象的指針，查找某個數(shù)據(jù)需要遍歷之前所有的數(shù)據(jù)民逼，所以效率比較低泵殴，而在修改操作中比較快。
