關于jdk8的hashmap

标題連結清單大于8且數組長度大于64才會将連結清單轉為紅黑樹

如果僅僅是連結清單長度大于8,而數組長度小于64,則會進行數組擴容2倍,來重新排列數組所有值

标題hashmap的預設長度必須為2的n次方,即使傳參長度設定為非2的n次方時,仍然會尋找大于其傳參最近的2的n次方作為數組的長度,

之是以會使用2的n次方,是因為在計算最後的存放位置的下标時,思路是使用>>> 然後^運算 最後&運算 ,

前面的>>>然後^運算這兩步主要是為了取到比較随機的數,而之後用&運算主要思路是用剛剛得到的随機數和數組長度取餘來得到下标,但是取餘運算對于計算機來說效率是不佳的,而sun大神發現取餘時可以用随機數和數組長度做&運算代替,但是僅限于數組長度是2的n次方的時候,是以也就是說,隻要數組的長度是2的n次方,則可以用&運算來取得餘數,而&運算時二進制運算肯定要比取餘運算快的多,

是以,這也是為什麼數組長度要是2的n方的原因,隻有這樣的時候,才可以利用&運算來高效率的取餘.

一般我們利用hash碼, 計算出在一個數組的索引, 常用方式是”h % length”, 也就是求餘的方式 . 可能是這種方式效率不高,

SUN大師們發現, “當容量一定是2^n時，h & (length - 1) == h % length” . 按位運算特别快 .

他是怎麼做到:如果傳進去的不是2的n次方,而轉為成大于本身的最接近的2的n次方呢?

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;
    }
    
這裡邏輯參考:https://blog.csdn.net/qq_27731689/article/details/95865083?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_baidulandingword~default-4.control&spm=1001.2101.3001.4242
           

這是hashmap将指定長度可以轉換為2的幂的流程

問題?:通過看如上代碼 為什麼要先cap-1,然後在做接下來的處理呢? 如上代碼:根據重複的

無符号右移,就會轉為大于自己的最接近的2的n次方,是以,如果傳進來的正好是2的n次方,就會變成大于本身2的n次方,而實際上,如果已經是2的n次方了,我們就可以直接使用了,而如果不減一,将變成比自己大的2的n次方,減去1的目的是為了處理傳進來的正好是2的幂的情況

put 的時候如果計算出下标的呢?

這個問題分為兩步

1.先取到hash值

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

從代碼可以看出他是通過key的hash值與key的hash值右移16位進行異或取到的

2.根據第一步擷取到的hash計算下标

使用取到的hash值和數組長度-1做與&運算(這裡等同于取模,之是以使用&,是因為二進制運算運算效率更高)

為什麼擴充因子是0.75?而不是存儲滿了不夠再進行擴容

如果負載因子過小,很輕易的導緻達到負載因子而頻繁擴容,導緻大量空間被浪費

如果負載因子太大:因為在每次擴容時,都需要将所有的資料重新計算,重新去排列,這些都是需要時間成本的,而負載因子過大甚至如果等到數組滿了才去擴容的話,因為很難達到到負載因子,而導緻難于擴容而産生大量hash碰撞,可能有一些連結清單中的資料量已經很長了,已經産生大量紅黑樹了,

為什麼連結清單在達到"8"時轉為了紅黑樹呢(前提是數組已經大于64)?

1.首先為什麼是8呢?而不是7或者9呢?

首先目的是什麼?

是為了防止同一連結清單過長,導緻查詢效率下降

紅黑樹本身存儲的時候是需要成本的基本上紅黑樹的占用空間時連結清單的2倍,從維護和存儲空間上都要更複雜一些,是以數量少的話,我們不建議去轉為紅黑樹的,是時間和空間的上的權衡,

之是以是8,是因為資料在存儲的時候機率是符合泊松分布的,也就是說實際上,一個連結清單在達到8而轉化為紅黑樹的機率是極低的.

從此處也可以看到,其實作者本身并不太願意轉為紅黑樹,而是連結清單過長時,采用這種方案來減少了大量的查詢時間,

為什麼連結清單增加元素時超過8轉為紅黑樹,而減少元素卻是小于6才轉回為連結清單

因為如果都設定為8的話,有可能頻繁的導緻某個位置的在紅黑樹和連結清單兩種結構頻繁互轉,畢竟轉換也是成本

hashmap在擴容時,肯定是需要重新排列所有的元素的位置把,那麼他是怎麼做的呢?

hashmap在擴容時,并不是周遊一遍,然後像增加元素時那樣,從新計算hash然後使用&取餘運算來計算元素在新數組上的位置,而是使用了一種效率更高但是仍然能達到目的的一樣方式

他是這麼做的,設計的非常巧妙,因為hashmap每次擴容時都是上次容量的2倍,與原來的hash&(n-1)隻相差一個bit位.,是以正好利用這個特性計算出恰好的特性,新的元素要不在新數組的 原位置,要不在新數組的 原位置+舊容量 的位置

那什麼時候是原位置,什麼時候是原位置+舊容量呢?

由此可見,在rehash時,并不需要重新計算hash然後計算下标,

而是用hash & oldCap(元素hash&原數組長度) 得到的最高位如果是0,那就是原下标位置,如果得到的最高位是1,那麼這個元素在新的數組的新位置就是 舊下标位置+舊數組長度=新的數組下标,

是以在新的數組上計算下标 不需要通過像之前那樣 >>> ^ & 運算來計算下标位置,