java util包中map应用

自：http://linux.net527.cn/Linuxwendang/kaifahuanjing/java/30691.html

开拓职员：J2EE JavaMap聚拢类简介 作者：JackShirazi 了解最常用的聚拢范例之一Map的根本知识以及怎样针对您操纵措施特有的数据优化Map。 java.util中的聚拢类包孕Java中某些最常用的类。最常用的聚拢类是List和Map。List的具体实现包孕ArrayList和Vector，

开拓职员：J2EE  
Java Map 聚拢类简介
作者：Jack Shirazi

了解 最常用的聚拢范例之一 Map 的根本 知识以及怎样针对您操纵措施特有的数据优化 Map。

java.util 中的聚拢类包孕  Java 中某些最常用的类。 最常用的聚拢类是 List 和 Map。 List 的具体 实现包孕 ArrayList 和 Vector，它们是可变巨细的列表，比拟 适宜 构建、存储和操纵任何范例器材的元素列表。 List 适用于按数值索引拜访元素的环境。

Map 供给 了一个更通用的元素存储行动 。 Map 聚拢类用于存储元素对（称作“键”和“值”），此中每个键映射到一个值。 从观念上而言，您可以将 List 看作是具有数值键的 Map。 而实际 上，除了 List 和 Map 都在界说  java.util 中外，两者并没有直接的联系。本文将侧重先容核心  Java 刊行套件中附带的 Map，同时还将先容怎样采用 或实现更适用于您操纵措施特定命据的专用 Map。

了解  Map 接口和行动 

Java 核心 类中有很多 预界说的 Map 类。 在先容具体 实现之前，我们先先容一下 Map 接口本身 ，以便了解 全部实现的共同 点。 Map 接口界说了四种范例的行动 ，每个 Map 都包孕这些行动 。 下面，我们从两个平凡的行动 （）起头对这些行动 加以先容。

表 1： 覆盖的行动 。 我们将这 Object 的这两个行动 覆盖，以精确 比拟  Map 器材的等价性。  

equals(Object o) 比较指定对象与此 Map 的等价性

hashCode() 返回此 Map 的哈希码

Map 构建

Map 界说了几个用于插入和删除元素的调动行动 （）。

表 2： Map 更新行动 ： 可以变动  Map 内容。  

clear() 从 Map 中删除所有映射
remove(Object key) 从 Map 中删除键和关联的值
put(Object key, Object value) 将指定值与指定键相关联
clear() 从 Map 中删除所有映射
putAll(Map t) 将指定 Map 中的所有映射复制到此 map

尽量您也许留意到，纵然假设漠视 构建一个必要 转达 给 putAll() 的 Map 的开销，应用  putAll() 通常也并不比应用大宗的 put() 调用更有遵从 ，但 putAll() 的存在一点也不特别。 这是由于，putAll() 除了迭代 put() 所推行 的将每个键值对添加到 Map 的算法以外，还必要 迭代所转达 的 Map 的元素。 但应留意，putAll() 在添加全部元素之前可以精确 调度  Map 的巨细，因此假如您未亲身调度  Map 的巨细（我们将对此举办大略 先容），则 putAll() 也许比预期的更有效 。

查察  Map

迭代 Map 中的元素不存在直接了当的行动 。 假如要查询某个 Map 以了解 其哪些元素满意特定查询，或假如要迭代其全部元素（无论缘故起因 怎样），则您起首必要 获取该 Map 的“视图”。 有三种也许的视图（拜见）

• 全部键值对 — 拜见  entrySet() 
• 全部键 — 拜见  keySet() 
• 全部

值 — 拜见  values() 


前两个视图均返回 Set 器材，第三个视图返回 Collection 器材。 就这两种情况而言，题目到这里并没有收场，这是由于您无法直接迭代 Collection 器材或 Set 器材。要举办迭代，您必需得到一个 Iterator 器材。 因此，要迭代 Map 的元素，必需举办比拟 啰嗦的编码



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

值得留意的是，这些器材（Set、Collection 和 Iterator）实际 上是根本  Map 的视图，而不是包孕全部元素的副本。 这使它们的应用遵从 很高。 另一方面，Collection 或 Set 器材的 toArray() 行动 却创建 包孕  Map 全部元素的数组器材，因此除了确凿必要 应用数组中元素的环境外，其遵从 并不高。

我运行了一个小测试（随附文件中的 ），该测试应用了 HashMap，并应用以下两种行动 对迭代 Map 元素的开销举办了比拟 ：



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();
  Object value = entry.getValue();
  ...
}
此测试应用了两种丈量行动 ： 一种是丈量迭代元素的工夫，另一种丈量应用  toArray 调用创建 数组的其他开销。
第一种行动 （漠视 创建 数组所需的工夫）表明，应用已从 toArray 调用中创建 的数组迭代元素的速率要比应用  Iterator 的速率约莫快 30%-60%。 但假如将应用  toArray 行动 创建 数组的开销包孕在内，则应用  Iterator 实际 上要快 10%-20%。 因此，假如由于某种缘故起因 要创建 一个聚拢元素的数组而非迭代这些元素，则应应用该数组迭代元素。 但假如您不必要 此中央数组，则不要创建 它，而是应用  Iterator 迭代元素。  


表 3： 返回视图的 Map 行动 ： 应用这些行动 返回的器材，您可以遍历 Map 的元素，还可以删除 Map 中的元素。  

entrySet() 返回 Map 中所包含映射的 Set 视图。 Set 中的每个元素都是一个 Map.Entry 对象，可以使用 getKey() 和 getValue() 方法（还有一个 setValue() 方法）访问后者的键元素和值元素

keySet() 返回 Map 中所包含键的 Set 视图。 删除 Set 中的元素还将删除 Map 中相应的映射（键和值） }

values() 返回 map 中所包含值的 Collection 视图。 删除 Collection 中的元素还将删除 Map 中相应的映射（键和值）

拜访元素

表 4 中列出了 Map 拜访行动 。Map 通常适宜 按键（而非按值）举办拜访。 Map 界说中没有规定 这确定是真的，但通常您可以祈望这是真的。 譬喻，您可以祈望 containsKey() 行动 与 get() 行动 一样快。 另一方面，containsValue() 行动 很也许必要 扫描 Map 中的值，因此它的速率也许比拟 慢。

表 4： Map 拜访和测试行动 ： 这些行动 检索有关 Map 内容的信息但不变动  Map 内容。  

get(Object key) 返回与指定键关联的值

containsKey(Object key) 如果 Map 包含指定键的映射，则返回 true

containsValue(Object value) 如果此 Map 将一个或多个键映射到指定值，则返回true

isEmpty() 如果 Map 不包含键-值映射，则返回 true

size() 返回 Map 中的键-值映射的数目

对应用  containsKey() 和 containsValue() 遍历 HashMap 中全部元素所需工夫的测试表明，containsValue() 所需的工夫要长很多 。 实际 上要长几个数量 级！ （拜见  和，以及随附文件中的 ）。 因此，假如  containsValue() 是操纵措施中的性能题目，它将很快涌现出来，并可以通过监测您的操纵措施轻松地将其识别。 这种情况下，我信赖您可以或许想出一个有效 的变更 行动 来实现 containsValue() 供给 的等效功能。 但假如想不出办法，则一个可行的办理方案 是再创建 一个 Map，并将第一个 Map 的全部值作为键。 如许，第一个 Map 上的 containsValue() 将成为第二个 Map 上更有效 的 containsKey()。 

核心  Map

Java 自带了种种  Map 类。 这些 Map 类可归为三种范例：
1.通用 Map，用于在操纵措施中管理 映射，通常在 java.util 措施包中实现  
HashMap 
Hashtable 
Properties 
LinkedHashMap 
IdentityHashMap 
TreeMap 
WeakHashMap 
ConcurrentHashMap 
2.专用 Map，您通常不必亲身创建 词攀? ? Map，而是通过某些其他类对其举办拜访  
java.util.jar.Attributes 
javax.print.attribute.standard.PrinterStateReasons 
java.security.Provider 
java.awt.RenderingHints 
javax.swing.UIDefaults 
3.一个用于赞助 实现您本身的 Map 类的抽象类  
AbstractMap 


内部哈希： 哈希映射能力 

险些全部通用 Map 都应用哈希映射。 这是一种将元素映射到数组的非常大略 的机制，您应了解 哈希映射的事变 原理，以便充沛操作 Map。

哈希映射结构由一个存储元素的内部数组构成。 由于内部采用 数组存储，因此一定存在一个用于断定恣意键拜访数组的索引机制。 实际 上，该机制必要 供给 一个小于数组巨细的整数索引值。 该机制称作哈希函数。 在 Java 基于哈希的 Map 中，哈希函数将器材转换为一个适宜 内部数组的整数。 您不必为探求一个易于应用的哈希函数而大伤脑筋： 每个器材都包孕一个返回整数值的 hashCode() 行动 。 要将该值映射到数组，只需将其转换为一个正值，然后在将该值除以数组巨细后取余数即可。 以下是一个大略 的、适用于任何器材的 Java 哈希函数



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

（% 二进制运算符（称作模）将左侧的值除以右侧的值，然后返回整数形式的余数。）

实际 上，在 1.4 版公布 之前，这就是种种基于哈希的 Map 类所应用的哈希函数。 但假如您查察 一下代码，您将看到



int hashvalue = (key.hashCode() & 0x7FFFFFFF) % table.length;
它实际 上是应用更快机制获取正值的同一函数。 在 1.4 版中，HashMap 类实现应用一个差别 且更繁杂的哈希函数，该函数基于 Doug Lea 的 util.concurrent 措施包（稍后我将更具体地再次先容  Doug Lea 的类）。




该图先容了哈希映射的根本 原理，但我们还没有对其举办具体先容。 我们的哈希函数将恣意器材映射到一个数组职位 ，但假如两个差别 的键映射到相同 的职位 ，情况将会怎样？ 这是一种一定发生的情况。 在哈希映射的术语中，这称作斗嘴。 Map 处理赏罚 这些斗嘴的行动 是在索引职位 处插入一个链接列表，并大略 地将元素添加到此链接列表。 因此，一个基于哈希的 Map 的根本  put() 行动 也许如下所示



public Object put(Object key, Object value) {  //我们的内部数组是一个 Entry 器材
数组  //Entry[] table;  //获取哈希码，并映射到一个索引  int hash = key.hashCode();  int index = (hash & 0x7FFFFFFF) % table.length;  //循环遍历位于 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;    }  }  //如故在此处，因此它是一个新键，只需添加一个新 Entry  //Entry 器材
包孕
key 器材
、 value 器材
、一个整型的 hash、  //和一个指向列表中的下一个 Entry 的 next Entry  //创建


一个指向上一个列表开头的新 Entry，  //并将此新 Entry 插入表中  Entry e = new Entry(hash, key, value, table[index]);  table[index] = e;  return null;}

假如看一下种种基于哈希的 Map 的源代码，您将创造这根本 上就是它们的事变 原理。 另外，尚有 一些必要 进一步思量 的事项，如处理赏罚 空键和值以及调度 内部数组。 此处界说的 put() 行动 还包孕相应 get() 的算法，这是由于插入包孕搜刮映射索引处的项以查明该键是否已经存在。 （即 get() 行动 与 put() 行动 具有相同 的算法，但 get() 不包孕插入和覆盖代码。） 应用链接列表并不是办理斗嘴的唯一行动 ，某些哈希映射应用另一种“开放式寻址”方案 ，本文对其不予先容。

优化 Hasmap

假如哈希映射的内部数组只包孕一个元素，则全部项将映射到此数组职位 ，从而构成 一个较长的链接列表。 由于我们的更新和拜访应用了对链接列表的线性搜刮，而这要比 Map 中的每个数组索引只包孕一个器材的环境要慢得多，因此如许做的遵从 很低。 拜访或更新链接列表的工夫与列表的巨细线性干系 ，而应用哈希函数拜访或更新数组中的单个元素则与数组巨细无关 — 就渐进性子（Big-O 表示法）而言，前者为 O(n)，尔后者为 O(1)。 因此，应用一个较大的数组而不是让太多的项凑集在太少的数组职位 中是故意义的。

调度  Map 实现的巨细 

在哈希术语中，内部数组中的每个职位 称作“存储桶”(bucket)，而可用的存储桶数（即内部数组的巨细）称作容量 (capacity)。 为使 Map 器材有效 地处理赏罚 恣意数方针项，Map 实现可以调度 自身的巨细。 但调度 巨细的开销很大。 调度 巨细必要 将全部元素重新插入到新数组中，这是由于差别 的数组巨细意味着器材如今映射到差别 的索引值。 先前斗嘴的键也许不再斗嘴，而先前不斗嘴的其他键如今也许斗嘴。 这显然表明，假如将 Map 调度 得充足大，则可以镌汰 乃至不再必要 重新调度 巨细，这很有也许明明前进速率。

应用  1.4.2 JVM 运行一个大略 的测试，即用大宗的项（数量高出 一百万）添补  HashMap。 表 5 表现告终果，并将全部工夫标准 化为已预先设置巨细的做事器模式（关联文件中的 ）。 对付已预先设置巨细的 JVM，客户端和做事器模式 JVM 运行工夫险些相同 （在放弃  JIT 编译阶段后）。 但应用  Map 的默认巨细将引发多次调度 巨细操纵，开销很大，在做事器模式下要多用 50% 的工夫，而在客户端模式下险些要多用两倍的工夫！

表 5： 添补已预先设置巨细的 HashMap 与添补默认巨细的 HashMap 所需工夫的比拟   



应用负载因子

为断定何时调度 巨细，而不是对每个存储桶中的链接列表的深度举办记数，基于哈希的 Map 应用一个稀奇 参数并大致打定存储桶的密度。 Map 在调度 巨细之前，应用名为“负载因子”的参数挑拨  Map 将包袱 的“负载”量，即它的负载程度 。 负载因子、项数（Map 巨细）与容量之间的相干大略 明确：



假如（负载因子）x（容量）>（Map 巨细），则调度  Map 巨细  


譬喻，假如默认负载因子为 0.75，默认容量为 11，则 11 x 0.75 = 8.25，该值向下取整为 8 个元素。 因此，假如将第 8 个项添加到此 Map，则该 Map 将自身的巨细调度 为一个更大的值。 相反，要打定停止调度 巨细所需的初始容量，用将要添加的项数除以负载因子，并向上取整，譬喻，



对付负载因子为 0.75 的 100 个项，应将容量设置为 100/0.75 = 133.33，并将结果向上取整为 134（或取整为 135 以应用奇数） 


奇数个存储桶使 map 可以或许通过镌汰 斗嘴数来前进推行 遵从 。 固然我所做的测试（关联文件中的）并未表明质数可以始终得到更好的遵从 ，但理想环境是容量取质数。 1.4 版后的某些 Map（如 HashMap 和 LinkedHashMap，而非 Hashtable 或 IdentityHashMap）应用必要  2 的幂容量的哈希函数，但下一个最高 2 的幂容量由这些 Map 打定，因此您不必亲身打定。

负载因子本身 是空间和工夫之间的调度 折衷 。 较小的负载因子将占用更多的空间，但将低落 斗嘴的也许性，从而将加快 拜访和更新的速率。 应用大于 0.75 的负载因子也许是不明智的，而应用大于 1.0 的负载因子确定是不明知的，这是由于这肯定 会引发一次斗嘴。 应用小于 0.50 的负载因子好处并不大，但只要您有效 地调度  Map 的巨细，应不会对小负载因子造成性能开销，而只会造成内存开销。 但较小的负载因子将意味着假如您未预先调度  Map 的巨细，则导致更频仍的调度 巨细，从而低落 性能，因此在调度 负载因子时肯定 要留意这个题目。

选择恰当的 Map

应应用哪种 Map？ 它是否必要 同步？ 要得到操纵措施的最佳性能，这也许是所面对的两个最重要 的题目。 当应用通用 Map 时，调度  Map 巨细和选择负载因子涵盖了 Map 调度 选项。

以下是一个用于得到最佳 Map 性能的大略 行动 

1.将您的全部  Map 变量声明为 Map，而不是任何具体 实现，即不要声明为 HashMap 或 Hashtable，或任何其他 Map 类实现。  




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

这使您可以或许只变动一行代码即可非常轻松地变更 任何特定的 Map 实例。
2.下载 Doug Lea 的 util.concurrent 措施包 ()。 将 ConcurrentHashMap 用作默认 Map。 当移植到 1.5 版时，将 java.util.concurrent.ConcurrentHashMap 用作您的默认 Map。 不要将 ConcurrentHashMap 包装在同步的包装器中，纵然它将用于多个线程。 应用默认巨细和负载因子。 
3.监测您的操纵措施。 假如创造某个 Map 造成瓶颈，则说明造成瓶颈的缘故起因 ，并部分 或整个变动该 Map 的以下内容： Map 类；Map 巨细；负载因子；关键器材  equals() 行动 实现。 专用的 Map 的根本 上都必要 出格用场的定制 Map 实现，不然通用 Map 将实现您所需的性能方针。 


Map 选择

大概您曾祈望更繁杂的考量，而这实际 上是否显得太轻易？ 好的，让我们逐渐来。 起首，您应应用哪种 Map？ 答案很大略 ： 不要为您的计划选择任何特定的 Map，除非实际 的计划必要 指定一个出格范例的 Map。 计划时通常不必要 选择具体 的 Map 实现。 您也许知道本身必要 一个 Map，但不知道应用哪种。 而这正好就是应用  Map 接口的意义地点。 直到必要 时再选择 Map 实现 — 假如到处应用 “Map”声明的变量，则变动操纵措施中任何出格 Map 的 Map 实现只必要 变动一行，这是一种开销很少的调度 选择。 是否要应用默认的 Map 实现？ 我很快将谈到这个题目。

同步 Map

同步与否有何区别？ （对付同步，您既可以应用同步的 Map，也可以应用  Collections.synchronizedMap() 将未同步的 Map 转换为同步的 Map。 后者应用 “同步的包装器”）这是一个非常繁杂的选择，完备 取决于您怎样按照多线程并发拜访和更新应用  Map，同时还必要 举办掩护方面的思量 。 譬喻，假如您起头时未并发更新特定 Map，但它其后变动为并发更新，情况将怎样？ 在这种情况下，很轻易在起头时应用一个未同步的 Map，并在其后向操纵措施中添加并发更新线程时忘怀将此未同步的 Map 变动为同步的 Map。 这将使您的操纵措施轻易瓦解 （一种要断定和跟踪的最糟糕的过错）。 但假如默认为同步，则将因随之而来的可骇 性能而序列化推行 多线程操纵措施。 看起来，我们必要 某种决定 树来赞助 我们精确 选择。

Doug Lea 是纽约州立大学奥斯威戈分校打定机科学系的传授。 他创建 了一组民众范围的措施包（统称 util.concurrent），该措施包包孕很多可以简化高性能并行编程的适用措施类。 这些类中包孕两个 Map，即 ConcurrentReaderHashMap 和 ConcurrentHashMap。 这些 Map 实现是线程安详的，并且 不必要 对并发拜访或更新举办同步，同时还适用于大多数必要  Map 的情况。 它们还远比同步的 Map（如 Hashtable）或应用同步的包装器更具伸缩性，并且 与 HashMap 相比，它们对性能的粉碎 很小。 util.concurrent 措施包构成 了 JSR166 的根本 ；JSR166 已经开拓了一个包孕在 Java 1.5 版中的并发适用措施，而 Java 1.5 版将把这些 Map 包孕在一个新的 java.util.concurrent 措施包中。

全部这统统意味着您不必要 一个决定 树来决议 是应用同步的 Map 照样应用非同步的 Map， 而只需应用  ConcurrentHashMap。 固然 ，在某些情况下，应用  ConcurrentHashMap 并不适宜 。 但这些情况很少见，并且 应具体 情况具体 处理赏罚 。 这就是监测的用场。



收场语

通过 Oracle JDeveloper 可以非常轻松地创建 一个用于比拟 种种  Map 性能的测试类。 更重要 的是，集成优良的监测器可以在开拓过程中快速、轻松地识别性能瓶颈 - 集成到 IDE 中的监测器通常被较频仍地应用，以便赞助 构建一个乐成 的工程。 如今，您已经拥有了一个监测器并了解 了有关通用 Map 及其性能的根本 知识，可以起头运行您本身的测试，以查明您的操纵措施是否因 Map 而存在瓶颈以及在那边 必要 变动所应用的 Map。

以上内容先容了通用 Map 及其性能的根本 知识。 固然 ，有关特定 Map 实现以及怎样按照差别 的需求应用它们还存在更多繁杂和值得存眷的事项，这些将在本文第 2 部分 中先容。


--------------------------------------------------------------------------------
Jack Shirazi 是 O'Reilly 的“Java 性能调度 ”的作者，以及受迎接的 JavaPerformanceTuning.com 网站（供给  Java 性能信息的环球闻名站点）的总监。 Jack 在 Java 性能范围供给 咨询并著书立说。 他还监督  JavaPerformanceTuning.com 供给 的信息，此中包孕每年约莫公布  1000 条性能技能 以及很多有关性能器材、讨论组等内容的文章。 Jack 从前还曾公布 有关卵白质结构猜测以及黑洞热力学方面的文章，并且在其空闲时还对某些 Perl5 核心 模块作出了孝敬 。