容器深入研究（6）：理解Map

深藏阁楼爱情的钟 2023-07-24 11:41 26阅读 0赞

###   一、理解Map ###

正如你在持有对象章节中所学到的，映射表（也称为关联数组）的基本思想是它维护的是键-值（对）关联，因此你可以使用键来查找值。标准的java类库中包含了Map的几种基本实现，包括：HashMap，TreeMap，LinkedHashMap，WeakHashMap，ConcurrentHashMap，IdentityHashMap。它们都有同样的基本接口Map，但是行为特性各不相同，这表现在效率、键值对的保存及呈现次序、对象的保存周期、映射表如何在多线程程序中工作和判定“键”等价的策略等方面。Map接口实现的数量应该可以让你感觉到这种工具的重要性。

你可以获得对Map更深入的理解，这有助于观察关联数组是如何创建的。下面是一个及其简单的实现：

public class AssociativeArray<K, V> {
    	private Object[][] pairs;
    	private int index;
    
    	public AssociativeArray(int length) {
    		pairs = new Object[length][2];
    	}
    
    	public void put(K key, V value) {
    		if (index >= pairs.length) {
    			throw new ArrayIndexOutOfBoundsException();
    		}
    		pairs[index++] = new Object[] { key, value };
    	}
    
    	@SuppressWarnings("unchecked")
    	public V get(K key) {
    		for (int i = 0; i < index; i++) {
    			if (key.equals(pairs[i][0])) {
    				return (V) pairs[i][1];
    			}
    		}
    		return null;
    	}
    
    	public String toString() {
    		StringBuilder result = new StringBuilder();
    		for (int i = 0; i < index; i++) {
    			result.append(pairs[i][0].toString());
    			result.append(" : ");
    			result.append(pairs[i][1].toString());
    			if (i < index - 1) {
    				result.append("\n");
    			}
    		}
    		return result.toString();
    	}
    
    	public static void main(String[] args) {
    		AssociativeArray<String, String> map = new AssociativeArray<>(6);
    		map.put("sky", "blue");
    		map.put("grass", "green");
    		map.put("ocean", "dancing");
    		map.put("tree", "tall");
    		map.put("earth", "brown");
    		map.put("sun", "warm");
    		try {
    			map.put("extra", "object");
    		} catch (ArrayIndexOutOfBoundsException e) {
    			System.out.println("Too many objects!");
    		}
    		System.out.println(map);
    		System.out.println(map.get("ocean"));
    	}
    }

关联数组中的基本方法是put()和get()，但是为了容易显示，toString()方法被覆盖为可以打印键-值对。为了展示它可以工作，main()用字符串对加载了一个AssociativeArray，并打印了所产生的映射表，随后是获取一个值的get()。

为了使用get()方法，你需要传递想要查找的key，然后它将会与之相关联的值作为结果返回，或者在找不到的情况下返回null。get()方法使用的可能是能想象到的效率最差的方式来定位值的：从数组的头部开始，使用equals()方法依次比较键。但是这里的关键是简单性而不是效率。

因此上面的版本是说明性的，但是缺乏效率，并且由于具有固定的尺寸而显得很不灵活，幸运的是，在java.util中的各种Map都没有这些问题，并且都可以替代到上面的示例中。

### 二、性能 ###

性能是映射表中的一个重要的问题，当在get()中使用线性搜索时，执行速度会相当的慢，而这正是HashMap提高速度的地方。HashMap使用了特殊的值，称作散列码，来取代对键的缓慢搜索。散列码是“相对唯一”的、用以代表对象的int值，它是通过将该对象的某些信息进行转换而生成的。hashCode()是根类Object中的方法，因此所有java对象都能产生散列码。HashMap就是使用对象的hashCode()进行快速查询的，此方法能够显著提高性能。

下面是基本的Map实现。在HashMap上打星号表示如果没有其他的限制，它就应该成为你的默认选择，因为它对速度进行了优化。其他实现强调了其他的特性，因此都不如HashMap快。

<table> 
 <tbody> 
  <tr> 
   <td style="width:159px;">HashMap*</td> 
   <td>Map基于散列表的实现（它取代了Hashtable）。插入和查询“键值对”的开销是固定的。可以通过构造器设置容量和负载因子，以调整容器的性能</td> 
  </tr> 
  <tr> 
   <td style="width:159px;">LinkedHashMap</td> 
   <td>类似于HashMap，但是迭代遍历它时，取得“键值对”的顺序是其插入次序，或者是最近最少使用（LRU）的次序。只比HashMap慢一点，而在迭代访问时反而更快，因为它使用链表维护内部次序。</td> 
  </tr> 
  <tr> 
   <td style="width:159px;">TreeMap</td> 
   <td>基于红黑树的实现。查看“键”或“键值对”时，它们会被排序（次序由Comparable或Comparator决定）。TreeMap的特点在于，所得到的结果是经过排序的。TreeMap是唯一带有subMap()方法的Map，它可以返回一个子树。</td> 
  </tr> 
  <tr> 
   <td style="width:159px;">WeakHashMap</td> 
   <td>弱键（weak key）映射，允许释放映射所指向的对象；这是为解决某类特殊问题而设计的。如果映射之外没有引用指向某个“键”，则此“键”可以被垃圾收集器回收</td> 
  </tr> 
  <tr> 
   <td style="width:159px;">ConcurrentHashMap</td> 
   <td>一种线程安全的Map，它不涉及同步加锁。我们将在“并发”一章中讨论</td> 
  </tr> 
  <tr> 
   <td style="width:159px;">IdentityHashMap</td> 
   <td>使用==代替equals()对“键”进行比较的散列映射。专为解决特殊问题而设计的</td> 
  </tr> 
 </tbody> 
</table>

散列是映射中存储元素的最常用的方式。稍后你将会了解散列机制是如何工作的。

对Map中使用的键的要求与对Set中的元素的要求一样，在TypesForSets.java中展示了这一点。任何键都必须具有equals()方法；如果键被用于散列Map，那么它必须还具有恰当的hashCode()方法；如果键被用于TreeMap，那么它必须实现Comparable。

下面的示例展示了通过Map接口可用的操作，这里使用了前面定义过的CountingMapData测试数据集：

import java.util.HashMap;
    import java.util.IdentityHashMap;
    import java.util.LinkedHashMap;
    import java.util.Map;
    import java.util.TreeMap;
    import java.util.WeakHashMap;
    import java.util.concurrent.ConcurrentHashMap;
    
    import com.buba.util.CountingMapData;
    
    public class Maps {
    	public static void printKeys(Map<Integer, String> map) {
    		System.out.println("Size = " + map.size());
    		System.out.println("Keys = " + map.keySet());
    	}
    
    	public static void test(Map<Integer, String> map) {
    		System.out.println("-------------------------------");
    		System.out.println(map.getClass().getSimpleName());
    		map.putAll(new CountingMapData(25));
    		map.putAll(new CountingMapData(25));
    		printKeys(map);
    		System.out.println("Values :" + map.values());
    		System.out.println(map);
    		System.out.println("map.containsKey(11) : " + map.containsKey(11));
    		System.out.println("map.get(11) : " + map.get(11));
    		System.out.println("map.containsValue(\"F0\") : " + map.containsValue("F0"));
    		Integer key = map.keySet().iterator().next();
    		System.out.println("First key int map : " + key);
    		map.remove(key);
    		printKeys(map);
    		map.clear();
    		System.out.println("map.isEmpty() : " + map.isEmpty());
    		map.putAll(new CountingMapData(25));
    		map.keySet().removeAll(map.keySet());
    		System.out.println("map.isEmpty() : " + map.isEmpty());
    	}
    
    	public static void main(String[] args) {
    		test(new HashMap<Integer, String>());
    		test(new TreeMap<Integer, String>());
    		test(new LinkedHashMap<Integer, String>());
    		test(new IdentityHashMap<Integer, String>());
    		test(new ConcurrentHashMap<Integer, String>());
    		test(new WeakHashMap<Integer, String>());
    	}
    }

printKeys()展示了如何生成Map的Collection视图。keySet()方法返回由Map的键组成的Set。因为在SE5提供了改进的打印支持，你可以直接打印values()方法的结果，该方法会产生一个包含Map中所有“值”的Collection。（注意，键必须是唯一的，而值可以有重复。）由于这些Collection背后是由Map支持的，所以对Collection的任何改动都会反映到与之相关联的Map。

### 三、SortedMap ###

使用SortedMap（TreeMap是其现阶段的唯一实现），可以确保键处于排序状态。这使得它具有额外的功能，这些功能有SortedMap接口中的下列方法提供：

*  Comparator comparator()返回当前Map使用的Comparator；或者返回null，表示以自然方式排序。
 *  T firstKey()返回Map中的第一个键。
 *  T lastKey()返回Map中的最末一个键。
 *  SortedMap subMap（fromKey，toKey）生成此Map的子集，范围由fromKey（包含）到toKey（不包含）的键确定。
 *  SortedMap headMap（toKey）生成此Map的子集，由键小于toKey的所有键值对组成。
 *  SortedMap tailMap（formKey）生成此Map的子集，由键大于或等于formKey的所有键值组成。

下面的例子与SortedSetDemo.java相似，演示了TreeMap新增的功能：

import java.util.Iterator;
    import java.util.TreeMap;
    
    import com.buba.util.CountingMapData;
    
    public class SortedMapDemo {
    	public static void main(String[] args) {
    		TreeMap<Integer, String> sortedMap = new TreeMap<>(new CountingMapData(10));
    		System.out.println(sortedMap);
    		Integer low = sortedMap.firstKey();
    		Integer high = sortedMap.lastKey();
    		System.out.println(low);
    		System.out.println(high);
    		Iterator<Integer> it = sortedMap.keySet().iterator();
    		for (int i = 0; i <= 6; i++) {
    			if (i == 3)
    				low = it.next();
    
    			if (i == 6)
    				high = it.next();
    			else
    				it.next();
    		}
    		System.out.println(low);
    		System.out.println(high);
    		System.out.println(sortedMap.subMap(low, high));
    		System.out.println(sortedMap.headMap(high));
    		System.out.println(sortedMap.tailMap(low));
    	}
    }

此处，键值对是按键的次序排列的。TreeMap中的次序是有意义的，因此“位置”的概念才有意义，所以才能取得第一个和最后一个元素，并且可以提取Map的子集。

### 四、LinkedHashMap ###

为了提高速度，LinkedHashMap散列化所有的元素，但是在遍历键值对时，却又以元素插入顺序返回键值对（System.out.println()会迭代遍历该映射，因此可以看到遍历的结果）。此外，可以在构造器中设定LinkedHashMap，使之采用基于访问的最近最少使用（LRU）算法，于是没有被访问过的（可被看作需要删除的）元素就会出现在队列的前面。对于需要定期清理元素以节省空间的程序，此功能使得程序很容易得以实现。下面就是一个简单的例子，它演示了LinkedHashMap的这两种特点：

import java.util.LinkedHashMap;
    
    import com.buba.util.CountingMapData;
    
    public class LinkedHashMapDemo {
    	public static void main(String[] args) {
    		LinkedHashMap<Integer, String> linkedMap = new LinkedHashMap<>(new CountingMapData(9));
    		System.out.println(linkedMap);
    		linkedMap = new LinkedHashMap<>(16, 0.75f, true);
    		linkedMap.putAll(new CountingMapData(9));
    		System.out.println(linkedMap);
    		for (int i = 0; i < 6; i++) {
    			linkedMap.get(i);
    		}
    		System.out.println(linkedMap);
    		linkedMap.get(0);
    		System.out.println(linkedMap);
    	}
    }

在输出中可以看到，键值对是以插入的顺序进行遍历的，甚至LRU算法的版本也是如此。但是，在LRU版本中，在（只）访问过前面六个元素后，最后三个元素移到了队列前面。然后再一次访问元素“o”时，它就被移到队列后端了。

**如果本文对您有很大的帮助，还请点赞关注一下。**