<dl id="opymh"></dl>

<div id="opymh"></div>
      <div id="opymh"><tr id="opymh"></tr></div>

        <em id="opymh"><ins id="opymh"><mark id="opymh"></mark></ins></em><sup id="opymh"><menu id="opymh"></menu></sup>

        <em id="opymh"></em>

        <em id="opymh"><ol id="opymh"></ol></em>

              頻道欄目
              首頁 > 程序開發 > 軟件開發 > Java > 正文
              java中的Map接口實現類TreeMap、HashMap、WeakHashMap、HashTable的實例講解
              2018-07-27 15:24:39         來源:調皮的寫代碼  
              收藏   我要投稿

              一、Map的簡介

              二、HashMap源碼解讀

              1)HashMap的特點

              HashMap是基于哈希表實現的,每一個元素是一個key-value對,其內部通過單鏈表解決沖突問題,容量不足(超過了閥值)時,同樣會自動增長;

              HashMap是非線程安全的,只是用于單線程環境下,多線程環境下可以采用concurrent并發包下的concurrentHashMap;

              HashMap實現了Serializable接口,因此它支持序列化;

              實現了Cloneable接口,能被克隆。

              2)HashMap的源碼講解(jdk1.7)參考附屬文件的代碼,原文中有注解,下載

              3)HashMap的總結

              首先要清楚HashMap的存儲結構,如下圖所示:

              \

              圖中,紫色部分即代表哈希表,也稱為哈希數組,數組的每個元素都是一個單鏈表的頭節點,鏈表是用來解決沖突的,如果不同的key映射到了數組的同一位置處,就將其放入單鏈表中。

              首先看鏈表中節點的數據結構:

              // Entry是單向鏈表。  
               // 它是 “HashMap鏈式存儲法”對應的鏈表。  
               // 它實現了Map.Entry 接口,即實現getKey(), getValue(), setValue(V value), equals(Object o), hashCode()這些函數  
               static class Entry implements Map.Entry {  
                final K key;  
                V value;  
                // 指向下一個節點  
                Entry next;  
                final int hash;  
               
                // 構造函數。  
                // 輸入參數包括"哈希值(h)", "鍵(k)", "值(v)", "下一節點(n)"  
                Entry(int h, K k, V v, Entry n) {  
              value = v;  
              next = n;  
              key = k;  
              hash = h;  
                }  
               
                public final K getKey() {  
              return key;  
                }  
               
                public final V getValue() {  
              return value;  
                }  
               
                public final V setValue(V newValue) {  
              V oldValue = value;  
              value = newValue;  
              return oldValue;  
                }  
               
                // 判斷兩個Entry是否相等  
                // 若兩個Entry的“key”和“value”都相等,則返回true。  
                // 否則,返回false  
                public final boolean equals(Object o) {  
              if (!(o instanceof Map.Entry))  
               return false;  
              Map.Entry e = (Map.Entry)o;  
              Object k1 = getKey();  
              Object k2 = e.getKey();  
              if (k1 == k2 || (k1 != null && k1.equals(k2))) {  
               Object v1 = getValue();  
               Object v2 = e.getValue();  
               if (v1 == v2 || (v1 != null && v1.equals(v2)))  
                return true;  
              }  
              return false;  
                }  
               
                // 實現hashCode()  
                public final int hashCode() {  
              return (key==null 0 : key.hashCode()) ^  
               (value==null  0 : value.hashCode());  
                }  
               
                public final String toString() {  
              return getKey() + "=" + getValue();  
                }  
               
                // 當向HashMap中添加元素時,繪調用recordAccess()。  
                // 這里不做任何處理  
                void recordAccess(HashMap m) {  
                }  
               
                // 當從HashMap中刪除元素時,繪調用recordRemoval()。  
                // 這里不做任何處理  
                void recordRemoval(HashMap m) {  
                }  
               }

              它的結構元素除了key、value、hash外,還有next,next指向下一個節點。另外,這里覆寫了equals和hashCode方法來保證鍵值對的獨一無二。

              HashMap共有四個構造方法。構造方法中提到了兩個很重要的參數:初始容量和加載因子。這兩個參數是影響HashMap性能的重要參數,其中容量表示哈希表中槽的數量(即哈希數組的長度),初始容量是創建哈希表時的容量(從構造函數中可以看出,如果不指明,則默認為16),加載因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度,當哈希表中的條目數超出了加載因子與當前容量的乘積時,則要對該哈希表進行 resize 操作(即擴容)。

              下面說下加載因子,如果加載因子越大,對空間的利用更充分,但是查找效率會降低(鏈表長度會越來越長);如果加載因子太小,那么表中的數據將過于稀疏(很多空間還沒用,就開始擴容了),對空間造成嚴重浪費。如果我們在構造方法中不指定,則系統默認加載因子為0.75,這是一個比較理想的值,一般情況下我們是無需修改的。

              另外,無論我們指定的容量為多少,構造方法都會將實際容量設為不小于指定容量的2的次方的一個數,且最大值不能超過2的30次方

              HashMap中key和value都允許為null。

              要重點分析下HashMap中用的最多的兩個方法put和get。先從比較簡單的get方法著手,源碼如下:

                // 獲取key對應的value  
               public V get(Object key) {  
                if (key == null)  
              return getForNullKey();  
                // 獲取key的hash值  
                int hash = hash(key.hashCode());  
                // 在“該hash值對應的鏈表”上查找“鍵值等于key”的元素  
                for (Entry e = table[indexFor(hash, table.length)];  
               e != null;  
               e = e.next) {  
              Object k;  
              			//判斷key是否相同
              if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
               return e.value;  
                }
              		//沒找到則返回null
                return null;  
               }  
               
               // 獲取“key為null”的元素的值  
               // HashMap將“key為null”的元素存儲在table[0]位置,但不一定是該鏈表的第一個位置!  
               private V getForNullKey() {  
                for (Entry e = table[0]; e != null; e = e.next) {  
              if (e.key == null)  
               return e.value;  
                }  
                return null;  
               } 

              首先,如果key為null,則直接從哈希表的第一個位置table[0]對應的鏈表上查找。記住,key為null的鍵值對永遠都放在以table[0]為頭結點的鏈表中,當然不一定是存放在頭結點table[0]中。

              如果key不為null,則先求的key的hash值,根據hash值找到在table中的索引,在該索引對應的單鏈表中查找是否有鍵值對的key與目標key相等,有就返回對應的value,沒有則返回null。

              put方法稍微復雜些,代碼如下:

              // 將“key-value”添加到HashMap中  
               public V put(K key, V value) {  
                // 若“key為null”,則將該鍵值對添加到table[0]中。  
                if (key == null)  
              return putForNullKey(value);  
                // 若“key不為null”,則計算該key的哈希值,然后將其添加到該哈希值對應的鏈表中。  
                int hash = hash(key.hashCode());  
                int i = indexFor(hash, table.length);  
                for (Entry e = table[i]; e != null; e = e.next) {  
              Object k;  
              // 若“該key”對應的鍵值對已經存在,則用新的value取代舊的value。然后退出!  
              if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
               V oldValue = e.value;  
               e.value = value;  
               e.recordAccess(this);  
               return oldValue;  
              }  
                }  
               
                // 若“該key”對應的鍵值對不存在,則將“key-value”添加到table中  
                modCount++;
              		//將key-value添加到table[i]處
                addEntry(hash, key, value, i);  
                return null;  
               }

              如果key為null,則將其添加到table[0]對應的鏈表中,putForNullKey的源碼如下:

              // putForNullKey()的作用是將“key為null”鍵值對添加到table[0]位置  
               private V putForNullKey(V value) {  
                for (Entry e = table[0]; e != null; e = e.next) {  
              if (e.key == null) {  
               V oldValue = e.value;  
               e.value = value;  
               e.recordAccess(this);  
               return oldValue;  
              }  
                }  
                // 如果沒有存在key為null的鍵值對,則直接題阿見到table[0]處!  
                modCount++;  
                addEntry(0, null, value, 0);  
                return null;  
               }

              如果key不為null,則同樣先求出key的hash值,根據hash值得出在table中的索引,而后遍歷對應的單鏈表,如果單鏈表中存在與目標key相等的鍵值對,則將新的value覆蓋舊的value,比將舊的value返回,如果找不到與目標key相等的鍵值對,或者該單鏈表為空,則將該鍵值對插入到改單鏈表的頭結點位置(每次新插入的節點都是放在頭結點的位置),該操作是有addEntry方法實現的,它的源碼如下:

              // 新增Entry。將“key-value”插入指定位置,bucketIndex是位置索引。  
               void addEntry(int hash, K key, V value, int bucketIndex) {  
                // 保存“bucketIndex”位置的值到“e”中  
                Entry e = table[bucketIndex];  
                // 設置“bucketIndex”位置的元素為“新Entry”,  
                // 設置“e”為“新Entry的下一個節點”  
                table[bucketIndex] = new Entry(hash, key, value, e);  
                // 若HashMap的實際大小 不小于 “閾值”,則調整HashMap的大小  
                if (size++ >= threshold)  
              resize(2 * table.length);  
               } 

              注意這里倒數第三行的構造方法,將key-value鍵值對賦給table[bucketIndex],并將其next指向元素e,這便將key-value放到了頭結點中,并將之前的頭結點接在了它的后面。該方法也說明,每次put鍵值對的時候,總是將新的該鍵值對放在table[bucketIndex]處(即頭結點處)。

              兩外注意最后兩行代碼,每次加入鍵值對時,都要判斷當前已用的槽的數目是否大于等于閥值(容量*加載因子),如果大于等于,則進行擴容,將容量擴為原來容量的2倍。

              6、關于擴容。上面我們看到了擴容的方法,resize方法,它的源碼如下:

               // 重新調整HashMap的大小,newCapacity是調整后的單位  
               void resize(int newCapacity) {  
                Entry[] oldTable = table;  
                int oldCapacity = oldTable.length;  
                if (oldCapacity == MAXIMUM_CAPACITY) {  
              threshold = Integer.MAX_VALUE;  
              return;  
                }  
               
                // 新建一個HashMap,將“舊HashMap”的全部元素添加到“新HashMap”中,  
                // 然后,將“新HashMap”賦值給“舊HashMap”。  
                Entry[] newTable = new Entry[newCapacity];  
                transfer(newTable);  
                table = newTable;  
                threshold = (int)(newCapacity * loadFactor);  
               } 

              很明顯,是新建了一個HashMap的底層數組,而后調用transfer方法,將就HashMap的全部元素添加到新的HashMap中(要重新計算元素在新的數組中的索引位置)。transfer方法的源碼如下:

              // 將HashMap中的全部元素都添加到newTable中  
               void transfer(Entry[] newTable) {  
                Entry[] src = table;  
                int newCapacity = newTable.length;  
                for (int j = 0; j < src.length; j++) {  
              Entry e = src[j];  
              if (e != null) {  
               src[j] = null;  
               do {  
                Entry next = e.next;  
                int i = indexFor(e.hash, newCapacity);  
                e.next = newTable[i];  
                newTable[i] = e;  
                e = next;  
               } while (e != null);  
              }  
                }  
               } 

              很明顯,擴容是一個相當耗時的操作,因為它需要重新計算這些元素在新的數組中的位置并進行復制處理。因此,我們在用HashMap的時,最好能提前預估下HashMap中元素的個數,這樣有助于提高HashMap的性能。

              7、注意containsKey方法和containsValue方法。前者直接可以通過key的哈希值將搜索范圍定位到指定索引對應的鏈表,而后者要對哈希數組的每個鏈表進行搜索。

              8、我們重點來分析下求hash值和索引值的方法,這兩個方法便是HashMap設計的最為核心的部分,二者結合能保證哈希表中的元素盡可能均勻地散列。

              計算哈希值的方法如下:

              static int hash(int h) {
                h ^= (h >>> 20) ^ (h >>> 12);
                return h ^ (h >>> 7) ^ (h >>> 4);
               }

              它只是一個數學公式,IDK這樣設計對hash值的計算,自然有它的好處,至于為什么這樣設計,我們這里不去追究,只要明白一點,用的位的操作使hash值的計算效率很高。

              由hash值找到對應索引的方法如下:

              static int indexFor(int h, int length) {
                return h & (length-1);
               }

              這個我們要重點說下,我們一般對哈希表的散列很自然地會想到用hash值對length取模(即除法散列法),Hashtable中也是這樣實現的,這種方法基本能保證元素在哈希表中散列的比較均勻,但取模會用到除法運算,效率很低,HashMap中則通過h&(length-1)的方法來代替取模,同樣實現了均勻的散列,但效率要高很多,這也是HashMap對Hashtable的一個改進。

              接下來,我們分析下為什么哈希表的容量一定要是2的整數次冪。首先,length為2的整數次冪的話,h&(length-1)就相當于對length取模,這樣便保證了散列的均勻,同時也提升了效率;其次,length為2的整數次冪的話,為偶數,這樣length-1為奇數,奇數的最后一位是1,這樣便保證了h&(length-1)的最后一位可能為0,也可能為1(這取決于h的值),即與后的結果可能為偶數,也可能為奇數,這樣便可以保證散列的均勻性,而如果length為奇數的話,很明顯length-1為偶數,它的最后一位是0,這樣h&(length-1)的最后一位肯定為0,即只能為偶數,這樣任何hash值都只會被散列到數組的偶數下標位置上,這便浪費了近一半的空間,因此,length取2的整數次冪,是為了使不同hash值發生碰撞的概率較小,這樣就能使元素在哈希表中均勻地散列。

              三、TreeMap源碼解讀

              1)TreeMap的特點

              2)TreeMap的源碼講解(jdk1.7)參考附屬文件的代碼,原文中有注解,下載

              3)TreeMap的總結

              四、WeakHashMap源碼解讀

              1)WeakHashMap的特點

              2)WeakHashMap的源碼講解(jdk1.7)參考附屬文件的代碼,原文中有注解,下載

              3)WeakHashMap的總結

              五、HashTable源碼解讀

              1)HashTable的特點

              Hashtable同樣是基于哈希表實現的,同樣每個元素是一個key-value對,其內部也是通過單鏈表解決沖突問題,容量不足(超過了閥值)時,同樣會自動增長。

              Hashtable也是JDK1.0引入的類,是線程安全的,能用于多線程環境中。

              Hashtable同樣實現了Serializable接口,它支持序列化,實現了Cloneable接口,能被克隆。

              2)HashTable的源碼講解(jdk1.7)參考附屬文件的代碼,原文中有注解,下載

              3)HashTable的總結

              針對Hashtable,我們同樣給出幾點比較重要的總結,但要結合與HashMap的比較來總結。

              1、二者的存儲結構和解決沖突的方法都是相同的。

              2、HashTable在不指定容量的情況下的默認容量為11,而HashMap為16,Hashtable不要求底層數組的容量一定要為2的整數次冪,而HashMap則要求一定為2的整數次冪。

              3、Hashtable中key和value都不允許為null,而HashMap中key和value都允許為null(key只能有一個為null,而value則可以有多個為null)。但是如果在Hashtable中有類似put(null,null)的操作,編譯同樣可以通過,因為key和value都是Object類型,但運行時會拋出NullPointerException異常,這是JDK的規范規定的。我們來看下ContainsKey方法和ContainsValue的源碼:

              // 判斷Hashtable是否包含“值(value)”  
               public synchronized boolean contains(Object value) {  
                //注意,Hashtable中的value不能是null,  
                // 若是null的話,拋出異常!  
                if (value == null) {  
              throw new NullPointerException();  
                }  
               
                // 從后向前遍歷table數組中的元素(Entry)  
                // 對于每個Entry(單向鏈表),逐個遍歷,判斷節點的值是否等于value  
                Entry tab[] = table;  
                for (int i = tab.length ; i-- > 0 ;) {  
              for (Entry e = tab[i] ; e != null ; e = e.next) {  
               if (e.value.equals(value)) {  
                return true;  
               }  
              }  
                }  
                return false;  
               }  
               
               public boolean containsValue(Object value) {  
                return contains(value);  
               }  
               
               // 判斷Hashtable是否包含key  
               public synchronized boolean containsKey(Object key) {  
                Entry tab[] = table;  
              		//計算hash值,直接用key的hashCode代替
                int hash = key.hashCode(); 
                // 計算在數組中的索引值 
                int index = (hash & 0x7FFFFFFF) % tab.length;  
                // 找到“key對應的Entry(鏈表)”,然后在鏈表中找出“哈希值”和“鍵值”與key都相等的元素  
                for (Entry e = tab[index] ; e != null ; e = e.next) {  
              if ((e.hash == hash) && e.key.equals(key)) {  
               return true;  
              }  
                }  
                return false;  
               } 

              很明顯,如果value為null,會直接拋出NullPointerException異常,但源碼中并沒有對key是否為null判斷,有點小不解!不過NullPointerException屬于RuntimeException異常,是可以由JVM自動拋出的,也許對key的值在JVM中有所限制吧。

              4、Hashtable擴容時,將容量變為原來的2倍加1,而HashMap擴容時,將容量變為原來的2倍。

              5、Hashtable計算hash值,直接用key的hashCode(),而HashMap重新計算了key的hash值,Hashtable在求hash值對應的位置索引時,用取模運算,而HashMap在求位置索引時,則用與運算,且這里一般先用hash&0x7FFFFFFF后,再對length取模,&0x7FFFFFFF的目的是為了將負的hash值轉化為正值,因為hash值有可能為負數,而&0x7FFFFFFF后,只有符號外改變,而后面的位都不變。

              點擊復制鏈接 與好友分享!回本站首頁
              上一篇:java開發學習之Jetty的工作原理講解
              下一篇:Java關于標識符與關鍵字的知識總結
              相關文章
              圖文推薦
              點擊排行

              關于我們 | 聯系我們 | 廣告服務 | 投資合作 | 版權申明 | 在線幫助 | 網站地圖 | 作品發布 | Vip技術培訓 | 舉報中心

              版權所有: 紅黑聯盟--致力于做實用的IT技術學習網站

              极速飞艇好假
              <dl id="opymh"></dl>

              <div id="opymh"></div>
                  <div id="opymh"><tr id="opymh"></tr></div>

                    <em id="opymh"><ins id="opymh"><mark id="opymh"></mark></ins></em><sup id="opymh"><menu id="opymh"></menu></sup>

                    <em id="opymh"></em>

                    <em id="opymh"><ol id="opymh"></ol></em>

                          <dl id="opymh"></dl>

                          <div id="opymh"></div>
                              <div id="opymh"><tr id="opymh"></tr></div>

                                <em id="opymh"><ins id="opymh"><mark id="opymh"></mark></ins></em><sup id="opymh"><menu id="opymh"></menu></sup>

                                <em id="opymh"></em>

                                <em id="opymh"><ol id="opymh"></ol></em>