點關注，不迷路！

快速開始HashMap相信大家在日常的開發中都用過，首先我們快速回憶下。

public class App { public static void main(String[] args) { //Map map = new HashMap<>(); App map=new App(); map.put("劉一", "劉一"); map.put("陳二", "陳二"); map.put("張三", "張三"); map.put("李四", "李四"); map.put("王五", "王五"); map.put("springboot", "原始碼學院-只為培養BAT程式設計師而生"); System.out.println(map.get("springboot")); }

hashmap在我們日常工作一般用的多的就是其put方法和get方法。

技術本質

現在我們已經對hashmap有一個大致的了解了，接下來我們要去了解其底層的原理，也就是本質。

很多朋友在面試的時候經常被問到hashmap底層實現原理？都說是資料+連結串列 ok！估計大家都會被了但是真正知道底層如何儲存的我相信不多，不急 我們來看下陣列和連結串列的定義

陣列

陣列：採用一段連續的儲存單元來儲存資料。對於指定下標的查詢，時間複雜度為O(1)；對於一般的插入刪除操作，涉及到陣列元素的移動，其平均複雜度也為O(n)

Java程式碼表示

 //陣列:採用一段連續的儲存單元來儲存資料。 //特點:指定下標O(1) 刪除插入O（N） 陣列：查詢快 插入慢 ArrayList public static void main(String[] args) { Integer[] integers = new Integer[10]; integers[0]=0;//王五 integers[1]=1; integers[2]=2; integers[9]=9;

連結串列連結串列是一種物理儲存單元上非連續、非順序的儲存結構，資料元素的邏輯順序是通過連結串列中的指標連結次序實現的對於連結串列的新增，刪除等操作（在找到指定操作位置後），僅需處理結點間的引用即可，時間複雜度為O(1)，而查詢操作需要遍歷連結串列逐一進行比對，複雜度為O(n)

public class Node { public Node next; private Object data; public Node(Object data) { this.data = data; } //連結串列：連結串列是一種物理儲存單元上非連續、非順序的儲存結構 //特點：插入、刪除時間複雜度O（1） 查詢遍歷時間複雜度0（N） 插入快 查詢慢 public static void main(String[] args) { Node node=new Node(15); node.next=new Node(1); node.next.next=new Node(9); }

雜湊演算法雜湊演算法（也叫雜湊），就是把任意長度值(Key)通過雜湊演算法變換成固定長度的key地址，通過這個地址進行訪問的資料結構。它通過把關鍵碼值對映到表中一個位置來訪問記錄，以加快查詢的速度。

實現原理剛才我們分析了hashmap由陣列+連結串列構成，介紹了陣列+連結串列的描述，接下來我們就把這兩個資料結構整合在一起吧，在整合在一起， 我們寫一個偽put程式碼。

 /*** * 輸出 key value hashcode 等 hash演算法 * @param key * @param value */ public void put(String key, String value) { //hash函式 System.out.printf("key:%s,hash值:%s,儲存位置:%s\\r\\n", key, key.hashCode(), Math.abs(key.hashCode() % 15)); }

執行程式碼如下

key:劉一,hash值:671464,儲存位置:4key:陳二,hash值:1212740,儲存位置:5key:張三,hash值:774889,儲存位置:4key:李四,hash值:842061,儲存位置:6key:王五,hash值:937065,儲存位置:0key:springboot,hash值:1362194047,儲存位置:7

對應的圖形儲存結構就是：

實現根據我們圖形的演示，你能手寫實現嗎？

public interface Map<K,V> { public V put(K k,V v); public V get(K k); public int size(); interface Entry<K,V>{ public K getKey(); public V getValue(); }}

具體實現：關注我的公眾號，輸入關鍵字hashmap即可下載原始碼。歡迎關注公眾號：Java大型網站架構