摘要：當(dāng)中包括的元素變得比較少時(shí)，為了存儲(chǔ)空間的占用，也會(huì)轉(zhuǎn)換為節(jié)點(diǎn)單向鏈表的方式實(shí)現(xiàn)，它們之間可以互相轉(zhuǎn)換的。

hashMap是通過(guò)數(shù)組存儲(chǔ)所有的數(shù)據(jù)，每個(gè)元素所存放數(shù)組的下標(biāo)，是根據(jù)該存儲(chǔ)元素的key的Hash值與該數(shù)組的長(zhǎng)度減去1做與運(yùn)算，如下所示:
index = (length_of_array - 1) & hash_of_the_key;
數(shù)組中存放元素的數(shù)據(jù)結(jié)構(gòu)使用了Node和TreeNode兩種數(shù)據(jù)結(jié)構(gòu)，在單個(gè)Hash值對(duì)應(yīng)的存儲(chǔ)元素小于8個(gè)時(shí)，默認(rèn)值為Node的單向鏈表形式存儲(chǔ)，當(dāng)單個(gè)Hash值存儲(chǔ)的元素大于8個(gè)時(shí)，其會(huì)使用TreeNode的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)。
因?yàn)樵趩蝹€(gè)Hash值對(duì)應(yīng)的元素小于等于8個(gè)時(shí)，其查詢(xún)時(shí)間最差為O(8)，但是當(dāng)單個(gè)Hash值對(duì)應(yīng)的元素大于8個(gè)時(shí)，再通過(guò)Node的單向鏈表的方式進(jìn)行查詢(xún)，速度上就會(huì)變得更慢了；這個(gè)時(shí)候HashMap就會(huì)將Node的普通節(jié)點(diǎn)轉(zhuǎn)為T(mén)reeNode（紅黑樹(shù)）進(jìn)行存儲(chǔ)，這是由于TreeNode占用的空間大小約為常規(guī)節(jié)點(diǎn)的兩倍，但是其查詢(xún)速度可以得到保證，這個(gè)是通過(guò)空間換時(shí)間了。當(dāng)TreeNode中包括的元素變得比較少時(shí)，為了存儲(chǔ)空間的占用，也會(huì)轉(zhuǎn)換為Node節(jié)點(diǎn)單向鏈表的方式實(shí)現(xiàn)，它們之間可以互相轉(zhuǎn)換的。
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;
    }
    ......

}

可以看到每個(gè)Node中包括了4個(gè)屬性，分別為：
hash值：當(dāng)前Node的Hash值
key：當(dāng)前Node的key
value:當(dāng)前Node的value
next:表示指向下一個(gè)Node的指針，相同hash值的Node，通過(guò)next進(jìn)行遍歷查找
TreeNode：

static final class TreeNode extends LinkedHashMap.Entry {
    TreeNode parent;  // red-black tree links
    TreeNode left;
    TreeNode right;
    TreeNode prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node next) {
        super(hash, key, val, next);
    }
    ......

}
可以看到TreeNode使用的是紅黑樹(shù)（Red Black Tree）的數(shù)據(jù)結(jié)構(gòu)，紅黑樹(shù)是一種自平衡二叉查找樹(shù)，在進(jìn)行插入和刪除操作時(shí)通過(guò)特定操作保持二叉查找樹(shù)的平衡，從而獲得較高的查找性能，即使在最壞情況運(yùn)行時(shí)間也是非常良好的，并且在實(shí)踐中是非常高效的，它可以在O(log n)時(shí)間內(nèi)做查找、插入和刪除等操作，這里的n 是樹(shù)中元素的數(shù)目。
以下是一張關(guān)于HashMap存儲(chǔ)結(jié)構(gòu)的示意圖：

1.寫(xiě)入數(shù)據(jù)
其方法如下：

//寫(xiě)入數(shù)據(jù)

public V put(K key, V value) {
//首先根據(jù)hash方法，獲取對(duì)應(yīng)key的hash值，計(jì)算方法見(jiàn)后面
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node[] tab; Node p; int n, i;
//判斷用戶(hù)存放元素的數(shù)組是否為空 
if ((tab = table) == null || (n = tab.length) == 0)
    //為空則進(jìn)行初使化，并將初使化后的數(shù)組賦值給變量tab，數(shù)組的長(zhǎng)值賦值給變量n
    n = (tab = resize()).length;
//判斷根據(jù)hash值與數(shù)組長(zhǎng)度減1求與得到的下標(biāo)，
//從數(shù)組中獲取元素并將其賦值給變量p(后續(xù)該變量p可以繼續(xù)使用)，并判斷該元素是否存在
if ((p = tab[i = (n - 1) & hash]) == null)
    //如果不存在則創(chuàng)建一個(gè)新的節(jié)點(diǎn)，并將其放到數(shù)組對(duì)應(yīng)的下標(biāo)中
    tab[i] = newNode(hash, key, value, null);
else {//根據(jù)數(shù)組的下標(biāo)取到了元素，并且該元素p且不為空，下面要判斷p元素的類(lèi)型是Node還是TreeNode
    Node e; K k;
    //判斷該數(shù)組對(duì)應(yīng)下標(biāo)取到的第一值是不是與正在存入值的hash值相同、
    //key相等（可能是對(duì)象，也可能是字符串），如果相等，則將取第一個(gè)值賦值給變量e
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
    //判斷取的對(duì)象是不是TreeNode，如果是則執(zhí)行TreeNode的put方法
    else if (p instanceof TreeNode)
        e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
    else {//是普通的Node節(jié)點(diǎn)，
        //根據(jù)next屬性對(duì)元素p執(zhí)行單向鏈表的遍歷
        for (int binCount = 0; ; ++binCount) {
            //如果被遍歷的元素最后的next為空，表示后面沒(méi)有節(jié)點(diǎn)了，則將新節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的next屬性建立關(guān)系
            if ((e = p.next) == null) {
                //做為當(dāng)前節(jié)點(diǎn)的后面的一個(gè)節(jié)點(diǎn)
                p.next = newNode(hash, key, value, null);
                //判斷當(dāng)前節(jié)點(diǎn)的單向鏈接的數(shù)量（8個(gè)）是不是已經(jīng)達(dá)到了需要將其轉(zhuǎn)換為T(mén)reeNode了
                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    //如果是則將當(dāng)前數(shù)組下標(biāo)對(duì)應(yīng)的元素轉(zhuǎn)換為T(mén)reeNode
                    treeifyBin(tab, hash);
                break;
            }
            //判斷待插入的元素的hash值與key是否與單向鏈表中的某個(gè)元素的hash值與key是相同的，如果是則退出
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            p = e;
        }
    }
    //判斷是否找到了與待插入元素的hash值與key值都相同的元素
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        //判斷是否要將舊值替換為新值
        if (!onlyIfAbsent || oldValue == null)
            //滿(mǎn)足于未指定不替換或舊值為空的情況，執(zhí)行將舊值替換為新值
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
}
++modCount;
if (++size > threshold)
    resize();
afterNodeInsertion(evict);
return null;
}

2.讀取數(shù)據(jù)
public V get(Object key) {

    Node e;
    //根據(jù)Key獲取元素
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

final Node getNode(int hash, Object key) {
    Node[] tab; Node first, e; int n; K k;
    //if語(yǔ)句的第一個(gè)判斷條件
    if ((tab = table) != null //將數(shù)組賦值給變量tab，將判斷是否為null
        && (n = tab.length) > 0 //將數(shù)組的長(zhǎng)值賦值給變量n
        && (first = tab[(n - 1) & hash]) != null) {//判斷根據(jù)hash和數(shù)組長(zhǎng)度減1的與運(yùn)算，計(jì)算出來(lái)的的數(shù)組下標(biāo)的第一個(gè)元素是不是為空
        //判斷第一個(gè)元素是否要找的元素，大部份情況下只要hash值太集中，或者元素不是很多，第一個(gè)元素往往都是需要的最終元素
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            //第一個(gè)元素就是要找的元素，因?yàn)閔ash值和key都相等，直接返回
            return first;
        if ((e = first.next) != null) {//如果第一元素不是要找到的元，則判斷其next指向是否還有元素
            //有元素，判斷其是否是TreeNode
            if (first instanceof TreeNode)
                //是TreeNode則根據(jù)TreeNode的方式獲取數(shù)據(jù)
                return ((TreeNode)first).getTreeNode(hash, key);
            do {//是Node單向鏈表，則通過(guò)next循環(huán)匹配，找到就退出，否則直到匹配完最后一個(gè)元素才退出
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    //沒(méi)有找到則返回null
    return null;
}