數(shù)據(jù)結(jié)構(gòu)是程序的重要組成部分，選擇好的數(shù)據(jù)結(jié)構(gòu)可以讓程序更加高效臣咖。對于數(shù)據(jù)的操作跃捣，無非就是增、刪夺蛇、改疚漆、查，下面將講解為什么使用HashMap以及它的原理刁赦。

起初娶聘，存儲數(shù)據(jù)最簡單的數(shù)據(jù)結(jié)構(gòu)是數(shù)組，數(shù)組的優(yōu)點是查找速度快截型，缺點是刪除速度特別慢趴荸。

接下來是鏈表數(shù)據(jù)結(jié)構(gòu)，鏈表的優(yōu)點是刪除速度快宦焦，缺點是查找速度慢发钝。

那么顿涣，有沒有一種數(shù)據(jù)結(jié)構(gòu)可以結(jié)合兩者的優(yōu)點呢？

答案是有的酝豪，這就是我們常說的哈希表涛碑。

我在網(wǎng)上截了一張圖，如下：

圖片.png

哈希表是由數(shù)組+鏈表組成的混合結(jié)構(gòu)孵淘，在圖中縱向的0~15表示一個數(shù)組蒲障，每個數(shù)組的下標都可以含有一個鏈表。

當使用put方法添加元素時瘫证，首先需計算出數(shù)組的索引揉阎，再將元素插入到當前數(shù)組索引對應鏈表的某個位置。實際上背捌，往往插入元素的次數(shù)比較頻繁毙籽，在索引為12的位置上插入過多的元素，每次都要從頭遍歷當前索引所對應鏈表毡庆，如果key相同坑赡，則替換掉原來的value值，否則直接在鏈表的末尾添加元素么抗。像這種毅否，重復的在某索引下插入元素叫做碰撞。很明顯蝇刀，如果碰撞次數(shù)太多螟加，會大大的影響hashmap的性能。那么熊泵，怎么才能減少碰撞的次數(shù)呢仰迁？請繼續(xù)往下看。

本文講解HashMap的大方向主要有以下幾點：

• 構(gòu)造方法
• 插入元素
• 獲取元素
• 遍歷

（1）構(gòu)造方法

【方法一】

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

在這個方法中顽分，DEFAULT_LOAD_FACTOR為負載系數(shù)徐许，源碼中的定義如下：

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

負載系數(shù)默認為0.75，這個參數(shù)和HashMap的擴容有關(guān)卒蘸。

另外雌隅，HashMap是有容量的，此時HashMap的默認容量是16缸沃，源碼中的定義如下：

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

【方法二】

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and the default load factor (0.75).
 *
 * @param  initialCapacity the initial capacity.
 * @throws IllegalArgumentException if the initial capacity is negative.
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

這個構(gòu)造方法容量可以自定義恰起，至于負載系數(shù)采用默認值0.75。

【方法三】

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and load factor.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

這個方法可以任意指定HashMap的容量以及負載系數(shù)趾牧。容量的大小不能大于MAXIMUM_CAPACITY检盼，有關(guān)MAXIMUM_CAPACITY源碼中的定義代碼是：

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

轉(zhuǎn)成十進制是：

static final int MAXIMUM_CAPACITY = 1073741824;

另外，這個方法中的tableSizeFor方法是計算當前容量的閾值翘单，即最大容量吨枉，最大容量總是等于2的n次冪蹦渣，假如HashMap的容量是9，那么數(shù)組的大小是16貌亭，2的4次冪柬唯。計算數(shù)組大小的源碼如下：

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

【方法四】

/**
 * Constructs a new <tt>HashMap</tt> with the same mappings as the
 * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
 * default load factor (0.75) and an initial capacity sufficient to
 * hold the mappings in the specified <tt>Map</tt>.
 *
 * @param   m the map whose mappings are to be placed in this map
 * @throws  NullPointerException if the specified map is null
 */
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

這個方法的形參就是HashMap集合，想都不用想圃庭，肯定會遍歷舊集合锄奢，并一個一個添加到新的集合中。putMapEntries方法的源碼如下：

/**
 * Implements Map.putAll and Map constructor
 *
 * @param m the map
 * @param evict false when initially constructing this map, else
 * true (relayed to method afterNodeInsertion).
 */
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) { // pre-size
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        else if (s > threshold)
            resize();
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

其中putVal方法就是插入元素剧腻。

（2）插入元素

當需要添加元素時拘央，代碼實現(xiàn)如下：

    HashMap<String, String> hashMap = new HashMap<>();
    //添加一個元素
    hashMap.put("key", "value");

那么，put方法的原理是什么呢恕酸？想要知道這個答案堪滨，必須研究下源碼了胯陋。

/**
 * 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 <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    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;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

【第一步】 對Key求Hash值蕊温，然后再計算下標

putVal的第一個參數(shù)是根據(jù)Key的hashcode計算一個新的hashcode，源碼如下：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

在JDK1.8之前遏乔，重新計算hashcode源碼是這樣的

    final int hash(Object k) {
        int h = 0;
        if (useAltHashing) {
            if (k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;
        }
        //得到k的hashcode值
        h ^= k.hashCode();
        //進行計算
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

計算數(shù)組下標代碼如下：

在JDK1.8之前的源碼是：

static int indexFor(int h, int length) {  
    return h & (length-1);
}

在JDK1.8之后义矛，計算數(shù)組下標的代碼在putVal中，

tab[i = (n - 1) & hash]

n是數(shù)組的長度盟萨，hash的重新計算后的hashcode凉翻。

所以，計算數(shù)組下標的算法是：

index =  hashcode & (length-1)

該算法相當于

index =  hashcode % length

那么捻激，問題來了制轰，為什么不直接使用key的hashcode？為什么JDK1.8前后會有差異胞谭？

原因只有一個：為了讓Hash表更加散列垃杖，減少沖突（碰撞）次數(shù)。

如果hashcode沒有重新計算丈屹，假設(shè)某對象的hashcode是3288498调俘，那么對應的二進制是：

1100100010110110110010

hashmap的長度默認為16，所以假設(shè)length = 16旺垒，hashcode & (length-1)的運算如下：

  1100100010110110110010
& 0000000000000000001111
--------------------------------------
  0000000000000000000010

以上計算結(jié)果是十進制2彩库，即數(shù)組下標為2。因此先蒋，我們發(fā)現(xiàn)的現(xiàn)象是：計算數(shù)組角標的計算骇钦，其實就是低位在計算，當前是在低4位上進行運算竞漾。

當數(shù)組長度為8時眯搭，在第3位計算出數(shù)組下標皇忿；
當數(shù)組長度為16時，在第4位計算出數(shù)組下標坦仍；
當數(shù)組長度為32時鳍烁，在第5位計算出數(shù)組下標；
當數(shù)組長度為64時繁扎，在第6位計算出數(shù)組下標幔荒；

以此類推...

為了讓HashMap的存儲更加散列，即低n位更加散列梳玫，需要和高m位進行異或運算爹梁，最終得出新的hashcode。這就是要重新計算hashcode的原因提澎。JDK1.8前后重新計算hashcode算法的差異是因為姚垃，JDK1.8的hash算法比JDK1.8之前的hash算法更能讓HashMap的存儲更加散列，避免存儲空間的擁擠盼忌，減少碰撞的發(fā)生积糯。

【第二步】 碰撞的處理

Java中HashMap是利用“拉鏈法”處理HashCode的碰撞問題。在調(diào)用HashMap的put方法或get方法時谦纱，都會首先調(diào)用hashcode方法看成，去查找相關(guān)的key，當有沖突時跨嘉，再調(diào)用equals方法川慌。hashMap基于hasing原理，我們通過put和get方法存取對象祠乃。當我們將鍵值對傳遞給put方法時梦重，他調(diào)用鍵對象的hashCode()方法來計算hashCode，然后找到bucket（哈希桶）位置來存儲對象亮瓷。當獲取對象時琴拧，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象寺庄。HashMap使用鏈表來解決碰撞問題艾蓝，當碰撞發(fā)生了，對象將會存儲在鏈表的下一個節(jié)點中斗塘。hashMap在每個鏈表節(jié)點存儲鍵值對對象赢织。當兩個不同的鍵卻有相同的hashCode時，他們會存儲在同一個bucket位置的鏈表中馍盟。

【第三步】 如果鏈表長度超過閥值( TREEIFY THRESHOLD==8)于置，就把鏈表轉(zhuǎn)成紅黑樹，鏈表長度低于6贞岭，就把紅黑樹轉(zhuǎn)回鏈表

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8;

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    //紅黑樹
    treeifyBin(tab, hash);

在JDK1.8之后八毯，HashMap的存儲引入了紅黑樹數(shù)據(jù)結(jié)構(gòu)搓侄。

【第四步】 如果節(jié)點已經(jīng)存在就替換舊值

代碼如下：

        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;

【第五步】 擴容

代碼如下：

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    //當前容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //閾值，最大容量
    int oldThr = threshold;
    //定義新容量和閾值
    int newCap, newThr = 0;
    if (oldCap > 0) {//如果當前容量>0
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            //計算新的閾值话速，在老閾值的基礎(chǔ)上乘以2
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        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"})

    //計算完容量和閾值之后讶踪，開始新建一個數(shù)組，擴容
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        //賦值操作
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    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;
}

以上擴容相關(guān)代碼是基于JDK1.8的泊交，和JDK1.8之前存在差異乳讥。

（3）獲取元素

/**
 * 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;
}

/**
 * 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;
}

獲取元素其實，沒什么好講的廓俭，但是需要知道的是云石，不管是插入元素還是獲取元素，都是圍繞節(jié)點(Node)來操作的研乒。Node實現(xiàn)了Map.Entry<K,V>接口汹忠。

（4）遍歷元素

【方法一】

如果只需要獲取所有的key，最佳方案如下：

    for (Integer key : map.keySet()) {//在for-each循環(huán)中遍歷keys
        System.out.println(String.valueOf(key));
    }

優(yōu)點：比entrySet遍歷要快雹熬，代碼簡潔宽菜。

【方法二】

如果只需要獲取所有的value，最佳方案如下：

    for (String value : map.values()) {//在for-each循環(huán)中遍歷value
        System.out.println(value);
    }

優(yōu)點：比entrySet遍歷要快橄唬，代碼簡潔赋焕。

【方法三】

通過鍵找值遍歷

    for (Integer key : map.keySet()) {//在for-each循環(huán)中遍歷keys
        String value = map.get(key);
        System.out.println(key+"========"+value);
    }

缺點：根據(jù)鍵取值是耗時操作，效率非常的慢仰楚， 所以不推薦。

【方法四】

通過Map.entrySet遍歷key和value

    for (Map.Entry<Integer, String> entry : map.entrySet()) {
        System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
    }

優(yōu)點：代碼簡潔犬庇，效率高僧界，推薦使用。

【方法五】

使用Iterator遍歷

    Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
    while (iterator.hasNext()) {
        Map.Entry<Integer, String> entry = iterator.next();
        System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
    }

缺點：代碼比起前面幾個方法并不簡潔臭挽。
優(yōu)點：當遍歷的時候捂襟，如果涉及到刪除操作，建議使用Iterator的remove方法欢峰，因為如果使用foreach的話會報錯葬荷。

[本章完...]