15. 映射、集合与关联数据建模¶
15.1. 映射和集合接口¶
到目前为止，我们一直使用 List 接口作为 Java 中容器的基本形式。然而，另外两个定义具有不同属性的容器的接口是 Map 和 Set 。 Map 和 Set 接口类似于 List ，因为 java.util 集合框架中有多个类实现了它们。主要区别在于它们以不同的方式组织值，这意味着你以不同的方式添加和访问值。
15.2. 映射接口¶
Map<K, V> 接口的建模灵感来自于在字典中查找单词释义。在计算机科学中，你会听到人们使用"映射"、"字典"、"散列"甚至"关联数组"等名称来指代这种"查找"结构。你可以将映射视为一组相互关联的 元素对 的集合。一个对由一个可以查找其值的 键 和一个对应于查找其键时得到的结果的 值 组成。如果你想到一本单词字典，字典中的每个条目由一个"单词"和其"释义"组成。我们称"单词"为"键"，其释义为"值"，字典本身就是一个键值对（单词和释义）的集合。你有时会将映射中的元素称为 键值对 ，因为它包含连接的值对。
对可以被添加到映射中，也可以从映射中移除。映射不能拥有具有相同键的不同对；如果你尝试将一个对添加到已经包含具有相同键的对的映射中，第二个对将替换第一个。
Map<K, V> 接口定义了映射操作。它接受两个独立的泛型类型参数： K 是指定键类型的类型参数， V 是指定值类型的类型参数。例如， K 可以是 Integer ， V 可以是 String 。或者 K 和 V 都可以是 Boolean 。或者 K 可以是 Jeroo ， V 可以是 List<Flower> 。组合方式没有限制！
最重要的 Map 操作如下：
public V put(K key, V val); // store a given key,value pair
public V get(K key); // get the value associated with given key
public V remove(K key); // remove key,value pair for given key
public boolean containsKey(K key); // determine whether key exists in Map
public Set<K> keySet(); // return the set of keys
15.2.1. 实现 Map 的类¶
HashMap 和 TreeMap 是 java.util 集合框架中实现 Map 接口的两个类。它们都提供了快速查找映射中键的操作，也提供了快速将对插入映射或从映射中移除对的操作。对于大量数据，两者在查找任务上都比将项目存储在 List 或数组中快得多。对于新手程序员，我们通常在创建新映射时使用 HashMap 作为默认选择，类似于选择 ArrayList 作为新 List 对象的默认选择。 HashMap 类在大多数情况下都很好用。
你会更倾向于使用 TreeMap 的一种情况是，当你希望按 排序顺序 遍历映射中的所有键时。例如，在字典中，你可能期望单词按字母顺序存储，在电话簿中，你可能期望名字按字母顺序存储。如果键有自然排序， TreeMap 类在遍历键时将使用此顺序，尽管这可能会略微影响映射的整体性能。 HashMap 不会以任何可预测的顺序保持键。
15.2.2. 使用 Map¶
让我们思考一个使用映射数据结构的简单示例。假设一名程序员正在为一家大公司开发一个免打扰名单（no-call list）应用程序。程序员希望存储姓名和电话号码对。我们可以用字符串表示两者，因此可以使用 Map<String, String> 来存储这些对。生成的映射将类似于电话簿，将姓名（键）与电话号码（值）关联成对。
public void testMap()
{
Map<String, String> noCallMap = new HashMap<String, String>();
}
15.3. 向映射中添加和访问对¶
现在，让我们向 noCallMap 添加一些值。要向映射中添加内容，我们将调用 put() 方法：
public void testMap()
{
Map<String, String> noCallMap = new HashMap<String, String>();
noCallMap.put("Roger M", "090−997−2918");
noCallMap.put("Jane Q", "999-777-1234");
}
put() 接受两个参数：首先是一个键，然后是一个关联值。上面对 put() 的两次调用创建了两个键值对，每个包含姓名和电话号码。
要访问这些对，我们使用 get() 方法：
public void testMap()
{
Map<String, String> noCallMap = new HashMap<String, String>();
noCallMap.put("Roger M", "090−997−2918");
noCallMap.put("Jane Q", "999-777-1234");
System.out.print("Jane Q's number is: " + noCallMap.get("Jane Q"));
}
当我们运行上面的代码时，将打印以下消息：
"Jane Q's number is: 999-777-1234"
15.4. 检查和移除映射中的对¶
如你在 get() 中看到的，在映射中访问值时，通常使用键来指定你想操作的对。事实上，有时人们会说使用键"索引到映射中"。"关联数组"这个别名来自于映射使用键作为其包含的对的唯一标识符，你可以将键视为映射中对的"位置"，就像数字位置用于引用 List 中的位置一样。
因此，在检查一个对是否存储在映射中，或从映射中移除该对时，使用键作为标识符是很自然的。映射提供了一个 remove() 方法，你指定一个键，具有该键的对将从映射中移除。映射还提供了一个 containsKey() 方法，它接受一个键值并返回一个布尔结果，指示映射中是否存在具有相应键的对。对于这两种操作，由于映射中的键必须是唯一的，我们真正只需要一个键。
public void testMap()
{
Map<String, String> noCallMap = new HashMap<String, String>();
noCallMap.put("Roger M", "090−997−2918");
noCallMap.put("Jane Q", "999-777-1234");
noCallMap.remove("Jane Q");
System.out.println(noCallMap.containsKey("Jane Q"));
}
这里，我们将"Jane Q"和她的电话号码添加到映射中，然后移除它，接着值 false 将被打印出来，因为我们的映射中不再有名为"Jane Q"的键。
15.5. 使用映射和 HashMap 的可视化总结¶
15.6. 遍历映射内容¶
如上所述，键是唯一的，映射提供了一个获取其包含的所有键的完整集合的方法。此方法名为 keySet() ，它返回一个键值的 Set——Set 接口将在接下来讨论。
由于 keySet() 方法返回映射中所有键的集合，它通常用于遍历整个映射：
public void testMap()
{
Map<String, String> noCallMap = new HashMap<String, String>();
noCallMap.put("Roger M", "090−997−2918");
noCallMap.put("Jane Q", "999-777-1234");
for (String name : noCallMap.keySet())
{
System.out.println("name: " + name
+ ", phone: " + noCallMap.get(name));
}
}
此方法将使用 for-each 循环遍历映射中所有键的集合，从而打印出映射的全部内容。这种在映射上编写 for-each 循环的方法是初学者入门的好选择。
更高级的程序员也可能使用 for-each 循环，但可能希望遍历映射中的所有 对 而不仅仅是键。这稍微复杂一些，因为映射中用于表示对的类型。 Map 接口提供了一个名为 Map.Entry 的嵌套类，表示映射中的一个 条目 或对。 Map 接口还提供了一个名为 entrySet() 的方法，类似于 keySet() ，但提供了映射中所有条目（对）的集合。你可以使用 entrySet() 编写更高级的循环，如下所示：
public void testMap()
{
Map<String, String> noCallMap = new HashMap<String, String>();
noCallMap.put("Roger M", "090−997−2918");
noCallMap.put("Jane Q", "999-777-1234");
for (Map.Entry<String, String> pair : noCallMap.entrySet())
{
System.out.println("name: " + pair.getKey(),
+ ", phone: " + pair.getValue());
}
}
使用 keySet() 编写循环通常更简单。然而，它需要调用 get() 来检索与每个键关联的值。使用 entrySet() 编写的循环稍微复杂一些，但由于它同时提供对键和值的访问而无需在映射中查找任何内容，因此当循环内同时需要键和值时，效率要高得多。
15.7. 集合接口¶
Set 接口的建模基于数学中教授的 集合论 原理。在数学中，集合是元素的集合——通常具有某些共同属性。集合是表示数学集合的集合。集合有三个重要属性：
同一个元素值在集合中只能出现一次。
遍历集合元素时出现的顺序通常与元素被添加的顺序不同。以不同顺序列出相同元素的两个集合被认为是同一个集合。
在计算机科学和 Java 中，建模集合的数据结构是为大型数据集设计的。此类数据结构有一种方法可以使用高效算法确定某个对象是否在给定集合中。对于大型数据集，使用此方法比遍历列表快得多。
15.7.1. 实现 Set 的类¶
TreeSet 和 HashSet 是集合框架中实现 Set 接口的两个类。它们都提供了检查元素是否在集合中的快速操作，还提供了将元素快速插入集合或从集合中移除元素的操作。对于大型集合——具有数千个以上元素的集合——存在大量插入、删除和元素存在性测试时，列表会慢得多。就像映射一样， TreeSet 保证按自然顺序遍历其值，而 HashSet 不维护任何顺序。
Set<E> 接口是 Collection<E> 的子类（就像 List<E> ），描述了所有集合提供的操作。以下是三个最重要的集合操作：
boolean add(E element); // add an element to the set
boolean contains(Object o); // does the set contain given object?
boolean remove(Object o); // remove given object from the set
15.7.2. 使用集合¶
让我们思考一个使用集合数据结构的简单示例。让我们回到免打扰名单的示例。假设一名程序员正在为一家大公司开发一个免打扰名单应用程序。程序员决定使用 TreeSet 数据结构来存储一系列 PhoneRecord 对象。
PhoneRecord 类如下所示：
public class PhoneRecord
{
public String name;
public String phoneNumber;
public PhoneRecord(String initName, String initNumber)
{
this.name = initName;
this.phoneNumber = initNumber;
}
}
TreeSet 似乎是此问题的合适结构，因为数据的主要用途是测试记录是否在集合中。
程序员首先需要创建一个 Set 变量来包含我们的 PhoneRecord 对象：
public void testSet()
{
Set<PhoneRecord> noCall = new TreeSet<PhoneRecord>();
}
15.8. 向集合中添加值¶
现在，让我们向 Set 添加一些记录：
public void testSet()
{
Set<PhoneRecord> noCall = new TreeSet<PhoneRecord>();
// making PhoneRecord and adding to set
PhoneRecord roger = new PhoneRecord("Roger M", "090−997−2918");
noCall.add(roger);
}
在上面的代码中，我们创建了一个名为 roger 的 PhoneRecord 对象，然后将其添加到集合中。我们也可以直接将对象添加到集合中，而不使用单独的变量：
noCall.add(new PhoneRecord("Stacy K", "090−997−9188"));
重要的是，多次将同一对象添加到集合中不会在代码中导致任何错误。只有第一次调用会实际将对象添加到集合中。
public void testSet()
{
Set<PhoneRecord> noCall = new TreeSet<PhoneRecord>();
PhoneRecord roger = new PhoneRecord("Roger M", "090−997−2918");
noCall.add(roger);
// Running a second time won't do anything
// but also won't cause errors:
noCall.add(roger);
}
就像列表一样，你必须确保添加的项目与尖括号（ <> ）中的类型相同。例如，我们不能简单地将数字 1 添加到集合 noCall 中。
15.9. 检查集合中的值¶
集合的第二个重要方法是 contains() 。此方法接受一个值，如果值在集合中则返回 true ，否则返回 false 。
public void testSet()
{
Set<PhoneRecord> noCall = new TreeSet<PhoneRecord>();
PhoneRecord roger = new PhoneRecord("Roger M", "090−997−2918");
noCall.add(roger);
boolean inside = noCall.contains(roger);
System.out.println("It is " + inside + " that Roger is in the set");
}
如果运行上面的代码，将输出以下消息：
"It is true that Roger is in the set"
但是，如果我们创建了另一个 PhoneRecord 对象但 没有 将其添加到集合中……
public void testSet()
{
Set<PhoneRecord> noCall = new TreeSet<PhoneRecord>();
PhoneRecord jane = new PhoneRecord("Jane Q", "999-777-1234");
boolean inside = noCall.contains(jane);
System.out.println("It is " + inside + " that Jane is in the set");
}
此方法将输出以下消息：
"It is false that Jane is in the set
15.10. 从集合中移除值¶
集合上最后一个重要的方法是 remove() ，它从集合中移除某个元素。
public void testSet()
{
Set<PhoneRecord> noCall = new TreeSet<PhoneRecord>();
PhoneRecord roger = new PhoneRecord("Roger M", "090−997−2918");
noCall.add(roger);
boolean inside = noCall.contains(roger);
System.out.println("It is " + inside + " that Roger is in the set");
noCall.remove(roger);
inside = noCall.contains(roger);
System.out.println("It is " + inside + " that Roger is in the set");
}
从上面可以看到，我们将名为 roger 的 PhoneRecord 添加到 noCall 中。然后打印出：
"It is true that Roger is in the set"
然后我们从集合中移除 roger 并打印出：
"It is false that Roger is in the set"
15.11. 遍历集合¶
使用 for-each 循环遍历集合是最简单的方式，它与使用 for-each 循环遍历列表几乎相同。
public void testMap()
{
Set<PhoneRecord> noCall = new TreeSet<PhoneRecord>();
// insert records into the set
for (PhoneRecord record : noCall)
{
System.out.println("name: " + record.getName()
+ ", phone: " + record.getPhoneNumber());
}
}
此方法将使用 for-each 循环遍历集合中所有元素，从而打印出集合的全部内容。
