HashMap具有以下特點：

Hashmap是基于Map的非同步實現(xiàn)，如果多線程修改，必須在外部保持同步
允許使用null值和null鍵
不保證映射順序
Hashmap實際上是一個鏈表散列的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體
Hashmap底層是一個數(shù)組，數(shù)組中每一項又是一個鏈表
默認容量 = 4(必須是2的n次方), 默認加載因子 = 0.75
只有對于HashMap中的Entry有新增或刪除的操作，都會更新modCount

假定Hash函數(shù)將元素適當?shù)姆植荚诟魍爸g，可為基本操作get和put提供穩(wěn)定的性能，迭代collection視圖所需的時間與HashMap實例的容量(桶的數(shù)量）及其大小(鍵值映射關(guān)系數(shù))成比例，所以如果迭代性能很重要，則不要將出示容量設(shè)置的太高或?qū)⒓虞d因子設(shè)置的太低

成員變量

    //默認初始容量為4
    staic final int DEFAULT_INITIAL_CAPACITY = 4;

    static final int MAXIMUM_CAPACITY = 1 << 30;

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    static final HashMapEntry<?,?>[] EMPTY_TABLE = {};

    transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;

    transient int size;

    int threshold;

    final float loadFactor = DEFAULT_LOAD_FACTOR;

    transient int modCount;

構(gòu)造函數(shù)

    public HashMap() {
        //默認容量是4, 加載因子是0.75
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                    initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY) {
            initialCapacity = MAXIMUM_CAPACITY;
        } else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
            initialCapacity = DEFAULT_INITIAL_CAPACITY;
        }

        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                    loadFactor);

        threshold = initialCapacity;
        init();
    }

一般情況下，我們使用HashMap時都會調(diào)用空參構(gòu)造函數(shù)，可以看到，空參構(gòu)造函數(shù)的初始容量默認為4

方法

1. put

    public V put(K key, V value) {
        //如果table是空，重新初始化table,容量是threshold，如果是空構(gòu)造函數(shù)，threshold就是4
        if (table == EMPTY_TABLE) {
            //【1.1】
            inflateTable(threshold);
        }
        //如果key是null, 更新相應(yīng)的Entry, key = null， 則Entry放在table[0]
        if (key == null)
            //【1.2】
            return putForNullKey(value);

        //計算hash值， 【1.3】
        int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
        //獲取hash值對應(yīng)的index位置， 【1.4】
        int i = indexFor(hash, table.length);
        //如果對應(yīng)的index位置已經(jīng)有鏈表，證明hash沖突，遍歷鏈表
        for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //如果鏈表中某一個entry的key值與傳入的key值相等，更新entry對應(yīng)的value值
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        //如果沒有hash沖突或者在hash沖突的鏈表中沒有相等的key值，更新modCount
        modCount++;
        //添加新的Entry， 【1.5】
        addEntry(hash, key, value, i);
        return null;
    }

key = null時，對應(yīng)的Entry放置在索引0處
如果key值存在了，新的value會替換舊的value，put方法會返回舊value
計算對應(yīng)的索引值的方法是, 獲取key值hash值，然后用hash & table.length - 1, table.length總是2的n次方

對于任意給定對象，只要其hashCode()返回值相同，那么HashMap計算出來的hash值也總相同

1.1 inflateTable

    private void inflateTable(int toSize) {
        // 保證HashMap的容量是2的n次方
        int capacity = roundUpToPowerOf2(toSize);

        //計算threshold值
        float thresholdFloat = capacity * loadFactor;
        if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
            thresholdFloat = MAXIMUM_CAPACITY + 1;
        }

        threshold = (int) thresholdFloat;
        table = new HashMapEntry[capacity];
    }
    
    private static int roundUpToPowerOf2(int number) {
        // assert number >= 0 : "number must be non-negative";
        int rounded = number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (rounded = Integer.highestOneBit(number)) != 0
                //Integer.bitCount返回number的二進制補碼中1的總數(shù)量
                ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
                : 1;

        return rounded;
    }

HashMap的容量會強制性的圓整到2的n次方，即使在初始化時傳入的初始容量不是2的n次方，這樣做是為了減少hash碰撞率從而提升空間利用效率

1.2 Hashing.singleWordWangJenkinsHash

    public static int singleWordWangJenkinsHash(Object k) {
        int h = k.hashCode();

        h += (h <<  15) ^ 0xffffcd7d;
        h ^= (h >>> 10); //無符號右移6位
        h += (h <<   3);
        h ^= (h >>>  6);//無符號右移6位,空位以0補齊, 帶符號右移是根據(jù)最左邊的符號位來確定空位補什么，如果符號位是1，則空位補1,符號位是0，空位補0
        h += (h <<   2) + (h << 14);
        return h ^ (h >>> 16);
    }

1.3 putForNullKey

    private V putForNullKey(V value) {
        //如果null已經(jīng)有對應(yīng)的value,則替換舊value為新value
        for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

null可以做鍵值，但是null所對應(yīng)的value每次只能存一個，如果已存在以null為鍵值的Entry, 會有新的value替換舊value

1.4 indexFor

    
    static int indexFor(int h, int length) {
        //length總是2的n次方時， h & (length - 1)等價于對length取模,h % length
        return h & (length-1);
    }

由于pow(2, n)是2的n次方，所以pow(2,n) - 1的二進制必然每一位都是1，這樣用hash值同pow(2,n)-1進行位與操作，得到的值得低位與hash值得低位一致

1.5 addEntry

    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            //如果key-value鍵值對數(shù)量達到threshold且對應(yīng)index處有Entry即存在鏈表, 擴容
            resize(2 * table.length);
            //計算hash值，null鍵值的hash是0
            hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        //創(chuàng)建新的Entry,并放入對應(yīng)的位置
        createEntry(hash, key, value, bucketIndex);
    }
    
        void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMapEntry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
        size++;
    }

如果key-value鍵值對的總和達到threshold且對應(yīng)的索引處存在鏈表，進行擴容
創(chuàng)建新的Entry,并放入table中

2. get

    public V get(Object key) {
        //如果key為null, 獲取null對應(yīng)的value
        if (key == null)
            //【2.1】
            return getForNullKey();
        //【2.2】
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

2.1 getForNullKey

    private V getForNullKey() {
        if (size == 0) {
            return null;
        }
        for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

2.2 getEntry


    final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
        for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

這里吐槽一下：曾經(jīng)遇到一個面試官問我如果哈希沖突的時候HashMap是通過什么方式獲取value的，我很確定的說會遍歷鏈表，然后判斷entry的哈希值是否跟key值計算出來的hash值相等同時會判斷entry的key值和傳入的key是否會相等，然后那個面試官告訴我不對!!!弄得我一臉懵逼，我說就是這樣的啊，結(jié)果他可能覺得我知錯不改，臉色不太好的告訴我回去再好好看看。。。好吧，我現(xiàn)在再一次好好看了，依然不知道我哪里說錯了，也許這位大哥可能有自己獨特的理解

3. remove

    public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.getValue());
    }
    
    final Entry<K,V> removeEntryForKey(Object key) {
        if (size == 0) {
            return null;
        }
        int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
        int i = indexFor(hash, table.length);
        HashMapEntry<K,V> prev = table[i];
        HashMapEntry<K,V> e = prev;

        while (e != null) {
            HashMapEntry<K,V> next = e.next;
            Object k;
            if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }

        return e;
    }

刪除元素其實也是首先計算has值，之后會根據(jù)hash值回去元素的索引值，之后遍歷索引位置處的鏈表，之后再進行entry的比對，如果想等，就會刪除這個元素，這里要注意的是之前提到過的一旦HashMap中的元素發(fā)生刪除或增加的改變時，會增加modCount

4. 遍歷HashMap

一般遍歷HashMap都是通過迭代器來遍歷:


    Iterator iter = map.entrySet().iterator();
　while (iter.hasNext()) {
　　     Map.Entry entry = (Map.Entry) iter.next();
　　    Object key = entry.getKey();
　　    Object val = entry.getValue();
  }

用迭代器來遍歷Hashmap時，不可以調(diào)用put或remove這樣會更改HashMap中Entry數(shù)量的操作，如果調(diào)用了，會拋出ConcurrentModificationException，這是因為fast-fail機制，至于具體原因，從下面的代碼分析中可以知道

4.1 entrySet

    public Set<Map.Entry<K,V>> entrySet() {
        return entrySet0();
    }

    private Set<Map.Entry<K,V>> entrySet0() {
        Set<Map.Entry<K,V>> es = entrySet;
        return es != null ? es : (entrySet = new EntrySet());
    }

調(diào)用entrySet()以后會返回一個EntrySet對象

4.2 EntrySet.iterator

    public Iterator<Map.Entry<K,V>> iterator() {
        return newEntryIterator();
    }
        
    Iterator<Map.Entry<K,V>> newEntryIterator()   {
        return new EntryIterator();
    }

EntryIterator繼承自HashIterator, EntryIterator.next實際調(diào)用的是其父類HashIterator.nextEntry()

4.3 HashIterator構(gòu)造函數(shù)

    private abstract class HashIterator<E> implements Iterator<E> {
        HashMapEntry<K,V> next;        // next entry to return
        int expectedModCount;   // For fast-fail
        int index;              // current slot
        HashMapEntry<K,V> current;     // current entry

        HashIterator() {
            expectedModCount = modCount;
            if (size > 0) { // advance to first entry
                HashMapEntry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
        }
        ...
        
   }

在HashIterator中有一個很重要的變量expectedModCount, 可以看到在構(gòu)造函數(shù)中將它的值攝為了HashMap.modCount，這就意味著HashIterator對象一旦創(chuàng)建，expectedModCount值就是固定的，如果在用迭代器遍歷HashMap時進行put或remove，那么modCount值必然會和expectedModCount不相等，一旦不相等，就會拋出ConcurrentModificationException

4.4 HashIterator.nextEntry

    final Entry<K,V> nextEntry() {
          if (modCount != expectedModCount)
              throw new ConcurrentModificationException();

          HashMapEntry<K,V> e = next;
          if (e == null)
              throw new NoSuchElementException();

          if ((next = e.next) == null) {
              HashMapEntry[] t = table;
              while (index < t.length && (next = t[index++]) == null)
                    ;
          }
          current = e;
          return e;
    }

可以看到，正如之前所說，當expectedModCount != modCount時，會拋出ConcurrentModificationException, 那如果想在遍歷的時候也可以進行刪除操作，應(yīng)該通過什么方法呢？答案是通過Iterator.remove

4.5 HashIterator.remove

    public void remove() {
        if (current == null)
             throw new IllegalStateException();

         if (modCount != expectedModCount)
              throw new ConcurrentModificationException();

         Object k = current.key;
         current = null;
         HashMap.this.removeEntryForKey(k);
         expectedModCount = modCount;
    }

由于HashIterator是HashMap的內(nèi)部類，所以可以調(diào)用HashMap的內(nèi)部方法removeEntryForKey，當刪除完entry后，會更新expectedModCount,這樣在進行下一次的next()調(diào)用時， expectedModCount就會與modCount保持一致

5. 遍歷key和遍歷value

如果通過迭代器遍歷key和遍歷value時的注意事項跟用迭代器遍歷HashMap的注意事項一樣，也是不可以在遍歷時調(diào)用remove方法，原理也是一樣的，內(nèi)部有一個expectedModCount，如果要刪除要掉用迭代器的remove方法

6. Java8新特性

在Java8中新增了forEach方法，接收一個BiConsumere<? super K, ? super V>參數(shù)，這個參數(shù)是一個函數(shù)式接口，所謂函數(shù)式接口是指接口只有一個待實現(xiàn)的方法(Java8中，接口可以有默認的實現(xiàn)), 函數(shù)式接口可以用lambda表達式來代替, BiConsumer<K, V>的lambda表達式原型是(K, V) - Void, 即傳入K,V, 返回Void

參考

HashMap的實現(xiàn)原理

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

HashMap源碼分析

HashMap源碼分析

成員變量

構(gòu)造函數(shù)

方法

1. put

1.1 inflateTable

1.2 Hashing.singleWordWangJenkinsHash

1.3 putForNullKey

1.4 indexFor

1.5 addEntry

2. get

2.1 getForNullKey

2.2 getEntry

3. remove

4. 遍歷HashMap

4.1 entrySet

4.2 EntrySet.iterator

4.3 HashIterator構(gòu)造函數(shù)

4.4 HashIterator.nextEntry

4.5 HashIterator.remove

5. 遍歷key和遍歷value

6. Java8新特性

參考

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

HashMap源碼分析

成員變量

構(gòu)造函數(shù)

方法

1. put

1.1 inflateTable

1.2 Hashing.singleWordWangJenkinsHash

1.3 putForNullKey

1.4 indexFor

1.5 addEntry

2. get

2.1 getForNullKey

2.2 getEntry

3. remove

4. 遍歷HashMap

4.1 entrySet

4.2 EntrySet.iterator

4.3 HashIterator構(gòu)造函數(shù)

4.4 HashIterator.nextEntry

4.5 HashIterator.remove

5. 遍歷key和遍歷value

6. Java8新特性

參考

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av