java集合类详解(四)：Map

1、Map
1.1、概述
      数学中的映射关系在Java中就是通过Map来实现的。它表示，里面存储的元素是一个对,我们通过一个对象，可以在这个映射关系中找到另外一个和这个对象相关的东西。 
      前面提到的我们对于根据帐号名得到对应的人员的信息，就属于这种情况的应用。我们讲一个人员的帐户名和这人员的信息作了一个映射关系，也就是说，我们把帐户名和人员信息当成了一个“键值对”，“键”就是帐户名，“值”就是人员信息。下面我们先看看Map 接口的常用方法。 
1.2、常用方法 
     Map 接口不是 Collection 接口的继承。而是从自己的用于维护键-值关联的接口层次结构入手。按定义，该接口描述了从不重复的键到值的映射。 
     我们可以把这个接口方法分成三组操作：改变、查询和提供可选视图。 
     改变操作允许您从映射中添加和除去键-值对。键和值都可以为 null。但是，您不能把 Map 作为一个键或值添加给自身。 
     Object put(Object key,Object value)：用来存放一个键-值对Map中 
     Object remove(Object key)：根据key(键)，移除一个键-值对，并将值返回 
     void putAll(Map mapping) ：将另外一个Map中的元素存入当前的Map中 
     void clear() ：清空当前Map中的元素 
     查询操作允许您检查映射内容： 
     Object get(Object key) ：根据key(键)取得对应的值 
     boolean containsKey(Object key) ：判断Map中是否存在某键（key） 
     boolean containsValue(Object value):判断Map中是否存在某值(value) 
     int size():返回Map中 键-值对的个数 
     boolean isEmpty() ：判断当前Map是否为空 
     最后一组方法允许您把键或值的组作为集合来处理。 
     public Set keySet() ：返回所有的键（key），并使用Set容器存放 
     public Collection values() ：返回所有的值（Value），并使用Collection存放 
     public Set entrySet() ：返回一个实现 Map.Entry 接口的元素 Set 
     因为映射中键的集合必须是唯一的，就使用 Set 来支持。因为映射中值的集合可能不唯一，就使用 Collection 来支持。最后一个方法返回一个实现 Map.Entry 接口的元素 Set。 
     我们看看Map的常用实现类的比较，如下表： 
      Map,保存键值对成员，基于键找值操作，使用compareTo或compare方法对键进行排序 
      HashMap,能满足用户对Map的通用需求 键成员可为任意Object子类的对象，但如果覆盖了equals方法，同时注意修改hashCode方法。 
     TreeMap,支持对键有序地遍历，使用时建议先用HashMap增加和删除成员，最后从HashMap生成TreeMap； 附加实现了SortedMap接口，支持子Map等要求顺序的操作 键成员要求实现Comparable接口，或者使用Comparator构造TreeMap键成员一般为同一类型。 
     LinkedHashMap,保留键的插入顺序，用equals 方法检查键和值的相等性 成员可为任意Object子类的对象，但如果覆盖了equals方法，同时注意修改hashCode方法。 
     下面我们看一个简单的例子：

import java.util.*;

public class MapTest {

   public static void main(String[] args) {

      Map map1 = new HashMap();

      Map map2 = new HashMap();

      map1.put("1", "aaa1");

      map1.put("2", "bbb2");

      map2.put("10", "aaaa10");

      map2.put("11", "bbbb11");

      // 根据键 "1" 取得值："aaa1"

      System.out.println("map1.get(\"1\")=" + map1.get("1"));

      // 根据键 "1" 移除键值对"1"-"aaa1"

      System.out.println("map1.remove(\"1\")=" + map1.remove("1"));

      System.out.println("map1.get(\"1\")=" + map1.get("1"));

      map1.putAll(map2);// 将map2全部元素放入map1中

      map2.clear();// 清空map2

      System.out.println("map1 IsEmpty?=" + map1.isEmpty());

      System.out.println("map2 IsEmpty?=" + map2.isEmpty());

      System.out.println("map1 中的键值对的个数size = " + map1.size());

      System.out.println("KeySet=" + map1.keySet());// set

      System.out.println("values=" + map1.values());// Collection

      System.out.println("entrySet=" + map1.entrySet());

      System.out.println("map1 是否包含键：11 = " + map1.containsKey("11"));

      System.out.println("map1 是否包含值：aaa1 = " + map1.containsValue("aaa1"));

   }

}

      运行输出结果为： 
       map1.get("1")=aaa1 
       map1.remove("1")=aaa1 
       map1.get("1")=null 
       map1 IsEmpty?=false 
       map2 IsEmpty?=true 
       map1 中的键值对的个数size = 3 
       KeySet=[10, 2, 11] 
       values=[aaaa10, bbb2, bbbb11] 
       entrySet=[10=aaaa10, 2=bbb2, 11=bbbb11] 
       map1 是否包含键：11 = true 
       map1 是否包含值：aaa1 = false 
       在该例子中，我们创建一个HashMap，并使用了一下Map接口中的各个方法。 
       其中Map中的entrySet()方法先提一下，该方法返回一个实现 Map.Entry 接口的对象集合。集合中每个对象都是底层 Map 中一个特定的键-值对。 
       Map.Entry 接口是Map 接口中的一个内部接口，该内部接口的实现类存放的是键值对。在下面的实现原理中，我们会对这方面再作介绍，现在我们先不管这个它的具体实现。 
      我们再看看排序的Map是如何使用：

import java.util.*;

public class MapSortExample {

   public static void main(String args[]) {

      Map map1 = new HashMap();

      Map map2 = new LinkedHashMap();

      for (int i = 0; i < 10; i++) {

        double s=Math.random()*100;//产生一个随机数,并将其放入Map中

        map1.put(new Integer((int)s),"第"+i+"个放入的元素："+s+"\n");

        map2.put(new Integer((int)s),"第"+i+"个放入的元素:"+s+"\n");

      }

      System.out.println("未排序前HashMap：" + map1);

      System.out.println("未排序前LinkedHashMap：" + map2);

      // 使用TreeMap来对另外的Map进行重构和排序

      Map sortedMap = new TreeMap(map1);

      System.out.println("排序后：" + sortedMap);

      System.out.println("排序后：" + new TreeMap(map2));

   }

}

     该程序的一次运行结果为： 
     未排序前HashMap：{64=第 1 个放入的元素：64.05341725531845 
      , 15=第 9 个放入的元素：15.249165766266382 
      , 2=第 4 个放入的元素：2.66794706854534 
      , 77=第 0 个放入的元素：77.28814965781416 
      , 97=第 5 个放入的元素：97.32893518378948 
      , 99=第 2 个放入的元素：99.99412014935982 
      , 60=第 8 个放入的元素：60.91451419025399 
      , 6=第 3 个放入的元素：6.286974058646977 
      , 1=第 7 个放入的元素：1.8261658496439903 
      , 48=第 6 个放入的元素：48.736039522423106 
      } 
      未排序前LinkedHashMap：{77=第 0 个放入的元素：77.28814965781416 
      , 64=第 1 个放入的元素：64.05341725531845 
      , 99=第 2 个放入的元素：99.99412014935982 
      , 6=第 3 个放入的元素：6.286974058646977 
      , 2=第 4 个放入的元素：2.66794706854534 
      , 97=第 5 个放入的元素：97.32893518378948 
      , 48=第 6 个放入的元素：48.736039522423106 
      , 1=第 7 个放入的元素：1.8261658496439903 
      , 60=第 8 个放入的元素：60.91451419025399 
      , 15=第 9 个放入的元素：15.249165766266382 
       } 
      排序后：{1=第 7 个放入的元素：1.8261658496439903 
      , 2=第 4 个放入的元素：2.66794706854534 
      , 6=第 3 个放入的元素：6.286974058646977 
      , 15=第 9 个放入的元素：15.249165766266382 
      , 48=第 6 个放入的元素：48.736039522423106 
      , 60=第 8 个放入的元素：60.91451419025399 
      , 64=第 1 个放入的元素：64.05341725531845 
      , 77=第 0 个放入的元素：77.28814965781416 
      , 97=第 5 个放入的元素：97.32893518378948 
      , 99=第 2 个放入的元素：99.99412014935982 
      } 
      排序后：{1=第 7 个放入的元素：1.8261658496439903 
      , 2=第 4 个放入的元素：2.66794706854534 
      , 6=第 3 个放入的元素：6.286974058646977 
      , 15=第 9 个放入的元素：15.249165766266382 
      , 48=第 6 个放入的元素：48.736039522423106 
      , 60=第 8 个放入的元素：60.91451419025399 
      , 64=第 1 个放入的元素：64.05341725531845 
      , 77=第 0 个放入的元素：77.28814965781416 
      , 97=第 5 个放入的元素：97.32893518378948 
      , 99=第 2 个放入的元素：99.99412014935982 
       } 
      从运行结果，我们可以看出，HashMap的存入顺序和输出顺序无关。而LinkedHashMap 则保留了键值对的存入顺序。TreeMap则是对Map中的元素进行排序。在实际的使用中我们也经常这样做：使用HashMap或者LinkedHashMap 来存放元素，当所有的元素都存放完成后，如果使用则是需要一个经过排序的Map的话，我们再使用TreeMap来重构原来的Map对象。这样做的好处是：因为HashMap和LinkedHashMap 存储数据的速度比直接使用TreeMap 要快，存取效率要高。当完成了所有的元素的存放后，我们再对整个的Map中的元素进行排序。这样可以提高整个程序的运行的效率，缩短执行时间。 
      这里需要注意的是，TreeMap中是根据键（Key）进行排序的。而如果我们要使用TreeMap来进行正常的排序的话，Key 中存放的对象必须实现Comparable 接口。 
      我们简单介绍一下这个接口：
 1.3、Comparable 接口 
      在 java.lang 包中，Comparable 接口适用于一个类有自然顺序的时候。假定对象集合是同一类型，该接口允许您把集合排序成自然顺序。 
      它只有一个方法：compareTo() 方法，用来比较当前实例和作为参数传入的元素。如果排序过程中当前实例出现在参数前（当前实例比参数大），就返回某个负值。如果当前实例出现在参数后（当前实例比参数小），则返回正值。否则，返回零。如果这里不要求零返回值表示元素相等。零返回值可以只是表示两个对象在排序的时候排在同一个位置。 
      上面例子中的整形的包装类：Integer 就实现了该接口。我们可以看一下这个类的源码： 
      可以看到compareTo 方法里面通过判断当前的Integer对象的值是否大于传入的参数的值来得到返回值的。
 在 Java 2 SDK，版本 1.2 中有十四个类实现 Comparable 接口。下表展示了它们的自然排序。虽然一些类共享同一种自然排序，但只有相互可比的类才能排序。 
      BigDecimal, BigInteger, Byte, Double, Float, Integer, Long, Short 按数字大小排序 
      Character 按 Unicode 值的数字大小排序 
      CollationKey 按语言环境敏感的字符串排序 
      Date 按年代排序 
      File 按系统特定的路径名的全限定字符的 Unicode 值排序 
      ObjectStreamField 按名字中字符的 Unicode 值排序 
      String 按字符串中字符 Unicode 值排序 
      这里只是简单的介绍一下排序接口，如果要详细的了解排序部分内容的话，可以参考文章最后的附录部分对于排序的更加详细的描述。 
      我们再回到Map中来，Java提高的API中除了上面介绍的几种Map比较常用以为还有一些Map，大家可以了解一下： 
      a、WeakHashMap： WeakHashMap 是 Map 的一个特殊实现，它只用于存储对键的弱引用。当映射的某个键在 WeakHashMap 的外部不再被引用时，就允许垃圾收集器收集映射中相应的键值对。使用 WeakHashMap 有益于保持类似注册表的数据结构，其中条目的键不再能被任何线程访问时，此条目就没用了。 
      b、IdentifyHashMap： Map的一种特性实现，关键属性的hash码不是由hashCode()方法计算，而是由System.identityHashCode 方法计算，使用==进行比较而不是equals()方法。 
      通过简单的对与Map中各个常用实现类的使用，为了更好的理解Map，下面我们再来了解一下Map的实现原理。
1.4、实现原理 
      有的人可能会认为 Map 会继承 Collection。在数学中，映射只是对（pair）的集合。但是，在“集合框架”中，接口 Map 和 Collection 在层次结构没有任何亲缘关系，它们是截然不同的。这种差别的原因与 Set 和 Map 在 Java 库中使用的方法有关。Map 的典型应用是访问按关键字存储的值。它支持一系列集合操作的全部，但操作的是键-值对，而不是单个独立的元素。因此 Map 需要支持 get() 和 put() 的基本操作，而 Set 不需要。此外，还有返回 Map 对象的 Set 视图的方法： 
      Set set = aMap.keySet(); 
      下面我们以HashMap为例，对Map的实现机制作一下更加深入一点的理解。 
      因为HashMap里面使用Hash算法，所以在理解HashMap之前，我们需要先了解一下Hash算法和Hash表。 
      Hash，一般翻译做“散列”，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做 预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能 会散列成相同的输出，而不可能从散列值来唯一的确定输入值。
 说的通俗一点，Hash算法的意义在于提供了一种快速存取数据的方法,它用一种算法建立键值与真实值之间的对应关系,(每一个真实值只能有一个键值,但是一个键值可以对应多个真实值),这样可以快速在数组等里面存取数据。 
      我们建立一个HashTable（哈希表），该表的长度为N，然后我们分别在该表中的格子中存放不同的元素。每个格子下面存放的元素又是以链表的方式存放元素。 
      a、当添加一个新的元素Entry 的时候，首先我们通过一个Hash函数计算出这个Entry元素的Hash值hashcode。通过该hashcode值，就可以直接定位出我们应该把这个Entry元素存入到Hash表的哪个格子中，如果该格子中已经存在元素了，那么只要把新的Entry元存放到这个链表中即可。 
      b、如果要查找一个元素Entry的时候，也同样的方式，通过Hash函数计算出这个Entry元素的Hash值hashcode。然后通过该hashcode值，就可以直接找到这个Entry是存放到哪个格子中的。接下来就对该格子存放的链表元素进行逐个的比较查找就可以了。 
      举一个比较简单的例子来说明这个算法的运算方式： 
      假定我们有一个长度为8的Hash表（可以理解为一个长度为8的数组）。在这个Hash表中存放数字：如下表 
      0 1 2 3 4 5 6 7 
      假定我们的Hash函数为： 
      Hashcode = X%8    -------- 对8 取余数 
      其中X就是我们需要放入Hash表中的数字，而这个函数返回的Hashcode就是Hash码。 
      假定我们有下面10个数字需要依次存入到这个Hash表中： 
      11 , 23 , 44 , 9 , 6 , 32 , 12 , 45 , 57 , 89 
      通过上面的Hash函数，我们可以得到分别对应的Hash码： 
      11――3 ; 23――7　；44――4　；9――1；6――6；32――0；12――4；45――5；57――1；89――1； 
      计算出来的Hash码分别代表，该数字应该存放到Hash表中的哪个对应数字的格子中。如果改格子中已经有数字存在了，那么就以链表的方式将数字依次存放在该格子中，如下表： 
      0 1 2 3 4 5 6 7 
      32 9 11 44 45 6 23 
      57 12 
      89 
      Hash表和Hash算法的特点就是它的存取速度比数组差一些，但是比起单纯的链表，在查找和存储方面却要好很多。同时数组也不利于数据的重构而排序等方面的要求。 
      更具体的说明，读者可以参考数据结构相关方面的书籍。 
      简单的了解了一下Hash算法后，我们就来看看HashMap的属性有哪些： 
      里面最重要的3个属性： 
      transient Entry[] table: 用来存放键值对的对象Entry数组，也就是Hash表
 transient int size：当前Map中存放的键值对的个数 
      final float loadFactor：负载因子，用来决定什么情况下应该对Entry进行扩容 
      我们Entry 对象是Map接口中的一个内部接口。即是使用它来保存我们的键值对的。 
      我们看看这个Entry 内部接口在HashMap中的实现： 
      通过查看源码，我们可以看到Entry类有点类似一个单向链表。其中： 
      final Object key　和　Object value;存放的就是我们放入Map中的键值对。 
      而属性Entry next;表示当前键值对的下一个键值对是哪个Entry。 
      接下来，我们看看HashMap的主要的构造函数： 
      我们主要看看 public HashMap(int initialCapacity, float loadFactor) 
      因为，另外两个构造函数实行也是同样的方式进行构建一个HashMap 的。 
      该构造函数： 
      1.首先是判断参数int initialCapacity和float loadFactor是否合法 
      2.然后确定Hash表的初始化长度。确定的策略是：通过传进来的参数initialCapacity 来找出第一个大于它的2的次方的数。比如说我们传了18这样的一个initialCapacity 参数，那么真实的table数组的长度为2的5次方，即32。之所以采用这种策略来构建Hash表的长度，是因为2的次方的运算对于现代的处理器来说，可以通过一些方法得到更加好的执行效率。 
      3.接下来就是得到重构因子（threshold）了，这个属性也是HashMap中的一个比较重要的属性，它表示，当Hash表中的元素被存放了多少个之后，我们就需要对该Hash表进行重构。 
      4.最后就是使用得到的初始化参数capacity 来构建Hash表：Entry[] table。 
      下面我们看看一个键值对是如何添加到HashMap中的。 
     该put方法是用来添加一个键值对（key-value）到Map中，如果Map中已经存在相同的键的键值对的话，那么就把新的值覆盖老的值，并把老的值返回给方法的调用者。如果不存在一样的键，那么就返回null 。我们看看方法的具体实现： 
      1.首先我们判断如果key为null则使用一个常量来代替该key值，该行为在方法maskNull（）终将key替换为一个非null 的对象k。 
      2.计算key值的Hash码：hash 
      3.通过使用Hash码来定位，我们应该把当前的键值对存放到Hash表中的哪个格子中。indexFor()方法计算出的结果：i 就是Hash表（table）中的下标。 
      4.然后遍历当前的Hash表中table[i]格中的链表。从中判断已否已经存在一样的键(Key)的键值对。如果存在一样的key的键，那么就用新的value覆写老的value，并把老的value返回 
      5.如果遍历后发现没有存在同样的键值对，那么就增加当前键值对到Hash表中的第i个格子中的链表中。并返回null 。 
      最后我们看看一个键值对是如何添加到各个格子中的链表中的： 
      我们先看void addEntry(int hash, Object key, Object value, int bucketIndex)方法，该方法的作用就用来添加一个键值对到Hash表的第bucketIndex个格子中的链表中去。这个方法作的工作就是： 
      1.创建一个Entry对象用来存放键值对。 
      2.添加该键值对 ---- Entry对象到链表中 
      3.最后在size属性加一，并判断是否需要对当前的Hash表进行重构。如果需要就在void resize(int newCapacity)方法中进行重构。 
      之所以需要重构，也是基于性能考虑。大家可以考虑这样一种情况，假定我们的Hash表只有4个格子，那么我们所有的数据都是放到这4个格子中。如果存储的数据量比较大的话，例如100。这个时候，我们就会发现，在这个Hash表中的4个格子存放的4个长长的链表。而我们每次查找元素的时候，其实相当于就是遍历链表了。这种情况下，我们用这个Hash表来存取数据的性能实际上和使用链表差不多了。 
      但是如果我们对这个Hash表进行重构，换为使用Hash表长度为200的表来存储这100个数据，那么平均2个格子里面才会存放一个数据。这个时候我们查找的数据的速度就会非常的快。因为基本上每个格子中存放的链表都不会很长，所以我们遍历链表的次数也就很少，这样也就加快了查找速度。但是这个时候又存在了另外的一个问题。我们使用了至少200个数据的空间来存放100个数据，这样就造成至少100个数据空间的浪费。 在速度和空间上面，我们需要找到一个适合自己的中间值。在HashMap中我们通过负载因子     （loadFactor）来决定应该什么时候应该重构我们的Hash表，以达到比较好的性能状态。
 我们再看看重构Hash表的方法：void resize(int newCapacity)是如何实现的： 
      它的实现方式比较简单： 
      1.首先判断如果Hash表的长度已经达到最大值，那么就不进行重构了。因为这个时候Hash表的长度已经达到上限，已经没有必要重构了。 
      2.然后就是构建新的Hash表 
      3.把老的Hash表中的对象数据全部转移到新的Hash表newTable中，并设置新的重构因子threshold 
      对于HashMap中的实现原理，我们就分析到这里。大家可能会发现，HashCode的计算，是用来定位我们的键值对应该放到Hash表中哪个格子中的关键属性。而这个HashCode的计算方法是调用的各个对象自己的实现的hashCode()方法。而这个方法是在Object对象中定义的，所以我们自己定义的类如果要在集合中使用的话，就需要正确的覆写hashCode() 方法。下面就介绍一下应该如何正确覆写hashCode()方法。
 1.5、覆写hashCode() 
      在明白了HashMap具有哪些功能，以及实现原理后，了解如何写一个hashCode()方法就更有意义了。当然，在HashMap中存取一个键值对涉及到的另外一个方法为equals ()，因为该方法的覆写在高级特性已经讲解了。这里就不做过多的描述。 
      设计hashCode（）时最重要的因素就是：无论何时，对同一个对象调用hashCode()都应该生成同样的值。如果在将一个对象用put（）方法添加进HashMap时产生一个hashCode()值，而用get()取出时却产生了另外一个hashCode()值，那么就无法重新取得该对象了。所以，如果你的hashCode()方法依赖于对象中易变的数据，那用户就要小心了，因为此数据发生变化时，hashCode()就会产生一个不同的hash码，相当于产生了一个不同的“键”。 
      此外，也不应该使hashCode()依赖于具有唯一性的对象信息，尤其是使用this的值，这只能产生很糟糕的hashCode()。因为这样做无法生成一个新的“键”，使之与put()种原始的“键值对”中的“键”相同。例如，如果我们不覆写Object的hashCode()方法，那么调用该方法的时候，就会调用Object的hashCode()方法的默认实现。Object的hashCode（）方法，返回的是当前对象的内存地址。下次如果我们需要取一个一样的“键”对应的键值对的时候，我们就无法得到一样的hashCode值了。因为我们后来创建的“键”对象已经不是存入HashMap中的那个内存地址的对象了。 
      我们看一个简单的例子，就能更加清楚的理解上面的意思。假定我们写了一个类：Person （人），我们判断一个对象“人”是否指向同一个人，只要知道这个人的身份证号一直就可以了。 
      先看我们没有实现hashCode的情况： 
 

package c08.hashEx;

import java.util.*;

//身份证类

class Code {

   final int id;//身份证号码已经确认,不能改变

 

   Code(int i) {

      id = i;

   }

   //身份号号码相同，则身份证相同

   public boolean equals(Object anObject) {

      if (anObject instanceof Code) {

        Code other = (Code) anObject;

        return this.id == other.id;

      }

      return false;

   }

   <s

java集合类详解(三)：List | java集合类详解(五)：Set

• 2010-12-01 14:19
• 浏览 2025
• 评论(0)
• 分类:企业架构
• 查看更多