HashMap 初探

概覽

這篇文章，我們打算探索一下Java集合(Collections)架構中Map接口中HashMap的實作。Map雖然是Collctions架構的一部分，但是Map并沒有實作Collection接口，而Set和List是實作Collection接口的。

簡單來說，HashMap主要通過key存儲value值，并且提供了添加，擷取和操作存儲value的方法。HashMap的實作基于HashTable。

HashMap内部呈現

Key-value對在内部是以buckets的方式存儲在一起，最終成為一個表。存儲和檢索操作的時間是固定的，也就是時間複雜度為O(1)。

這篇文章暫時不過于涉及HashMap的底層，我們先對HashMap有個整體認知。

put方法

Map中通過put方法來存儲一個value。

/**
     * 建立鍵值對應關系，如果之前已經存在對應的key，
     * 傳回之前存儲的value，之前如果不存在對應的key，傳回null
     */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
           

知識點一： 當Map的調用put方法的時候，key對象被調用hashCode()方法，獲得一個hash值供hashmap使用。

我們建立一個對象來證明一下。

public class MyKey {
    private int id;
    
    @Override
    public int hashCode() {
        System.out.println("調用 hashCode()");
        return id;
    }

    // constructor, setters and getters 
}

   @Test
    public void mapKeyTest(){
        HashMap<MyKey,String> map = new HashMap<MyKey, String>();
        String retV = map.put(new MyKey(1),"value1");
    }
           

可以看到控制台的輸出資訊

調用 hashCode()
           

知識點二： hash()方法計算出的hash值可以辨別它在buckets數組中的索引位置。

HashMap的hash()方法如下：可以與put方法進行關聯。

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

HashMap有一個特點，它可以存儲null的key和null的value。當key時null的時候，執行put方法，它會自動配置設定hash為0. 這也意味着key為null的時候沒有hash操作，這樣就避免了空指針異常。

get() 方法

為了擷取存儲在hashMap中的對象，我們需要知道與它對應的key。然後通過get方法把對應的key傳到參數裡。調用HashMap的get方法的時候，也會調用key對象的hashCode方法。

@Test
    public void mapKeyTest(){
        HashMap<MyKey,String> map = new HashMap<MyKey, String>();
        MyKey key1 = new MyKey(1);
        map.put(key1,"value1");
        String retV =  map.get(key1);
    }
           

控制台上可以看到兩行輸出

調用 hashCode()
調用 hashCode()
           

HashMap中的集合視圖

HashMap提供了三種方式，讓我們可以把key和value作為其它集合來使用。

Set<K> keys = map.keySet()
Collection<V> values = map.values()
Set<Entry<K, V>> entries = map.entrySet();
           

注意： 在iteators建立完畢後，對map的任何結構修改，都會抛出一個異常。

@Test
public void givenIterator_whenFailsFastOnModification_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");
 
    Set<String> keys = map.keySet();
    Iterator<String> it = keys.iterator();
    map.remove("type");
    while (it.hasNext()) {
        String key = it.next();
    }
}

// 會抛出java.util.ConcurrentModificationException異常
           

HashMap中唯一允許的修改是在iterator中移除元素。

public void givenIterator_whenRemoveWorks_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");
 
    Set<String> keys = map.keySet();
    Iterator<String> it = keys.iterator();
 
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
 
    assertEquals(0, map.size());
}

           

HashMap在iterator上的性能相比于LinkedHashMap和treeMap，性能非常糟糕。最差情況下為O(n)，n為hashmap中條目的個數。

HashMap性能

HashMap的性能主要有兩個參數影響，初始容量和負載因子。初始容量為Map底層桶數組的長度，負載因子為當桶容量的長度為多大的時候，重新開辟新的空間。

int threshold;
    final float loadFactor;
           

預設的初始容量為16，預設的負載因子為0.75. 我們也可以自定義它們的值。

Map<String,String> hashMapWithCapacity=new HashMap<>(32);
Map<String,String> hashMapWithCapacityAndLF=new HashMap<>(32, 0.5f);
           

初始容量：

大的初始容量用于條目數較多，但是少量疊代(iteration)

小的初始容量用于條目數較少，但是多次疊代(iteration)

負載因子：

0.75是一個很折衷的方案了。在我們初始化HashMap的時候，初始容量和負載因子都應該考慮在内，比如為了減少重新hash的操作，初始容量乘以負載因子應該大于能存儲的最大條目數，這樣就不會發生重新hash的操作。

最後

HashMap内部有很多東西值得探索，這篇僅僅對HashMap做了一層表面的分析。接下來會深入分析。

百度的面試題：

HashMap的源碼，實作原理 ，底層結構。

參考

• What is the significance of load factor in HashMap?
• The Java HashMap Under the Hood