Map接口
基本概念
Map有鍵和值的概念实檀，一個(gè)鍵映射到一個(gè)值，Map按照鍵存儲(chǔ)和訪問值疗疟，鍵不能重復(fù)如失，即一個(gè)鍵只會(huì)存儲(chǔ)一份，給同一個(gè)鍵重復(fù)設(shè)值會(huì)覆蓋原來的值限嫌。使用Map可以方便地處理需要根據(jù)鍵訪問對(duì)象的場(chǎng)景靴庆，比如：
- 一個(gè)詞典應(yīng)用，鍵可以為單詞怒医，值可以為單詞信息類炉抒，包括含義、發(fā)音稚叹、例句等焰薄。
- 統(tǒng)計(jì)和記錄一本書中所有單詞出現(xiàn)的次數(shù)，可以以單詞為鍵扒袖，出現(xiàn)次數(shù)為值塞茅。
- 管理配置文件中的配置項(xiàng)，配置項(xiàng)是典型的鍵值對(duì)季率。
- 根據(jù)身份證號(hào)查詢?nèi)藛T信息野瘦，身份證號(hào)為鍵，人員信息為值。
數(shù)組鞭光、ArrayList吏廉、LinkedList可以視為一種特殊的Map，鍵為索引惰许，值為對(duì)象席覆。
接口定義
Map接口的定義為：
public interface Map<K,V> {
V put(K key, V value);//保存鍵值對(duì)
V get(Object key);
V remove(Object key);
int size();
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
void putAll(Map<? extends K, ? extends V> m);//批量保存，保存參數(shù)m中的所有鍵值對(duì)到當(dāng)前Map
void clear();
Set<K> keySet();//獲取Map中鍵的集合汹买，Set沒有重復(fù)的元素集合
Collection<V> values();//獲取Map中所有值的集合佩伤，可以重復(fù)
Set<Map.Entry<K, V>> entrySet();//獲取Map中的所有鍵值對(duì)
interface Entry<K,V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
}
boolean equals(Object o);
int hashCode();
}
HashMap
構(gòu)造方法
除了默認(rèn)構(gòu)造方法，HashMap還有如下構(gòu)造方法：
public HashMap(int initialCapacity)
public HashMap(int initialCapacity, float loadFactor)
public HashMap(Map<? extends K, ? extends V> m)
實(shí)現(xiàn)原理
內(nèi)部組成
HashMap內(nèi)部有如下幾個(gè)主要的實(shí)例變量：
//被transient關(guān)鍵字修飾的變量不會(huì)被序列化
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;//一個(gè)Entry類型的數(shù)組晦毙，其中的每個(gè)元素指向一個(gè)單向鏈表畦戒，鏈表中的每個(gè)節(jié)點(diǎn)表示一個(gè)鍵值對(duì)，Entry是一個(gè)內(nèi)部類
transient int size;//實(shí)際鍵值對(duì)的個(gè)數(shù)
int threshold;//閾值结序，當(dāng)鍵值對(duì)個(gè)數(shù)size大于等于threshold時(shí)考慮進(jìn)行擴(kuò)展
final float loadFactor;//負(fù)載因子障斋，表示整體上table被占用的程度，是一個(gè)浮點(diǎn)數(shù)徐鹤，默認(rèn)為0.75垃环，可以通過構(gòu)造方法進(jìn)行修改
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next//指向下一個(gè)Entry節(jié)點(diǎn)
int hash;//key的哈希值，直接存儲(chǔ)hash值是為了在比較的時(shí)候加快計(jì)算
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}
table的初始值為EMPTY_TABLE返敬，是一個(gè)空表遂庄，具體定義為：
static final Entry<?,?>[] EMPTY_TABLE = {};
當(dāng)添加鍵值對(duì)后，table就不是空表了劲赠，它會(huì)隨著鍵值對(duì)的添加進(jìn)行擴(kuò)展涛目，擴(kuò)展的策略類似于ArrayList，添加第一個(gè)元素時(shí)凛澎，默認(rèn)分配的大小為16霹肝，不過，并不是size大于16時(shí)再進(jìn)行擴(kuò)展塑煎，下次什么時(shí)候擴(kuò)展與threshold有關(guān)沫换。一般而言，threshold等于table.length乘以loadFactor最铁，比如讯赏，如果table.length為16，loadFactor為0.75冷尉，則threshold為12漱挎。
默認(rèn)構(gòu)造方法
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);//(16,0.75)
}
public HashMap(int initialCapacity, float loadFactor) {
this.loadFactor = loadFactor;
threshold = initialCapacity;
}
保存鍵值對(duì)
下面，我們來看HashMap是如何把一個(gè)鍵值對(duì)保存起來的雀哨，代碼為：
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);//計(jì)算key的哈希值
int i = indexFor(hash, table.length);//計(jì)算應(yīng)該將這個(gè)鍵值對(duì)放到table的哪個(gè)位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {//保存位置i磕谅，table[i]指向一個(gè)單向鏈表，在這個(gè)鏈表中逐個(gè)查找是否已經(jīng)有這個(gè)鍵了
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;//如果找到了已經(jīng)存儲(chǔ)的key，直接修改后返回
}
}
modCount++;//記錄修改次數(shù)怜庸，方便在迭代中檢測(cè)結(jié)構(gòu)性變化
addEntry(hash, key, value, i);//未存儲(chǔ)過，則新增
return null;
}
//如果是第一次保存垢村，首先會(huì)調(diào)用inflateTable()方法給table分配實(shí)際的空間
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
//默認(rèn)情況下割疾，capacity的值為16，threshold會(huì)變?yōu)?2嘉栓，table會(huì)分配一個(gè)長(zhǎng)度為16的Entry數(shù)組
}
static int indexFor(int h, int length) {
return h & (length-1);
//HashMap中宏榕，length為2的冪次方，h&(length-1)等同于求模運(yùn)算：h%length
}
//在給定的位置添加一條
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);//空間不夠侵佃，要擴(kuò)展
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);//如果空間是夠的麻昼，不需要resize，調(diào)用createEntry添加一條數(shù)據(jù)
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);//這里實(shí)際上是相當(dāng)于添加到了鏈表頭
size++;
}
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));//將原來的鍵值對(duì)移植過來
table = newTable;//更新內(nèi)部的table變量
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//遍歷原來的每個(gè)鍵值對(duì)馋辈，計(jì)算新位置抚芦，并保存到新位置
void transfer(Entry[] newTable, boolean rehash) {//rehash一般為false
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
以上，就是保存鍵值對(duì)的主要代碼迈螟，簡(jiǎn)單總結(jié)一下叉抡，基本步驟為：
- 計(jì)算鍵的哈希值
- 根據(jù)哈希值得到保存位置（取模）
- 插到對(duì)應(yīng)位置的鏈表頭部或更新已有值
- 根據(jù)需要擴(kuò)展table大小
圖示說明
以上描述可能比較抽象，我們通過一個(gè)例子答毫，用圖示的方式說明褥民，代碼是：
Map<String,Integer> countMap = new HashMap<>();
countMap.put("hello", 1);
countMap.put("world", 3);
countMap.put("position", 4);
在通過new HashMap()創(chuàng)建一個(gè)對(duì)象后，內(nèi)存中的圖示結(jié)構(gòu)大概是：
接下來執(zhí)行countMap.put("hello", 1);
"hello"的hash值為96207088洗搂，模16的結(jié)果為0消返，所以插入table[0]指向的鏈表頭部，內(nèi)存結(jié)構(gòu)會(huì)變?yōu)椋?/p>
"world"的hash值為111207038耘拇，模16結(jié)果為15撵颊，所以保存完"world"后，內(nèi)存結(jié)構(gòu)會(huì)變?yōu)椋?/p>
"position"的hash值為771782464惫叛，模16結(jié)果也為0秦驯，table[0]已經(jīng)有節(jié)點(diǎn)了，新節(jié)點(diǎn)會(huì)插到鏈表頭部挣棕，內(nèi)存結(jié)構(gòu)會(huì)變?yōu)椋?/p>
實(shí)現(xiàn)原理小結(jié)
以上就是HashMap的基本實(shí)現(xiàn)原理译隘，內(nèi)部有一個(gè)數(shù)組table，每個(gè)元素table[i]指向一個(gè)單向鏈表洛心，根據(jù)鍵存取值固耘，用鍵算出hash，取模得到數(shù)組中的索引位置buketIndex词身，然后操作table[buketIndex]指向的單向鏈表厅目。
存取的時(shí)候依據(jù)鍵的hash值，只在對(duì)應(yīng)的鏈表中操作，不會(huì)訪問別的鏈表损敷，在對(duì)應(yīng)鏈表操作時(shí)也是先比較hash值葫笼，相同的話才用equals方法比較，這就要求拗馒，相同的對(duì)象其hashCode()返回值必須相同路星，如果鍵是自定義的類，就特別需要注意這一點(diǎn)诱桂。這也是hashCode和equals方法的一個(gè)關(guān)鍵約束洋丐。
HashMap特點(diǎn)分析
HashMap實(shí)現(xiàn)了Map接口，內(nèi)部使用數(shù)組鏈表和哈希的方式進(jìn)行實(shí)現(xiàn)挥等，這決定了它有如下特點(diǎn)：
- 根據(jù)鍵保存和獲取值的效率都很高友绝，為O(1)，每個(gè)單向鏈表往往只有一個(gè)或少數(shù)幾個(gè)節(jié)點(diǎn)肝劲，根據(jù)hash值就可以直接快速定位迁客。
- HashMap中的鍵值對(duì)沒有順序，因?yàn)閔ash值是隨機(jī)的辞槐。
如果經(jīng)常需要根據(jù)鍵存取值哲泊，而且不要求順序，那HashMap就是理想的選擇催蝗。
不過HashMap沒有順序切威，如果要保持添加的順序，可以使用HashMap的一個(gè)子類LinkedHashMap丙号，Map還有一個(gè)重要的實(shí)現(xiàn)類TreeMap先朦，它可以排序。
