欧美性猛交XXXX免费看蜜桃,成人网18免费韩国,亚洲国产成人精品区综合,欧美日韩一区二区三区高清不卡,亚洲综合一区二区精品久久

java.util 中的集合類(lèi)包含 Java 中某些最常用的類(lèi)。 最常用的集合類(lèi)是 List 和 Map。 List 的具體實(shí)現包括 ArrayList 和 Vector，它們是可變大小的列表，比較適合構建、存儲和操作任何類(lèi)型對象的元素列表。 List 適用于按數值索引訪(fǎng)問(wèn)元素的情形。

Map 提供了一個(gè)更通用的元素存儲方法。 Map 集合類(lèi)用于存儲元素對（稱(chēng)作“鍵”和“值”），其中每個(gè)鍵映射到一個(gè)值。 從概念上而言，您可以將 List 看作是具有數值鍵的 Map。 而實(shí)際上，除了 List 和 Map 都在定義 java.util 中外，兩者并沒(méi)有直接的聯(lián)系。本文將著(zhù)重介紹核心 Java 發(fā)行套件中附帶的 Map，同時(shí)還將介紹如何采用或實(shí)現更適用于您應用程序特定數據的專(zhuān)用 Map。

了解 Map 接口和方法

Java 核心類(lèi)中有很多預定義的 Map 類(lèi)。 在介紹具體實(shí)現之前，我們先介紹一下 Map 接口本身，以便了解所有實(shí)現的共同點(diǎn)。 Map 接口定義了四種類(lèi)型的方法，每個(gè) Map 都包含這些方法。 下面，我們從兩個(gè)普通的方法（表 1）開(kāi)始對這些方法加以介紹。

表 1： 覆蓋的方法。 我們將這 Object 的這兩個(gè)方法覆蓋，以正確比較 Map 對象的等價(jià)性。

Map 構建

Map 定義了幾個(gè)用于插入和刪除元素的變換方法（表 2）。

表 2： Map 更新方法： 可以更改 Map 內容。

盡管您可能注意到，縱然假設忽略構建一個(gè)需要傳遞給 putAll() 的 Map 的開(kāi)銷(xiāo)，使用 putAll() 通常也并不比使用大量的 put() 調用更有效率，但 putAll() 的存在一點(diǎn)也不稀奇。 這是因為，putAll() 除了迭代 put() 所執行的將每個(gè)鍵值對添加到 Map 的算法以外，還需要迭代所傳遞的 Map 的元素。 但應注意，putAll() 在添加所有元素之前可以正確調整 Map 的大小，因此如果您未親自調整 Map 的大?。ㄎ覀儗Υ诉M(jìn)行簡(jiǎn)單介紹），則 putAll() 可能比預期的更有效。

查看 Map

迭代 Map 中的元素不存在直接了當的方法。 如果要查詢(xún)某個(gè) Map 以了解其哪些元素滿(mǎn)足特定查詢(xún)，或如果要迭代其所有元素（無(wú)論原因如何），則您首先需要獲取該 Map 的“視圖”。 有三種可能的視圖（參見(jiàn)表 3）

• 所有鍵值對 — 參見(jiàn) entrySet()
• 所有鍵 — 參見(jiàn) keySet()
• 所有值 — 參見(jiàn) values()

前兩個(gè)視圖均返回 Set 對象，第三個(gè)視圖返回 Collection 對象。 就這兩種情況而言，問(wèn)題到這里并沒(méi)有結束，這是因為您無(wú)法直接迭代 Collection 對象或 Set 對象。要進(jìn)行迭代，您必須獲得一個(gè) Iterator 對象。 因此，要迭代 Map 的元素，必須進(jìn)行比較煩瑣的編碼

Iterator keyValuePairs = aMap.entrySet().iterator();Iterator keys = aMap.keySet().iterator();Iterator values = aMap.values().iterator();

值得注意的是，這些對象（Set、Collection 和 Iterator）實(shí)際上是基礎 Map 的視圖，而不是包含所有元素的副本。 這使它們的使用效率很高。 另一方面，Collection 或 Set 對象的 toArray() 方法卻創(chuàng )建包含 Map 所有元素的數組對象，因此除了確實(shí)需要使用數組中元素的情形外，其效率并不高。

我運行了一個(gè)小測試（隨附文件中的 Test1），該測試使用了 HashMap，并使用以下兩種方法對迭代 Map 元素的開(kāi)銷(xiāo)進(jìn)行了比較：

int mapsize = aMap.size();Iterator keyValuePairs1 = aMap.entrySet().iterator();for (int i = 0; i < mapsize; i++){  Map.Entry entry = (Map.Entry) keyValuePairs1.next();  Object key = entry.getKey();  Object value = entry.getValue();  ...}Object[] keyValuePairs2 = aMap.entrySet().toArray();for (int i = 0; i < rem; i++) {{  Map.Entry entry = (Map.Entry) keyValuePairs2[i];  Object key = entry.getKey();
Profilers in Oracle JDeveloper
Oracle JDeveloper 包含一個(gè)嵌入的監測器，它測量?jì)却婧蛨绦袝r(shí)間，使您能夠快速識別代碼中的瓶頸。 我曾使用 Jdeveloper 的執行監測器監測 HashMap 的 containsKey() 和 containsValue() 方法，并很快發(fā)現 containsKey() 方法的速度比 containsValue() 方法慢很多（實(shí)際上要慢幾個(gè)數量級?。?。 （參見(jiàn)圖 1 和圖 2，以及隨附文件中的 Test2 類(lèi)）。 
  Object value = entry.getValue();  ...}

表 3： 返回視圖的 Map 方法： 使用這些方法返回的對象，您可以遍歷 Map 的元素，還可以刪除 Map 中的元素。

訪(fǎng)問(wèn)元素

表 4 中列出了 Map 訪(fǎng)問(wèn)方法。Map 通常適合按鍵（而非按值）進(jìn)行訪(fǎng)問(wèn)。 Map 定義中沒(méi)有規定這肯定是真的，但通常您可以期望這是真的。 例如，您可以期望 containsKey() 方法與 get() 方法一樣快。 另一方面，containsValue() 方法很可能需要掃描 Map 中的值，因此它的速度可能比較慢。

表 4： Map 訪(fǎng)問(wèn)和測試方法： 這些方法檢索有關(guān) Map 內容的信息但不更改 Map 內容。

對使用 containsKey() 和 containsValue() 遍歷 HashMap 中所有元素所需時(shí)間的測試表明，containsValue() 所需的時(shí)間要長(cháng)很多。 實(shí)際上要長(cháng)幾個(gè)數量級！ （參見(jiàn)圖 1 和圖 2，以及隨附文件中的 Test2）。 因此，如果 containsValue() 是應用程序中的性能問(wèn)題，它將很快顯現出來(lái)，并可以通過(guò)監測您的應用程序輕松地將其識別。 這種情況下，我相信您能夠想出一個(gè)有效的替換方法來(lái)實(shí)現 containsValue() 提供的等效功能。 但如果想不出辦法，則一個(gè)可行的解決方案是再創(chuàng )建一個(gè) Map，并將第一個(gè) Map 的所有值作為鍵。 這樣，第一個(gè) Map 上的 containsValue() 將成為第二個(gè) Map 上更有效的 containsKey()。

圖 1： 使用 JDeveloper 創(chuàng )建并運行 Map 測試類(lèi)

圖 2： 在 JDeveloper 中使用執行監測器進(jìn)行的性能監測查出應用程序中的瓶頸

核心 Map

Java 自帶了各種 Map 類(lèi)。 這些 Map 類(lèi)可歸為三種類(lèi)型：

1. 通用 Map，用于在應用程序中管理映射，通常在 java.util 程序包中實(shí)現
   • HashMap
   • Hashtable
   • Properties
   • LinkedHashMap
   • IdentityHashMap
   • TreeMap
   • WeakHashMap
   • ConcurrentHashMap
2. 專(zhuān)用 Map，您通常不必親自創(chuàng )建此類(lèi) Map，而是通過(guò)某些其他類(lèi)對其進(jìn)行訪(fǎng)問(wèn)
   • java.util.jar.Attributes
   • javax.print.attribute.standard.PrinterStateReasons
   • java.security.Provider
   • java.awt.RenderingHints
   • javax.swing.UIDefaults
3. 一個(gè)用于幫助實(shí)現您自己的 Map 類(lèi)的抽象類(lèi)
   • AbstractMap

內部哈希： 哈希映射技術(shù)

幾乎所有通用 Map 都使用哈希映射。 這是一種將元素映射到數組的非常簡(jiǎn)單的機制，您應了解哈希映射的工作原理，以便充分利用 Map。

哈希映射結構由一個(gè)存儲元素的內部數組組成。 由于內部采用數組存儲，因此必然存在一個(gè)用于確定任意鍵訪(fǎng)問(wèn)數組的索引機制。 實(shí)際上，該機制需要提供一個(gè)小于數組大小的整數索引值。 該機制稱(chēng)作哈希函數。 在 Java 基于哈希的 Map 中，哈希函數將對象轉換為一個(gè)適合內部數組的整數。 您不必為尋找一個(gè)易于使用的哈希函數而大傷腦筋： 每個(gè)對象都包含一個(gè)返回整數值的 hashCode() 方法。 要將該值映射到數組，只需將其轉換為一個(gè)正值，然后在將該值除以數組大小后取余數即可。 以下是一個(gè)簡(jiǎn)單的、適用于任何對象的 Java 哈希函數

int hashvalue = Maths.abs(key.hashCode()) % table.length;

（% 二進(jìn)制運算符（稱(chēng)作模）將左側的值除以右側的值，然后返回整數形式的余數。）

實(shí)際上，在 1.4 版發(fā)布之前，這就是各種基于哈希的 Map 類(lèi)所使用的哈希函數。 但如果您查看一下代碼，您將看到

int hashvalue = (key.hashCode() & 0x7FFFFFFF) % table.length;

它實(shí)際上是使用更快機制獲取正值的同一函數。 在 1.4 版中，HashMap 類(lèi)實(shí)現使用一個(gè)不同且更復雜的哈希函數，該函數基于 Doug Lea 的 util.concurrent 程序包（稍后我將更詳細地再次介紹 Doug Lea 的類(lèi)）。

圖 3： 哈希工作原理

該圖介紹了哈希映射的基本原理，但我們還沒(méi)有對其進(jìn)行詳細介紹。 我們的哈希函數將任意對象映射到一個(gè)數組位置，但如果兩個(gè)不同的鍵映射到相同的位置，情況將會(huì )如何？ 這是一種必然發(fā)生的情況。 在哈希映射的術(shù)語(yǔ)中，這稱(chēng)作沖突。 Map 處理這些沖突的方法是在索引位置處插入一個(gè)鏈接列表，并簡(jiǎn)單地將元素添加到此鏈接列表。 因此，一個(gè)基于哈希的 Map 的基本 put() 方法可能如下所示

public Object put(Object key, Object value) {  //我們的內部數組是一個(gè) Entry 對象數組  //Entry[] table;  //獲取哈希碼，并映射到一個(gè)索引  int hash = key.hashCode();  int index = (hash & 0x7FFFFFFF) % table.length;  //循環(huán)遍歷位于 table[index] 處的鏈接列表，以查明  //我們是否擁有此鍵項 — 如果擁有，則覆蓋它  for (Entry e = table[index] ; e != null ; e = e.next) {    //必須檢查鍵是否相等，原因是不同的鍵對象    //可能擁有相同的哈希    if ((e.hash == hash) && e.key.equals(key)) {      //這是相同鍵，覆蓋該值      //并從該方法返回 old 值      Object old = e.value;      e.value = value;      return old;    }  }  //仍然在此處，因此它是一個(gè)新鍵，只需添加一個(gè)新 Entry  //Entry 對象包含 key 對象、 value 對象、一個(gè)整型的 hash、  //和一個(gè)指向列表中的下一個(gè) Entry 的 next Entry  //創(chuàng  )建一個(gè)指向上一個(gè)列表開(kāi)頭的新 Entry，  //并將此新 Entry 插入表中  Entry e = new Entry(hash, key, value, table[index]);  table[index] = e;  return null;}

如果看一下各種基于哈希的 Map 的源代碼，您將發(fā)現這基本上就是它們的工作原理。 此外，還有一些需要進(jìn)一步考慮的事項，如處理空鍵和值以及調整內部數組。 此處定義的 put() 方法還包含相應 get() 的算法，這是因為插入包括搜索映射索引處的項以查明該鍵是否已經(jīng)存在。 （即 get() 方法與 put() 方法具有相同的算法，但 get() 不包含插入和覆蓋代碼。） 使用鏈接列表并不是解決沖突的唯一方法，某些哈希映射使用另一種“開(kāi)放式尋址”方案，本文對其不予介紹。

優(yōu)化 Hasmap

如果哈希映射的內部數組只包含一個(gè)元素，則所有項將映射到此數組位置，從而構成一個(gè)較長(cháng)的鏈接列表。 由于我們的更新和訪(fǎng)問(wèn)使用了對鏈接列表的線(xiàn)性搜索，而這要比 Map 中的每個(gè)數組索引只包含一個(gè)對象的情形要慢得多，因此這樣做的效率很低。 訪(fǎng)問(wèn)或更新鏈接列表的時(shí)間與列表的大小線(xiàn)性相關(guān)，而使用哈希函數訪(fǎng)問(wèn)或更新數組中的單個(gè)元素則與數組大小無(wú)關(guān) — 就漸進(jìn)性質(zhì)（Big-O 表示法）而言，前者為 O(n)，而后者為 O(1)。 因此，使用一個(gè)較大的數組而不是讓太多的項聚集在太少的數組位置中是有意義的。

調整 Map 實(shí)現的大小

在哈希術(shù)語(yǔ)中，內部數組中的每個(gè)位置稱(chēng)作“存儲桶”(bucket)，而可用的存儲桶數（即內部數組的大?。┓Q(chēng)作容量 (capacity)。 為使 Map 對象有效地處理任意數目的項，Map 實(shí)現可以調整自身的大小。 但調整大小的開(kāi)銷(xiāo)很大。 調整大小需要將所有元素重新插入到新數組中，這是因為不同的數組大小意味著(zhù)對象現在映射到不同的索引值。 先前沖突的鍵可能不再沖突，而先前不沖突的其他鍵現在可能沖突。 這顯然表明，如果將 Map 調整得足夠大，則可以減少甚至不再需要重新調整大小，這很有可能顯著(zhù)提高速度。

使用 1.4.2 JVM 運行一個(gè)簡(jiǎn)單的測試，即用大量的項（數目超過(guò)一百萬(wàn)）填充 HashMap。 表 5 顯示了結果，并將所有時(shí)間標準化為已預先設置大小的服務(wù)器模式（關(guān)聯(lián)文件中的 Test3）。 對于已預先設置大小的 JVM，客戶(hù)端和服務(wù)器模式 JVM 運行時(shí)間幾乎相同（在放棄 JIT 編譯階段后）。 但使用 Map 的默認大小將引發(fā)多次調整大小操作，開(kāi)銷(xiāo)很大，在服務(wù)器模式下要多用 50% 的時(shí)間，而在客戶(hù)端模式下幾乎要多用兩倍的時(shí)間！

表 5： 填充已預先設置大小的 HashMap 與填充默認大小的 HashMap 所需時(shí)間的比較

使用負載因子

為確定何時(shí)調整大小，而不是對每個(gè)存儲桶中的鏈接列表的深度進(jìn)行記數，基于哈希的 Map 使用一個(gè)額外參數并粗略計算存儲桶的密度。 Map 在調整大小之前，使用名為“負載因子”的參數指示 Map 將承擔的“負載”量，即它的負載程度。 負載因子、項數（Map 大?。┡c容量之間的關(guān)系簡(jiǎn)單明了：

• 如果（負載因子）x（容量）>（Map 大?。?，則調整 Map 大小

例如，如果默認負載因子為 0.75，默認容量為 11，則 11 x 0.75 = 8.25，該值向下取整為 8 個(gè)元素。 因此，如果將第 8 個(gè)項添加到此 Map，則該 Map 將自身的大小調整為一個(gè)更大的值。 相反，要計算避免調整大小所需的初始容量，用將要添加的項數除以負載因子，并向上取整，例如，

• 對于負載因子為 0.75 的 100 個(gè)項，應將容量設置為 100/0.75 = 133.33，并將結果向上取整為 134（或取整為 135 以使用奇數）

奇數個(gè)存儲桶使 map 能夠通過(guò)減少沖突數來(lái)提高執行效率。 雖然我所做的測試（關(guān)聯(lián)文件中的Test4）并未表明質(zhì)數可以始終獲得更好的效率，但理想情形是容量取質(zhì)數。 1.4 版后的某些 Map（如 HashMap 和 LinkedHashMap，而非 Hashtable 或 IdentityHashMap）使用需要 2 的冪容量的哈希函數，但下一個(gè)最高 2 的冪容量由這些 Map 計算，因此您不必親自計算。

負載因子本身是空間和時(shí)間之間的調整折衷。 較小的負載因子將占用更多的空間，但將降低沖突的可能性，從而將加快訪(fǎng)問(wèn)和更新的速度。 使用大于 0.75 的負載因子可能是不明智的，而使用大于 1.0 的負載因子肯定是不明知的，這是因為這必定會(huì )引發(fā)一次沖突。 使用小于 0.50 的負載因子好處并不大，但只要您有效地調整 Map 的大小，應不會(huì )對小負載因子造成性能開(kāi)銷(xiāo)，而只會(huì )造成內存開(kāi)銷(xiāo)。 但較小的負載因子將意味著(zhù)如果您未預先調整 Map 的大小，則導致更頻繁的調整大小，從而降低性能，因此在調整負載因子時(shí)一定要注意這個(gè)問(wèn)題。

選擇適當的 Map

應使用哪種 Map？ 它是否需要同步？ 要獲得應用程序的最佳性能，這可能是所面臨的兩個(gè)最重要的問(wèn)題。 當使用通用 Map 時(shí)，調整 Map 大小和選擇負載因子涵蓋了 Map 調整選項。

以下是一個(gè)用于獲得最佳 Map 性能的簡(jiǎn)單方法

1. 將您的所有 Map 變量聲明為 Map，而不是任何具體實(shí)現，即不要聲明為 HashMap 或 Hashtable，或任何其他 Map 類(lèi)實(shí)現。

   Map criticalMap = new HashMap(); //好HashMap criticalMap = new HashMap(); //差

   這使您能夠只更改一行代碼即可非常輕松地替換任何特定的 Map 實(shí)例。

2. 下載 Doug Lea 的 util.concurrent 程序包 (http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html)。 將 ConcurrentHashMap 用作默認 Map。 當移植到 1.5 版時(shí)，將 java.util.concurrent.ConcurrentHashMap 用作您的默認 Map。 不要將 ConcurrentHashMap 包裝在同步的包裝器中，即使它將用于多個(gè)線(xiàn)程。 使用默認大小和負載因子。
3. 監測您的應用程序。 如果發(fā)現某個(gè) Map 造成瓶頸，則分析造成瓶頸的原因，并部分或全部更改該 Map 的以下內容： Map 類(lèi)；Map 大??；負載因子；關(guān)鍵對象 equals() 方法實(shí)現。 專(zhuān)用的 Map 的基本上都需要特殊用途的定制 Map 實(shí)現，否則通用 Map 將實(shí)現您所需的性能目標。

Map 選擇

也許您曾期望更復雜的考量，而這實(shí)際上是否顯得太容易？ 好的，讓我們慢慢來(lái)。 首先，您應使用哪種 Map？ 答案很簡(jiǎn)單： 不要為您的設計選擇任何特定的 Map，除非實(shí)際的設計需要指定一個(gè)特殊類(lèi)型的 Map。 設計時(shí)通常不需要選擇具體的 Map 實(shí)現。 您可能知道自己需要一個(gè) Map，但不知道使用哪種。 而這恰恰就是使用 Map 接口的意義所在。 直到需要時(shí)再選擇 Map 實(shí)現 — 如果隨處使用“Map”聲明的變量，則更改應用程序中任何特殊 Map 的 Map 實(shí)現只需要更改一行，這是一種開(kāi)銷(xiāo)很少的調整選擇。 是否要使用默認的 Map 實(shí)現？ 我很快將談到這個(gè)問(wèn)題。

同步 Map

同步與否有何差別？ （對于同步，您既可以使用同步的 Map，也可以使用 Collections.synchronizedMap() 將未同步的 Map 轉換為同步的 Map。 后者使用“同步的包裝器”）這是一個(gè)異常復雜的選擇，完全取決于您如何根據多線(xiàn)程并發(fā)訪(fǎng)問(wèn)和更新使用 Map，同時(shí)還需要進(jìn)行維護方面的考慮。 例如，如果您開(kāi)始時(shí)未并發(fā)更新特定 Map，但它后來(lái)更改為并發(fā)更新，情況將如何？ 在這種情況下，很容易在開(kāi)始時(shí)使用一個(gè)未同步的 Map，并在后來(lái)向應用程序中添加并發(fā)更新線(xiàn)程時(shí)忘記將此未同步的 Map 更改為同步的 Map。 這將使您的應用程序容易崩潰（一種要確定和跟蹤的最糟糕的錯誤）。 但如果默認為同步，則將因隨之而來(lái)的可怕性能而序列化執行多線(xiàn)程應用程序。 看起來(lái)，我們需要某種決策樹(shù)來(lái)幫助我們正確選擇。

Doug Lea 是紐約州立大學(xué)奧斯威戈分校計算機科學(xué)系的教授。 他創(chuàng )建了一組公共領(lǐng)域的程序包（統稱(chēng) util.concurrent），該程序包包含許多可以簡(jiǎn)化高性能并行編程的實(shí)用程序類(lèi)。 這些類(lèi)中包含兩個(gè) Map，即 ConcurrentReaderHashMap 和 ConcurrentHashMap。 這些 Map 實(shí)現是線(xiàn)程安全的，并且不需要對并發(fā)訪(fǎng)問(wèn)或更新進(jìn)行同步，同時(shí)還適用于大多數需要 Map 的情況。 它們還遠比同步的 Map（如 Hashtable）或使用同步的包裝器更具伸縮性，并且與 HashMap 相比，它們對性能的破壞很小。 util.concurrent 程序包構成了 JSR166 的基礎；JSR166 已經(jīng)開(kāi)發(fā)了一個(gè)包含在 Java 1.5 版中的并發(fā)實(shí)用程序，而 Java 1.5 版將把這些 Map 包含在一個(gè)新的 java.util.concurrent 程序包中。