摘要:當中包括的元素變得比較少時,為了存儲空間的占用,也會轉換為節點單向鏈表的方式實現,它們之間可以互相轉換的。
hashMap是通過數組存儲所有的數據,每個元素所存放數組的下標,是根據該存儲元素的key的Hash值與該數組的長度減去1做與運算,如下所示:
index = (length_of_array - 1) & hash_of_the_key;
數組中存放元素的數據結構使用了Node和TreeNode兩種數據結構,在單個Hash值對應的存儲元素小于8個時,默認值為Node的單向鏈表形式存儲,當單個Hash值存儲的元素大于8個時,其會使用TreeNode的數據結構存儲。
因為在單個Hash值對應的元素小于等于8個時,其查詢時間最差為O(8),但是當單個Hash值對應的元素大于8個時,再通過Node的單向鏈表的方式進行查詢,速度上就會變得更慢了;這個時候HashMap就會將Node的普通節點轉為TreeNode(紅黑樹)進行存儲,這是由于TreeNode占用的空間大小約為常規節點的兩倍,但是其查詢速度可以得到保證,這個是通過空間換時間了。當TreeNode中包括的元素變得比較少時,為了存儲空間的占用,也會轉換為Node節點單向鏈表的方式實現,它們之間可以互相轉換的。
Node:
static class Nodeimplements Map.Entry { final int hash; final K key; V value; Node next; Node(int hash, K key, V value, Node next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } ......
}
可以看到每個Node中包括了4個屬性,分別為:
hash值:當前Node的Hash值
key:當前Node的key
value:當前Node的value
next:表示指向下一個Node的指針,相同hash值的Node,通過next進行遍歷查找
TreeNode:
static final class TreeNodeextends LinkedHashMap.Entry { TreeNode parent; // red-black tree links TreeNode left; TreeNode right; TreeNode prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node next) { super(hash, key, val, next); } ......
}
可以看到TreeNode使用的是紅黑樹(Red Black Tree)的數據結構,紅黑樹是一種自平衡二叉查找樹,在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡,從而獲得較高的查找性能,即使在最壞情況運行時間也是非常良好的,并且在實踐中是非常高效的,它可以在O(log n)時間內做查找、插入和刪除等操作,這里的n 是樹中元素的數目。
以下是一張關于HashMap存儲結構的示意圖:
1.寫入數據
其方法如下:
//寫入數據
public V put(K key, V value) { //首先根據hash方法,獲取對應key的hash值,計算方法見后面 return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { Node[] tab; Node p; int n, i; //判斷用戶存放元素的數組是否為空 if ((tab = table) == null || (n = tab.length) == 0) //為空則進行初使化,并將初使化后的數組賦值給變量tab,數組的長值賦值給變量n n = (tab = resize()).length; //判斷根據hash值與數組長度減1求與得到的下標, //從數組中獲取元素并將其賦值給變量p(后續該變量p可以繼續使用),并判斷該元素是否存在 if ((p = tab[i = (n - 1) & hash]) == null) //如果不存在則創建一個新的節點,并將其放到數組對應的下標中 tab[i] = newNode(hash, key, value, null); else {//根據數組的下標取到了元素,并且該元素p且不為空,下面要判斷p元素的類型是Node還是TreeNode Node e; K k; //判斷該數組對應下標取到的第一值是不是與正在存入值的hash值相同、 //key相等(可能是對象,也可能是字符串),如果相等,則將取第一個值賦值給變量e if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //判斷取的對象是不是TreeNode,如果是則執行TreeNode的put方法 else if (p instanceof TreeNode) e = ((TreeNode )p).putTreeVal(this, tab, hash, key, value); else {//是普通的Node節點, //根據next屬性對元素p執行單向鏈表的遍歷 for (int binCount = 0; ; ++binCount) { //如果被遍歷的元素最后的next為空,表示后面沒有節點了,則將新節點與當前節點的next屬性建立關系 if ((e = p.next) == null) { //做為當前節點的后面的一個節點 p.next = newNode(hash, key, value, null); //判斷當前節點的單向鏈接的數量(8個)是不是已經達到了需要將其轉換為TreeNode了 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //如果是則將當前數組下標對應的元素轉換為TreeNode treeifyBin(tab, hash); break; } //判斷待插入的元素的hash值與key是否與單向鏈表中的某個元素的hash值與key是相同的,如果是則退出 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //判斷是否找到了與待插入元素的hash值與key值都相同的元素 if (e != null) { // existing mapping for key V oldValue = e.value; //判斷是否要將舊值替換為新值 if (!onlyIfAbsent || oldValue == null) //滿足于未指定不替換或舊值為空的情況,執行將舊值替換為新值 e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
2.讀取數據
public V get(Object key) {
Nodee; //根據Key獲取元素 if ((e = getNode(hash(key), key)) == null) return null; if (accessOrder) afterNodeAccess(e); return e.value; } final Node getNode(int hash, Object key) { Node [] tab; Node first, e; int n; K k; //if語句的第一個判斷條件 if ((tab = table) != null //將數組賦值給變量tab,將判斷是否為null && (n = tab.length) > 0 //將數組的長值賦值給變量n && (first = tab[(n - 1) & hash]) != null) {//判斷根據hash和數組長度減1的與運算,計算出來的的數組下標的第一個元素是不是為空 //判斷第一個元素是否要找的元素,大部份情況下只要hash值太集中,或者元素不是很多,第一個元素往往都是需要的最終元素 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) //第一個元素就是要找的元素,因為hash值和key都相等,直接返回 return first; if ((e = first.next) != null) {//如果第一元素不是要找到的元,則判斷其next指向是否還有元素 //有元素,判斷其是否是TreeNode if (first instanceof TreeNode) //是TreeNode則根據TreeNode的方式獲取數據 return ((TreeNode )first).getTreeNode(hash, key); do {//是Node單向鏈表,則通過next循環匹配,找到就退出,否則直到匹配完最后一個元素才退出 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } //沒有找到則返回null return null; }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/77798.html
摘要:掌握的實現原理,已經是程序員的基礎操作了。后記這次主要是理解了一下的實現原理,特別重點寫了很多關于散列函數的理解,并沒有按照源碼一行行的去理解。之前看的時候對散列函數都是跳過去的,只知道是用來計算鍵的,不知道里面的原理。 序 HashMap是Java中常用的Map接口的實現類,因為在日常工作中非常頻繁的出現,所以在大部分的Java面試中都會問幾個關于HashMap的問題。掌握HashM...
摘要:的工作原理是近年來常見的面試題。讓我們再來看看這些問題設計哪些知識點的概念中解決碰撞的方法和的應用,以及它們在中的重要性不可變對象的好處多線程的條件競爭重新調整的大小總結的工作原理基于原理,我們通過和方法儲存和獲取對象。 HashMap 的工作原理是近年來常見的 Java 面試題。幾乎每個 Java 程序員都知道 HashMap,都知道哪里要用 HashMap,知道Hashtable和...
摘要:從結構實現來講,是數組鏈表紅黑樹增加了紅黑樹部分實現的。當鏈表長度大于時,將這個鏈表轉換成紅黑樹,利用紅黑樹快速增刪改查的特點提高的性能。 原文鏈接 更多教程 本文涉及HashMap的: HashMap的簡單使用 HashMap的存儲結構原理 HashMap的擴容方法原理 HashMap中定位數據索引實現 HashMap中put、get方法實現 HashMap的簡單使用 Ha...
摘要:百度網盤提取碼一面試題熟練掌握是很關鍵的,大公司不僅僅要求你會使用幾個,更多的是要你熟悉源碼實現原理,甚至要你知道有哪些不足,怎么改進,還有一些有關的一些算法,設計模式等等。 ??百度網盤??提取碼:u6C4?一、java面試題熟練掌握java是很關鍵的,大公司不僅僅要求你會使用幾個api,更多的是要你熟悉源碼實現原理,甚...
閱讀 2436·2019-08-30 15:52
閱讀 2237·2019-08-30 12:51
閱讀 2832·2019-08-29 18:41
閱讀 2812·2019-08-29 17:04
閱讀 810·2019-08-29 15:11
閱讀 1719·2019-08-28 18:02
閱讀 3602·2019-08-26 10:22
閱讀 2510·2019-08-26 10:12