HashMap結(jié)構(gòu)圖

image.png

HashMap主要方法

• final int hash(Object k)
• static int indexFor(int h, int length)
• void resize(int newCapacity)
• public V put(K key, V value)
• public V get(Object key)
• public V remove(Object key)

HashMap方法解讀

final int hash(Object k)源碼：

 final int hash(Object k) {
        int h = 0;
        if (useAltHashing) {
            if (k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;
        }
        h ^= k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

這段代碼的含義我確實搞不清楚，簡單理解的話就是做一次hash算法

static int indexFor(int h, int length)源碼：

//做一次&運算，定位到在數(shù)組的位置
 static int indexFor(int h, int length) {
        return h & (length-1);
    }

public V get(Object key)的源碼：

public V get(Object key) {
        //如果這個key為null就會放入數(shù)組的第0個位置
        if (key == null)
            return getForNullKey();
        //獲取key為非0的元素
        Entry<K,V> entry = getEntry(key);
        return null == entry ? null : entry.getValue();
    }
//獲取key為0的元素，因為數(shù)組第0個位置是一個鏈表組成，遍歷這個鏈表就可以找到對應(yīng)的值
 private V getForNullKey() {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }
//當(dāng)key不為0的時候
final Entry<K,V> getEntry(Object key) {
        //這就是之前的hash算法，算出對應(yīng)的hash值
        int hash = (key == null) ? 0 : hash(key);
        //indexFor這也就是前面講的找到數(shù)組對應(yīng)的位置
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            //判斷是否是這個key對應(yīng)的數(shù)據(jù)條件是：hash值相等&對應(yīng)的key值相等，或者key equals
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

總結(jié)起來就是：
如果這個key為null就走null的獲取方式：其實就是對數(shù)據(jù)第0個位置的鏈表進行遍歷。
如果這個key不為null就走不為null的獲取方式：首先，計算出hash值，然后，定位到在數(shù)組的位置，最后遍歷這個鏈表，條件就是hash值相等并且key相等或者equals

public V remove(Object key) 源碼為：

public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }
//真正的刪除元素
final Entry<K,V> removeEntryForKey(Object key) {
        //算hash值
        int hash = (key == null) ? 0 : hash(key);
       //定位位置
        int i = indexFor(hash, table.length);
        // 將table[i]賦值給prev
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;
        //開始遍歷刪除
        while (e != null) {
            Entry<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
                     //刪除當(dāng)前元素，把當(dāng)前元素的前一個節(jié)點指向當(dāng)前元素的后一個節(jié)點
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            //依次循環(huán)查找
            prev = e;
            e = next;
        }
        return e;
    }

總結(jié)起來就是：
第一步：算出hash；第二步：定位位置；第三步：遍歷定位位置的鏈表，找到對應(yīng)元素刪除。

public V put(K key, V value)源碼為：

 public V put(K key, V value) {
        // key為null時的put
        if (key == null)
            return putForNullKey(value);
        //hash
        int hash = hash(key);
        //index
        int i = indexFor(hash, table.length);
        //如果是index位置對應(yīng)的鏈表里面有想要put的元素，用新的元素覆蓋老的元素，**說明hashmap如果key相同的話，value會相互覆蓋**
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        //如果這個key沒有的話，新增一個entry
        addEntry(hash, key, value, i);
        return null;
    }
//新增操作
void addEntry(int hash, K key, V value, int bucketIndex) {
        //計算需要不需要擴容
        if ((size >= threshold) && (null != table[bucketIndex])) {
             //擴容操作
             resize(2 * table.length);
            //重新hash
            hash = (null != key) ? hash(key) : 0;
            //重新index
            bucketIndex = indexFor(hash, table.length);
        }
        //新增entry
        createEntry(hash, key, value, bucketIndex);
    }
//新增entry
void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }
//這個一個頭插法，新來的元素插入頭部
 Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
//擴容操作
void resize(int newCapacity) {
        //擴容操作之前的一些判斷處理，還有一些我也不足道什么意思，不過不是很重要，我們主要看一下transfer
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        Entry[] newTable = new Entry[newCapacity];
        boolean oldAltHashing = useAltHashing;
        useAltHashing |= sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash = oldAltHashing ^ useAltHashing;
        transfer(newTable, rehash);
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
//把原來的元素復(fù)制到新的數(shù)組里
void transfer(Entry[] newTable, boolean rehash) {
        //創(chuàng)建一個新的數(shù)組
        int newCapacity = newTable.length;
      //循環(huán)老的數(shù)組
        for (Entry<K,V> e : table) {
            //遍歷每一個數(shù)組對應(yīng)的鏈表
            while(null != e) {
                Entry<K,V> next = e.next;
                //hash
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                // index
                int i = indexFor(e.hash, newCapacity);
                //這一點比較bug,不是很好理解，我會貼一篇比較清楚的文章
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

put操作總結(jié)起來就是：
第一：hash,index之后找原來的鏈表查看是否存在，存在的話覆蓋掉
第二：不存在就新建一個entry，新建的前提需要考慮容量是否超過閾值，沒有超過直接新建
第三：超過閾值，就需要擴容2*size,還需要把原來的table里面的元素復(fù)制到新的table里，這里需要注意如果是多線程環(huán)境操作的話可能形成環(huán)狀結(jié)構(gòu)導(dǎo)致CPU飆升
第四：新增entry是才有頭插法，好處是不用遍歷。
這里我必須貼出一遍寫的很精彩的文章，還有他對resize的詳細介紹：
hashmap擴容機制

HashMap遍歷方式

目前我常用的就是這個了，還有其他的歡迎補充。

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

HashMap其他特性介紹

• hashmap的組成結(jié)構(gòu)為數(shù)組+鏈表。
• hashmap是非線程安全的，在多線程的環(huán)境下是會出問題的。
• hashmap 的key可以為空，value也可以為空。
• hashmap的默認數(shù)組長度為16，默認加載因子為0.75f，當(dāng)閾值的時候是會擴容的，在擴容的時候需要注意在多線程的環(huán)境里有可能出現(xiàn)環(huán)形。