深入理解HashMap
什么是HashMap
HashMap作為Java語言中一種重要的類型，其存儲數(shù)據(jù)通過鍵值對的形式存儲类茂，即<key耍属，value>的形式托嚣。HashMap繼承AbstractMap類，最終實現(xiàn)的是Map接口厚骗。HashMap中數(shù)據(jù)的Key值不允許重復示启，HashMap中存儲的數(shù)據(jù)可以為null，由于其key值不能重復领舰，則也只有一個對象的key值可以為null夫嗓。HashMap通過hashcode()來獲取哈希值來決定在Map中的存儲位置，所以HashMap中數(shù)據(jù)的存儲順序與存入順序無關冲秽。
HashMap的基本用法
class StudentInfo
{
private int id;
private String homeTown;
private int score;
private final static StudentInfo INSTANCE = new StudentInfo();
StudentInfo(){}
StudentInfo(int id, String homeTown, int score)
{
this.id = id;
this.homeTown = homeTown;
this.score = score;
}
public StudentInfo getInstance(){return INSTANCE;}
public int getId() {return this.id;}
public void setId(int id) {this.id = id;}
public String getHomeTown() {return this.homeTown;}
public void setHomeTown(String homeTown) {this.homeTown = homeTown;}
public int getScore() {return this.score;}
public void setScore(int score) {this.score = score;}
}
這里首先定義一個學生信息類啤月，主要包含學生的id、家鄉(xiāng)和成績?nèi)龡l屬性以及set和get方法
Map<String,StudentInfo> map = new HashMap<String, StudentInfo>();
StudentInfo Tom = new StudentInfo(1,"New York",90);
StudentInfo Abell = new StudentInfo(2,"Houston",95);
map.put("Tom",Tom);
map.put("Abell",Abell);
StudentInfo aStudent = map.get("Abell");
System.out.println("Id: " + aStudent.getId() + " Hometown: " +
aStudent.getHomeTown() + " Score: " + aStudent.getScore());
HashMap的類定義是一種范型的形式public class HashMap<K,V>所以HashMap的Key和Value值可以是各種類型。調(diào)用HashMap的put方法進行數(shù)據(jù)的存儲铛绰，調(diào)用get方法依靠key值來獲取對應的value值戳寸。
該程序的輸出為：
Id: 2 Hometown: Houston Score: 95
HashMap中put()和get()方法的實現(xiàn)
想要更好的理解HashMap，閱讀其源碼是很有必要的郑诺，put()和get()方法又是HashMap數(shù)據(jù)操作中的最基本的兩個方法。put()和get()方法中又調(diào)用了我們常說的hashcode()以及equal()的方法杉武，其中hashcode()用來獲取對象的哈希值辙诞，equal()用來比較兩個對象是否相等；這兩個方法都是從Object類中繼承轻抱。這里我們逐步給出分析飞涂。首先我們來看一下put()方法。
put()方法的實現(xiàn)
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with {@code key}, or
* {@code null} if there was no mapping for {@code key}.
* (A {@code null} return can also indicate that the map
* previously associated {@code null} with {@code key}.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
簡單來說祈搜，在執(zhí)行put操作時较店，將根據(jù)插入的key值與之前的數(shù)據(jù)進行比較，且該方法以范型的形式進行定義容燕，其返回值與value的類型相同梁呈。如果入?yún)ey值相同（當然Key的hash值也需要相同）但value值不同的話，則方法返回老的value值蘸秘，且將用新的value代替老的value值官卡。如果新插入的數(shù)據(jù)與老數(shù)據(jù)沒有發(fā)生碰撞，即沒有因為key值相同重復醋虏，則put()方法返回null寻咒。
putVal()方法底層是通過數(shù)組+鏈表+紅黑樹算法實現(xiàn)的。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict)
putVal()方法的入?yún)⑷缟暇苯溃謩e保存為hash值毛秘、key和value；其中onlyIfAbsent粘舟，evict參數(shù)再HashMap格式中都沒有使用
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
在put()方法中先根據(jù)傳入的hash值進行判斷熔脂，通過(n-1) & hash來決定數(shù)據(jù)的存儲位置佩研，其中n為當前存儲數(shù)據(jù)表的大小，若傳入的hash值與已存在的數(shù)據(jù)的hash值相同霞揉，則發(fā)生碰撞旬薯，將不走該if的邏輯。若tab[i] == null,則未發(fā)生碰撞直接將數(shù)據(jù)儲存适秩。在此判斷中同時給p賦值绊序，Node<K,V> p』嘬瘢可以理解p保存了發(fā)生碰撞的數(shù)據(jù)的值骤公，Node<K,V>為鏈表的格式，用來存儲單條數(shù)據(jù)扬跋。
如果沒有碰撞阶捆，將數(shù)據(jù)存儲之后，直接跳到以下代碼進行處理
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
modCount為int類型钦听，記錄HashMap結構變更的次數(shù)洒试，在執(zhí)行put()方法時，只有新增條目的時候才會發(fā)生結構的變更朴上，同時該變量在remove()等操作中也將記錄次數(shù)的增加垒棋。size變量記錄HashMap中有多少個鍵值對，其大小限制為threshold,查看resize()的源碼痪宰，我們可以知道其初始值為16*0.75叼架，當size大小超過threshold后再此調(diào)用resize()方法，將容量擴帶為當前的兩倍衣撬。
如果數(shù)據(jù)發(fā)生碰撞乖订，則執(zhí)行else的邏輯,這里定義了Node<K,V> e; K k;，為存儲數(shù)據(jù)的臨時變量淮韭。afterNodeInsertion(evict)方法再HashMap中為空操作垢粮；執(zhí)行return null結束put()方法的調(diào)用。
如果判斷hash值時靠粪，發(fā)生了數(shù)據(jù)的碰撞，將轉入下面的邏輯進行處理
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;
}
}
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
我們分段來看一下這部分程序毫蚓，如果入?yún)⑴c碰撞的數(shù)據(jù)hash值占键、并且key值相同，則直接用臨時變量來保存發(fā)生碰撞的老數(shù)據(jù)元潘，然后跳到后面對碰撞數(shù)據(jù)的處理
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
在該部分中畔乙，首先用變量oldValue保存老的value數(shù)據(jù)，然后通過將傳入的value賦值給e.value完成數(shù)據(jù)的覆蓋翩概；隨后afterNodeAccess(e)在HashMap中操作為空（在LinkedHashMap中對該方法進行了重寫）牲距，return了發(fā)生碰撞老的value值返咱。其余分支的代碼為存儲桶邏輯和紅黑樹的邏輯，從源碼中我們可以看到如果桶的大小增長到8之后牍鞠，將轉成紅黑樹進行處理咖摹。
get()方法的實現(xiàn)
看完put()方法之后，再來看一下get()方法的實現(xiàn)
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
從上面的源碼可以看到难述，get()方法入?yún)⑽秌ey值萤晴，這里沒用范型的形式，而是直接定義為Object類型參數(shù)胁后，通過調(diào)用getNode()完成進一步的數(shù)據(jù)查詢操作店读。因為這部分源碼也比較簡單，這里直接給出分析
/**
* Implements Map.get and related methods.
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
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;
}
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null)
首先也是進行臨時變量的定義攀芯，然后進行判空屯断，如果數(shù)據(jù)表為空直接返回null，進一步在這個判斷中也通過hash值對數(shù)據(jù)的位置進行判斷（所以說如果要用自定義的類做key值的時候侣诺，重寫hashcode()是很必要的)裹纳。
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);
}
這部分將以鏈表的形式對整個數(shù)據(jù)表進行遍歷，首先檢查鏈表中的第一個Node紧武，之后通過鏈表的指針逐個指向后面的元素剃氧，進行數(shù)據(jù)的查找，直到找到匹配的數(shù)據(jù)或者指針指到最后一個元素阻星。
重寫hashcode()和equal()
當我們使用自定義的類型作為HashMap的key值的時候朋鞍，我們需要重寫一下hashcode()和equal()方法。在說原因之前妥箕，我們先看一個例子
class People
{
private String name;
People(){}
People(String name){this.name = name;}
public void setName(String name){this.name = name;}
public String getName(){return this.name;}
首先定義一個簡單的People類滥酥，其中有對應的name屬性
People jack = new People("Tony");
int age = 10;
Map<People,Integer> hasmap = new HashMap<People,Integer>();
hasmap.put(jack,age);
System.out.print("The Tony's age is : ");
System.out.print(hasmap.get(new People("Tony")));
之后我們定義一個People的對象，名叫做Tony畦幢，然后將它放到hashmap中坎吻，然后用get方法來取出這個名叫Jack的People變量，看一下輸出結果
The Tony's age is : null
為什么是null宇葱，而不是我們期望的10瘦真。這里就可以想一下剛才看到的get()方法的源碼。對黍瞧，因為兩個People對象并不是同一個诸尽，所以其對應的HashCode也不相同，然而我們就像通過相同的名字來取數(shù)據(jù)怎么辦印颤。這里就需要在People類中重寫hashcode()和euqal()方法了您机。
@Override
public int hashCode()
{
return name.hashCode();
}
@Override
public boolean equals(Object obj)
{
if(obj instanceof People)
{
People inPeople = (People)obj;
return this.name.equals(inPeople.getName());
}
return false;
}
重寫之后，將不在調(diào)用Object類中的方法，再次執(zhí)行际看，結果符合預期
The Tony's age is : 10
總結
我們都知道如果用數(shù)組的形式存儲數(shù)據(jù)咸产，執(zhí)行插入或者刪除的操作的時候，數(shù)組中所有元素都要移動仲闽，該操作對于頻繁的插入脑溢、刪除操作將十分耗內(nèi)存；而使用鏈表的形式蔼囊，雖不需要去移動數(shù)據(jù)焚志，但執(zhí)行查找遍歷整個鏈表又是十分耗時的。
HashMap通過hash值的方式很好的解決了鏈表查找耗時的缺點畏鼓，同時通過動態(tài)的擴容以及靈活的指針操作酱酬，解決了內(nèi)存損耗的問題≡平茫可以說是兩種基本存儲結構的結合體膳沽，也是在Java中頻繁使用的一種數(shù)據(jù)存儲格式。
