詳細分析jdk1.7的HashMap源碼

先看一段代碼

public static void main(String[] args) {
       Map<String,Object> map=new HashMap<>();
       map.put("key=1","value=100");
       Object put = map.put("key=1", "value=200");
       System.out.println(put);
   }

結果

//value=100

我們知道map中一個key只能對應一個value，我們再put這個key，會把原來的value返回回來。

為什么jdk1.7 HashMap 的實現原理：數組+鏈表

我們要向一個數組中存入一個值，我們必須知道你要存的下標
jdk是如何實現的呢

    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        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++;
        addEntry(hash, key, value, i);
        return null;
    }

可以看到它通過hash（）這個方法計算了一個hash值，再通過indexFor（）這個方法根據hash值和數組長度算出索引值i
在這里插入圖片描述
采用鏈表的結構很大程度上解決了hash沖突問題。
為什么第二個在上面，這是由于jdk1.7 采用了頭插的方式，這個下面再敘述

看一下這個indexFor方法

    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

HashMap的初始容量和擴容都是以2的次方來進行的，那么length-1換算成二進制的話肯定所有位都為1，就比如數組長度為8，2的3次方為8（1000），length-1的二進制表示就是111，而按位與計算的原則是兩位同時為“1”，結果才為“1”，否則為“0”。假設計算出來的hash值為135
135（10000111）&7（111）=7，現在，數組下標為7，所以h& (length-1)運算從數值上來講其實等價于對length取模，也就是h%length。

如果不滿足前提條件“HashMap的初始容量和擴容都是以2的次方來進行的”，會發生什么問題呢？

假設當前table的length是15，二進制表示為1111，那么length-1就是1110，此時有兩個hash值為8和9的key需要計算索引值，計算過程如下：

//8的二進制表示：1000
//8&（length-1）= 1000 & 1110 = 1000，索引值即為8;

//9的二進制表示：1001
//9&（length-1）= 1001 & 1110 = 1000，索引值也為8;

這樣一來就產生了相同的索引值，也就是說兩個hash值為8和9的key會定位到數組中的同一個位置上形成鏈表，這就產生了碰撞
同時，我們也可以發現，當數組長度為15的時候，hash值會與length-1（1110）進行按位與，那么最后一位永遠是0，而0001，0011，0101，1001，1011，0111，1101這幾個位置永遠都不能存放元素了，會造成嚴重的空間浪費，更糟的是這種情況下，數組可以使用的位置比數組長度小了很多，這意味著進一步增加了碰撞的幾率，減慢了查詢的效率。
因此可以看出，只有當數組長度為2的n次方時，不同的key計算得出的index索引相同的幾率才會較小，數據在數組上分布也比較均勻，碰撞的幾率也小，相對的，查詢的時候就不用遍歷某個位置上的鏈表，這樣查詢效率也就較高了。
此外，位運算快于十進制運算，hashmap擴容也是按位擴容，這樣同時也提高了運算效

HashMap的構造函數

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //數組默認的容量為16
    static final int MAXIMUM_CAPACITY = 1 << 30;//最大
    static final float DEFAULT_LOAD_FACTOR = 0.75f;//擴容因子
    static final Entry<?,?>[] EMPTY_TABLE = {};
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;//Entry數組
    transient int size;
    int threshold;//閾值
    final float loadFactor;
    transient int modCount;
    static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
	/*
	*initialCapacity傳進來的數組容量，loadFactor擴容因子
	*先對這兩個值進行合法判斷
	*threshold = initialCapacity;把容量賦值給了一個閾值？
	*/
    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;
        threshold = initialCapacity;
        init();
    }
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
    public HashMap(Map<? extends K, ? extends V> m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        inflateTable(threshold);

        putAllForCreate(m);
    }

put方法

	/*
	*	首先判斷table數組是否為空，如果是空的進行初始化	inflateTable（）
	*/
    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        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++;
        addEntry(hash, key, value, i);
        return null;
    }

	/*
	*	這個方法主要是對table進行初始化，table = new Entry[capacity];
	*	它為什么不直接把我們傳進來的容量作為數組大小呢，
	*	這個問題與上面容量和擴容都是2的次方數一樣
	*	int capacity = roundUpToPowerOf2(toSize);找到大于這toSize的最小2的次方數
	*	例如	7-----》8		9---------》16
	*	那么它是如何實現的？
	*/
private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);

        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }

	/*
	*	如果number》=MAXIMUM_CAPACITY 就等于MAXIMUM_CAPACITY   否則進入 (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1
	*	如果	number > 1	進入	Integer.highestOneBit((number - 1) << 1)  否則等于1
	*	這個方法的核心方法Integer.highestOneBit((number - 1) << 1)
	*	highestOneBit下面講到是找到小于等于參數值的最小2的次方數
	*	我們原本是想找到大于這toSize的最小2的次方數，這兩個方法看似完全相反
	*	我們想找》10的最小2的次方數
	*	1010 左移一位
	*	0001 1010
	*	highestOneBit（0001 1010）就是16
	*	為什么要減一，如果傳入了一個2的次方數，比如8，不減一會返回16，需要減一再左移
	*/
private static int roundUpToPowerOf2(int number) {
        // assert number >= 0 : "number must be non-negative";
        return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
    }

	/*
	*	假設我想找到	小于等于10的最小2次方數
	*	10------》1010
	*	8-------》1000
	*	
	*	現在看這個方法，假設我傳進來了一個10( ... 0000 1010)
	*	右移一位							( ... 0000 0101)  進行或運算，有一則為一
	*	結果							( ... 0000 1111)	
	*	右移兩位							( ... 0000 0011)  進行或運算
	*	結果							( ... 0000 1111)	
	*	。。。
	*	最終i=		 (  ... 0000 1111)	
	*  	i進行右移一位 （ 	... 0000 0111)進行相減
	* 	最終的返回值為(... 0000 1000) 8
	*/
public static int highestOneBit(int i) {
        // HD, Figure 3-1
        i |= (i >>  1);
        i |= (i >>  2);
        i |= (i >>  4);
        i |= (i >>  8);
        i |= (i >> 16);
        return i - (i >>> 1);
    }

本文鏈接：https://blog.csdn.net/weixin_45007916/article/details/106823327

智能推薦

freemarker + ItextRender 根據模板生成PDF文件

1. 制作模板 2. 獲取模板，并將所獲取的數據加載生成html文件 2. 生成PDF文件其中由兩個地方需要注意，都是關于獲取文件路徑的問題，由于項目部署的時候是打包成jar包形式，所以在開發過程中時直接安照傳統的獲取方法沒有一點文件，但是當打包后部署，總是出錯。于是參考網上文章，先將文件讀出來到項目的臨時目錄下，然后再按正常方式加載該臨時文件；還有一個問題至今沒有解決，就是關于生成PDF文件...

電腦空間不夠了？教你一個小秒招快速清理 Docker 占用的磁盤空間！

Docker 很占用空間，每當我們運行容器、拉取鏡像、部署應用、構建自己的鏡像時，我們的磁盤空間會被大量占用。如果你也被這個問題所困擾，咱們就一起看一下 Docker 是如何使用磁盤空間的，以及如何回收。 docker 占用的空間可以通過下面的命令查看： TYPE 列出了docker 使用磁盤的 4 種類型： Images：所有鏡像占用的空間，包括拉取下來的鏡像，和本地構建的。 Con...

requests實現全自動PPT模板

http://www.1ppt.com/moban/ 可以免費的下載PPT模板，當然如果要人工一個個下，還是挺麻煩的，我們可以利用requests輕松下載訪問這個主頁，我們可以看到下面的樣式點每一個PPT模板的圖片，我們可以進入到詳細的信息頁面，翻到下面，我們可以看到對應的下載地址點擊這個下載的按鈕，我們便可以下載對應的PPT壓縮包那我們就開始做吧首先，查看網頁的源代碼，我們可以看到每一...

SpringMvc自定義類型轉換器步驟

...

Linux C系統編程-線程互斥鎖（四）

互斥鎖互斥鎖也是屬于線程之間處理同步互斥方式，有上鎖/解鎖兩種狀態。互斥鎖函數接口 1）初始化互斥鎖 pthread_mutex_init() man 3 pthread_mutex_init (找不到的情況下首先 sudo apt-get install glibc-doc sudo apt-get install manpages-posix-dev) 動態初始化 int pthread_...