HashMap的底層原理

2021 年 5 月 15 日
筆記

package com.programme.demo01;

import java.util.HashSet;
import java.util.List;

/**
 * @program: spring
 * @description: ${description}
 * @author: Mr.zw
 * @create: 2021-05-15 10:26
 **/
public class Demo01 {
    public static void main(String[] args) {
        HashSet<Integer> set = new HashSet<>();
        set.add(3);
        set.add(2);
        set.add(4);
        set.add(5);
        set.add(16);
        set.add(17);
        set.add(7);
        set.add(1);
        set.add(6);
        set.add(9);
        set.add(8);
        set.add(10);
        System.out.println(set);
       //輸出： [16, 17, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    }
}

　　添加元素

package com.programme.demo01;

import java.util.HashSet;
import java.util.List;

/**
 * @program: spring
 * @description: ${description}
 * @author: Mr.zw
 * @create: 2021-05-15 10:26
 **/
public class Demo01 {
    public static void main(String[] args) {
        HashSet<Integer> set = new HashSet<>();
        set.add(3);
        set.add(2);
        set.add(4);
        set.add(5);
        set.add(16);
        set.add(17);
        set.add(7);
        set.add(1);
        set.add(6);
        set.add(9);
        set.add(8);
        set.add(10);
        set.add(11);
        set.add(12);
        set.add(13);
        System.out.println(set);
        //輸出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16, 17]
    }
}

　　這裡我們的16，17到了後面去了，這涉及到哈希表的底層，set集合的底層其實也是hashmap

哈希桶也是有索引的，哈希桶的初始容量是十六

1<<4;是1左移四位，也就是1乘以2的4次方，>>表示右移除以。

假設這裡有一個元素要進來想往hashmap裡面存，先是用hashcode.equals判斷是否有值然後通過put存放進去

通過計算哈希值來放入tab中也就等於我們的數組中

通過這個方法計算哈希值擾亂函數低十六位異或高十六位這個操作叫做擾亂函數

將計算的哈希值右移16位，讓哈希值盡量分散開，查詢map的時候盡量快一點，所以也哈希表也叫散列表

異或相同為0不同為1

計算出來的哈希值這麼大怎麼將元素存入一個索引為0-15的哈希表去

長度必須是二的幾次方

如果我們自定義的容量不是二的幾次方也會強轉為2的次方

這麼做的目的就是為了計算存放索引

默認長度16的的2進位是10000 看源碼的操作

這裡將10000-1得到1111 再進行與操作得到0101也就是5索引這種操作叫做路由定址

我們將元素存到5索引

假設這個又來個一個元素通過計算也存到了5索引就發生了哈希碰撞（哈希衝突）第一個存進去的元素後面有個拉鏈將他們拉起來 1.7是頭插法1.8是尾插法

如果我們的數組存滿了就會擴容，比如16擴容成了32，不能讓後面16位空著，要盡量讓它散列，1.7會出現環形鏈表也就是著名的約瑟夫環問題。

在 Java 1.8 中，如果鏈表長度到8，數組容量到64，鏈表會樹化；刪除元素紅黑樹長度小於6，紅黑樹退化為鏈表;（這裡的數組容量指的是數組長度，不是64個元素）

何時擴容數組中長度*載入因子（0.75)個位置上都有元素，再存會擴容

16乘以0.75等於12

package com.programme.demo01;

import com.sun.org.apache.xpath.internal.operations.Equals;

import java.util.HashSet;
import java.util.List;

/**
 * @program: spring
 * @description: ${description}
 * @author: Mr.zw
 * @create: 2021-05-15 10:26
 **/
public class Demo01 {
    public static void main(String[] args) {
        HashSet<Integer> set = new HashSet<>();

        set.add(3);//1
        set.add(2);//2
        set.add(4);//3
        set.add(5);//4
        set.add(16);//5
        set.add(17);//6
        set.add(7);//7
        set.add(1);//8
        set.add(6);//9
        set.add(9);//10
        set.add(8);//11
        set.add(10);//12
        set.add(11);//13
        //輸出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 16, 17]
        System.out.println(set);
    }
}

package com.programme.demo01;

import com.sun.org.apache.xpath.internal.operations.Equals;

import java.util.HashSet;


/**
 * @program: spring
 * @description: ${description}
 * @author: Mr.zw
 * @create: 2021-05-15 10:26
 **/
public class Demo01 {
    public static void main(String[] args) {
        HashSet<Integer> set = new HashSet<>();

        set.add(3);//1
        set.add(2);//2
        set.add(4);//3
        set.add(5);//4
        set.add(16);//5
        set.add(17);//6
        set.add(7);//7
        set.add(1);//8
        set.add(6);//9
        set.add(9);//10
        set.add(8);//11
        set.add(10);//12
        //輸出：[16, 17, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
        System.out.println(set);
    }
}

package com.programme.demo01;

import com.sun.org.apache.xpath.internal.operations.Equals;

import java.util.HashSet;


/**
 * @program: spring
 * @description: ${description}
 * @author: Mr.zw
 * @create: 2021-05-15 10:26
 **/
public class Demo01 {
    public static void main(String[] args) {
        HashSet<Integer> set = new HashSet<>();

        set.add(3);//1
        set.add(2);//2
        set.add(4);//3
        set.add(5);//4
        set.add(16);//5
        set.add(17);//6
        set.add(0);//7
        set.add(1);//8
        set.add(6);//9
        set.add(9);//10
        set.add(8);//11
        set.add(10);//12 16乘以0.75=13 未擴容
        //輸出：[16, 17, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
        //16計算索引是0 17計算索引是1   16和0在一個鏈上 17和1在一個鏈上
        System.out.println(set);
    }
}

　　擴容一下

package com.programme.demo01;

import com.sun.org.apache.xpath.internal.operations.Equals;

import java.util.HashSet;


/**
 * @program: spring
 * @description: ${description}
 * @author: Mr.zw
 * @create: 2021-05-15 10:26
 **/
public class Demo01 {
    public static void main(String[] args) {
        HashSet<Integer> set = new HashSet<>();

        set.add(3);//1
        set.add(2);//2
        set.add(4);//3
        set.add(5);//4
        set.add(16);//5
        set.add(17);//6
        set.add(0);//7
        set.add(1);//8
        set.add(6);//9
        set.add(9);//10
        set.add(8);//11
        set.add(10);//12
        set.add(11);//13 已擴容
        //輸出：[0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 16, 17] 16 17被分到擴容的位置上去了
        System.out.println(set);
    }
}

　　在擴容的時候會將鏈表分成低位鏈和高位鏈，擴容時低位鏈不變，高位鏈分配是原索引加原長度（下圖原索引為1原長度為16，擴容後分配到17索引）