男女午夜视频在线观看,99久久中文字幕伊人情人,日韩免费大片

快速入門

存儲：put 方法 put(key,value)
查詢 : get 方法 get(key)
java 代碼如下

import java.util.HashMap;
import java.util.Map;

public class App {

   public static void main(String[] args) {
       Map<String,String> map = new HashMap<>();
       map.put("劉一","劉一");
       map.put("陳二","陳二");
       map.put("張三","張三");
       map.put("李四","李四");
       map.put("王五","王五");
       map.put("Money","我是猴哥Money老師");
       System.out.println(map.get("Money"));
   }
}
//輸出結果：我是猴哥Money老師

技術的本質――底層結構

程序是等于我們的數據結構和算法

HashMap底層原理全面詳解面試絕對不慌

HashMap 其實就是做存儲的，做存儲的就是數據結構

在JDK7 : HashMap 是由數組，鏈表組成的
在JDK8: HashMap 是由數組，鏈表，紅黑樹組成的

存儲是按上面的規則存儲的，那查詢是怎么查的了

算法：哈希算法

結構構成

既然要了解HashMap 的組成，就談談它的結構組成

首先我們來說下數組，數組在java 中是怎么定義的了

    //數組：采用一段連續的存儲單元來存儲數據的
    //數組的特點: 查詢時間復雜度:0(1) ,刪除,插入,時間負責度0(N),總結：查詢塊，插入慢
    public static void main(String [] args){
        //數組的定義：初始化長度為10，數據類型Integer ,
        Integer integer[] = new Integer[10];
        //指定下標，復制
        integer[0]=0;
        //指定下標，復制
        integer[1]=1;
        //指定下標，復制
        integer[9]=2;
        //指定下標，復制
        integer[9]=400;
        System.out.println(integer[9]);
    }
    // 輸出結果：400

數組結構如圖：

HashMap底層原理全面詳解面試絕對不慌

查詢：時間復雜度 0（1）,查詢非常快的
刪除，插入：時間復雜度0（N）非常慢的，效率沒有查詢那么快

為什么查詢快，插入，刪除慢了？

查詢快

是因為我們數組了都有一個序號,如圖，0,1,2,3,4,5,… ，如果要找到下標為3的數據值, 這些序號其實就是他們的下標地址，可以理解為他們的一個下標索引，這個下標是連續的，是自增的，所以我們立馬可以確定3個這個位置，根據這個索引3 找到它對應的節點。

HashMap底層原理全面詳解面試絕對不慌

插入，刪除慢

假如我現在要出入一個Monkey 的數據，插入到3和4之間，如圖

HashMap底層原理全面詳解面試絕對不慌

存在這個位置我們是沒有下標的，則我們的下標4 則要移到 Monkey 那個位置，5下標就移到4那個位置，如圖：

HashMap底層原理全面詳解面試絕對不慌

類似，我們后面的下標都要向左移動，這樣我后面的數據是不是要做很大的改動，這樣時間復雜度則為0（N），這樣就保證了我們數組的連續性，同理刪除的話如圖：

HashMap底層原理全面詳解面試絕對不慌

數組后面數據的下標，都要還原成之前插入前的下標，后面的節點都要改變，這樣我們可以看出，這就是數組，刪除，插入為什么這么慢！
除非是插入，刪除，數組的最后一個元素，大家懂了嗎？還不懂那就私聊！

擴充：
大家知道我們java 哪一個類，底層用的就是數組？
在我們的java.util 包下面有一個ArrayList 類，如圖

HashMap底層原理全面詳解面試絕對不慌

怎么驗證了？
我們查看它的add 方法

   public boolean add(E var1) {
        this.ensureCapacityInternal(this.size + 1);
        this.elementData[this.size++] = var1;
        return true;
    }

如果面試被問到ArrayList 的特性，直接回答查詢快，插入，刪除慢

為什么要用鏈表

為什么HashMap 用到數組存儲了，還要用到鏈表了？

談談什么是鏈表？
在java 中是這么定義的：

package node;

import com.sun.org.apache.bcel.internal.generic.IMPDEP1;

public class Node {

    public Node next;
    private Object data;


    public Node(Object next) {
        this.data = next;
    }

    //鏈表：鏈表是一種物理存儲單元上非連續，非順序的存儲結構
    //特點: 插入，刪除時間復雜度0(1) 查找遍歷時間復雜度0(N) 總結：插入快,查詢慢
    public static void main(String[] args){
        Node head =new Node("monkey");
        head.next =new Node("張三");
        head.next.next =new Node("劉一");
        System.out.println(head.data);
        System.out.println(head.next.data);
        System.out.println(head.next.next.data);
    }
}
//輸出結果:
//monkey
//張三
//劉一

鏈表：鏈表是一種物理存儲單元上非連續，非順序的存儲結構,如圖：

HashMap底層原理全面詳解面試絕對不慌

為什么它插入，刪除快，查詢慢了？
刪除某個節點，只需要上一個節點 head.next =null
插入某個幾點，只需要上一個節點 head.next 指向插入的節點，插入的節點指向下一個節點
查詢某個節點：鏈表查詢都要通過頭節點，比如我們要查‘劉一"，我們則要先查頭monkey,再查張三，再查到劉一，
雖然只有3個節點，但是我們要查到劉一要查三次，把整個鏈表都遍歷了一次，所以查詢慢！

HashMap底層原理全面詳解面試絕對不慌

擴充
在我們java 中，哪一個util 類采用的鏈表來實現的?

HashMap底層原理全面詳解面試絕對不慌

我們來查看它的add 方法

   public boolean add(E var1) {
        this.linkLast(var1);
        return true;
    }
    //看上面有一個linkLast,如下:

   void linkLast(E var1) {
        LinkedList.Node var2 = this.last;
        LinkedList.Node var3 = new LinkedList.Node(var2, var1, (LinkedList.Node)null);
        this.last = var3;
        if (var2 == null) {
            this.first = var3;
        } else {
            var2.next = var3;
        }

        ++this.size;
        ++this.modCount;
    }
    //看上面有一個Node,如下:
    private static class Node<E> {
        E item;
        LinkedList.Node<E> next;
        LinkedList.Node<E> prev;

        Node(LinkedList.Node<E> var1, E var2, LinkedList.Node<E> var3) {
            this.item = var2;
            this.next = var3;
            this.prev = var1;
        }
    }
	  //上面有一個next,有一個prev 
	  //這是一個雙向鏈表

雙向鏈表如圖: 類似與分頁，上一頁，下一頁，下面的對象也可以獲取上面對象的數據（head.prev）

HashMap底層原理全面詳解面試絕對不慌

現在大家都已經了解JDK7 HashMap 數據結構了，開始了解下算法！

哈希算法

那么HashMap 是怎么去存儲的了？他是如何將數據放到我們的數組和鏈表上的？
用的就是哈希算法，你們知道哈希算法的底層是怎么實現的？
哈希表

什么是哈希算法？
哈希算法（也叫散列），就是把任意長度值（key）通過散列算法變換成固定長度的key(地址)，通過這個地址進行訪問的數據結構，
它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找速度。

HashMap底層原理全面詳解面試絕對不慌

例如圖中的John Smith 通過散列算法變換成固定長度的key:152 （永遠是152），然后通過152 變成John Smith 是不可能的，哈希算法是不可逆的。
HashCode: 通過字符串算出它的ascii 碼，進行mod(取模)，算出哈希表中的下標

HashMap底層原理全面詳解面試絕對不慌

代碼如下：

public class AsciiCode {

    public static void main(String[] args) {
        char c [] ="lies".toCharArray();
        for (int i = 0; i < c.length; i++) {
            System.out.println((c[i])+":" +(int)c[i]);
        }
    }

}
//輸出結果：
//l:108
//i:105
//e:101
//s:115

將 lies 算出來的ascii 碼相加然后除以10 取模（為什么取模不直接存儲 429了）
為什么取模不直接存儲 429了？
//數組是采用一段連續的存儲單元來存儲數據的，那存lies 數據將如圖：

HashMap底層原理全面詳解面試絕對不慌

如果你要存lies 則需要300 個這樣的內存空間，所以我們取模為10，算出來的值為 9，則節省了很多空間，我們取模的目的就是節省內存空間！

如果我們取模會出現什么問題
會出現hash 沖突(碰撞)的一個問題,

什么是hash沖突

lies 的值通過ascii 碼計算的總和為 429foes 的值通過ascii 碼計算的總和也為 429

HashMap底層原理全面詳解面試絕對不慌

兩個單詞取模后的值都是 9 ，則lies 會存在下標為9 的這個位置，foes 也存在下標為9 的這個位置，而數組存在同一個下標下面是會覆蓋的（上面代碼講數組的時候Intergers[9]=400,會覆蓋Intergers[9]=2 的值，最終Intergers[9] =400）,同樣我們先存的是lies 后存的是foes,則lies
將會被覆蓋，lies 和foes 是不同的key, 我們HashMap 是可以存這兩個值的，為什么沒有被覆蓋了？這個地方就叫做哈希碰撞！

Hash沖突怎么解決了
我們用鏈表來解決這個問題, 鏈表是有一個指針的，我們可以讓這個lies 指向這個foes,我們讓foes 去匹配下標為9 的這個節點，如果匹配lies 不相等，則去匹配下一個節點foes,最終就會找到這個foes,這就是我們hash 算法底層的原理及解決沖突。

手寫HashMap

不調用JDK7 的HashMap,自己手動寫一個HashMap

public class App {

    public static void main(String[] args) {
       //Map<String,String> map = new HashMap<>();
        App map = new App();
        map.put("劉一","劉一");
        map.put("陳二","陳二");
        map.put("張三","張三");
        map.put("李四","李四");
        map.put("王五","王五");
        map.put("Money","我是猴哥Money老師");
        //System.out.println(map.get("Money"));
    }

public void put(String key,String value){
 System.out.printf("key:%s:::::::::::::::;::hash值:%s:::::::::::::::::::存儲位置:%s
",key,key.hashCode(),Math.abs(key.hashCode() % 15));
    }
}
//輸出結果:
//    key:劉一:::::::::::::::;::hash值:671464:::::::::::::::::::存儲位置:4
//    key:陳二:::::::::::::::;::hash值:1212740:::::::::::::::::::存儲位置:5
//    key:張三:::::::::::::::;::hash值:774889:::::::::::::::::::存儲位置:4
//    key:李四:::::::::::::::;::hash值:842061:::::::::::::::::::存儲位置:6
//    key:王五:::::::::::::::;::hash值:937065:::::::::::::::::::存儲位置:0
//    key:Monkey:::::::::::::::;::hash值:-1984628749:::::::::::::::::::存儲位置:4

我們多次運行，運行的結果還是這樣，這就是hash 算法的一個特點：它是一個冪等性的一個算法

模擬我們是怎么存值的
我們一組數據就是 key,value , 可以用string,int 來存嗎？這里顯然不能，我們一般存這種值一般用對象來存值，我在這里隨便命名用個Object或者叫Entry 對象，其實我們還要存另外兩個值？（hash和next），當發生hash 沖突的時候（存儲位置4） next 可以指向下一個節點，hash 值是用來比較的,比較hashCode 值是否相等！

存取結構圖如下：

HashMap底層原理全面詳解面試絕對不慌

上面的圖形結構，我們就知道如何存數據了！

那我們該如何取數據了？
-假如我們要取‘劉一" 的值

我們通過get(key) 方法獲取數據的模，然后根據key,與hashCode 的值去比較下標為4 的key 和hashCode,查看是否相等，如果不相等我們通過next 方法比較下一個節點的數據，直到 key 與hashCode 對比的值都相等，此時，獲取value的值就是當前key 所對應的value!

HashMap底層的實現

HashMap 底層如何實現的了？我們用寫源碼的方式驗證

模擬java HashMap

定義一個Map 接口

/**
 * 自己手動定義Map
 * @param <K>
 * @param <V>
 */
public interface Map<K,V> {

    V put(K k,V v);

    V get(K k);

    int size();

     interface  Entry<K,V>{
      K getKey();
      V getValue();
     }

}

定義一個實現Map 的HashMap

import sun.management.snmp.jvmmib.JvmRTInputArgsTableMeta;

/**
 * 自己定義HashMap
 * @param <K>
 * @param <V>
 */
public class HashMap<K,V> implements Map<K,V>{

    //存儲元素對象
    private Entry<K,V> table[] = null;

    //擴容初始化
    int size =0;

    //初始化存儲元素對象大小
    public HashMap() {
        this.table = new Entry[16];
    }

    /**
     * 1.通過key hash 算法算出hash值,然后取模
     * 2.取模后就有對應的index 數組下標,然后存儲對象<Entry>
     * 3.判斷當前對象是否為空，如果空，直接存儲，
     * 4.如果不為空，我們就要用到next 鏈表
     * 5.返回當前這個節點
     * @param k
     * @param v
     * @return
     */
    @Override
    public V put(K k, V v) {
       int index = hash(k);
       Entry<K,V> entry = table[index];
       if(null ==entry){
           //劉一，陳二，李四，王五 就開始存在這個entry,每個entry 對象則存儲到了對應table 中
           table[index] = new Entry<>(k, v, index, null);
           size++;
       }else{
           //沖突了，張三，Monkey
           table[index] = new Entry<>(k, v, index, entry);
       }
        
        return table[index].getValue();
    }

    private int hash(K k) {
        //HashMap 底層用到的是移位的操作，性能高很多 >>,我們這里就直接取模
        int index =k.hashCode() % 16;
        //Math.abs(index);
        return index>0?index:-index;
    }

    /**
     * 1.通過 key 進行hash 運算，取模，找到數組對應的下標 index
     * 2.判斷當前對象是否為空,如果不為空
     * 3.判斷是否相等，如果不相等
     * 4.判斷next 是否為空，如果不為空，
     * 5.再判斷相等，知道相等為止，或者為空為止
     * 6.然后返回
     *
     *
     *
     * @param k
     * @return
     */
    @Override
    public V get(K k) {
        //如果沒有存儲數據那size 為0，也不用查了，直接返回null
        if(size ==0){
            return null;
        }
        int index = hash(k);
        Entry<K, V> entry = findValue(table[index], k);
        //通過index 找打這個對象
        return entry==null?null:entry.getValue();
    }

    /**
     *
     * @param entry
     * @param k 查詢劉一
     * @return
     */
    private Entry<K,V> findValue(Entry<K,V> entry,K k) {
        //存的可能是數值類型，也可能是字符串類型
        if (k.equals(entry.getKey()) || k == entry.getKey()) {
            return entry;
            //如果不相等，估計這個節點是個鏈表，判斷它next 數據是否匹配
        } else {
            if(entry.next !=null){
                //用到遞歸，在鏈表里面一直查詢這個k,值是否相等
                return findValue(entry.next,k);
            }
        }
        return null;
    }

    @Override
    public int size() {
        return size++;
    }



    class Entry<K,V> implements Map.Entry<K,V>{

         //存四個值
        K k;
        V v;
        int hash;
        Entry<K,V> next;

        public Entry(K k, V v, int hash, Entry<K, V> next) {
            this.k = k;
            this.v = v;
            this.hash = hash;
            this.next = next;
        }

        @Override
        public K getKey() {
            return k;
        }

        @Override
        public V getValue() {
            return v;
        }
    }

}

定義一個測試類

public class Test {

    public static void main(String[] args) {
        Map<String,String> map = new HashMap<>();
        map.put("Monkey","我是moneky老師");
        map.put("東山再起","東山再起是位好同學");
        System.out.println(map.get("Monkey"));
        System.out.println(map.get("東山再起"));
    }

//輸出結果:
//我是moneky老師
//東山再起是位好同學
}

查看到測試結果，我們就能看到HashMap ，是怎么存儲的，和獲取值的！

但是JDK8 用的是紅黑樹，為什么了？
舉個代碼的例子

import com.sun.xml.internal.ws.api.model.wsdl.WSDLOutput;

public class Test {

    public static void main(String[] args) {
        Map<String,String> map = new HashMap<>();
        for (int i = 0; i < 1000; i++) {
            map.put("Monkey"+i,"我是moneky老師"+i);
        }
        System.out.println(map);
    }
}

可以看到這個map 的size 只有16，卻存了很多的數據：

HashMap底層原理全面詳解面試絕對不慌

容量不夠，我們就只能把這個數據放到鏈表上，鏈表無線延長，這種hash沖突是十分嚴重的，而鏈表的特性是查詢慢，而鏈表又無線延長，我們查詢鏈表末端的數據，這樣性能就很低了，所以JDK8 就用紅黑樹了！

總結：解決鏈表過長查詢效率過低的問題

什么情況下用紅黑樹?

前提條件
閾值 8

HashMap 類下面有個這個：

  static final int TREEIFY_THRESHOLD = 8;

為什么要閾值是8 了？

因為紅黑叔插入慢，他要判斷小中大（也就是左邊的小于右邊的），而鏈表插入快，刪除快，但是為什么是 8 不是 6了？

HashMap底層原理全面詳解面試絕對不慌

具體原因請參考這篇Java紅黑樹的數據結構與算法解析

到此這篇關于HashMap底層原理全面詳解面試絕對不慌的文章就介紹到這了,更多相關HashMap底層原理內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！

原文鏈接：https://blog.csdn.net/weixin_39436556/article/details/118635569

一区二区三区在线-一区二区三区亚洲视频-一区二区三区亚洲-一区二区三区午夜-一区二区三区四区在线视频-一区二区三区四区在线免费观看

HashMap底層原理全面詳解面試絕對不慌

目錄

快速入門

技術的本質――底層結構

結構構成

為什么要用鏈表

哈希算法

手寫HashMap

HashMap底層的實現

什么情況下用紅黑樹?

延伸 · 閱讀

xml與Java對象的轉換詳解

Java8中Stream使用的一個注意事項

Java使用SAX解析xml的示例

20個非常實用的Java程序代碼片段

Java實現搶紅包功能

小米推送Java代碼

Java BufferWriter寫文件寫不進去或缺失數據的解決

升級IDEA后Lombok不能使用的解決方法

云服務器是什么，云主機干什么用的？

2020最新好用的web服務器軟件推薦

服務器操作系統有哪些?

web服務器配置（圖文詳解）

企業如何選擇阿里云服務器配置?

五大免費主機管理系統優缺點對比及推薦

2019最新三款Windows下連接Linux的ssh軟件下載推薦

服務器常用管理軟件盤點

Nginx服務器究竟是怎么執行PHP項目