021 集合和映射表

本文为《Java 语言程序设计》第十版 章节笔记

21.1 引言

• 集合（set） 是一个用于存储和处理无重复元素的高效数据结构。
• 映射表（map） 类似于目录，提供了使用键值快速查询和获取值的功能。

21.2 集合（set）

Set 接口拓展了 Collection 接口，但它没有引入新的方法和常量，只是规定 Set 的实例不包含重复元素（多次添加也只有一个被存储）。

可以使用集合的三个具体类 HashSet（散列类）、LinedHashSet（链式散列集）、TreeSet（树形集） 来创建集合。

一个集合的散列码是这个集合中所有元素散列码的和。

21.2.1 HashSet

HashSet 类可以用来存储互不相同的任何元素。默认情况下，初始容量为 16 而负载系数是 0.75（16 * 0.75 = 12）。

散列集中的元素没有特定的顺序，不会按照它们被插入集合时的顺序存储。要强加一个顺序，就需要使用 LinkedHashSet 类。

21.2.2 LinkedHashSet

LinkedHashSet 用一个链表实现来拓展 HashSet 类，它支持对集合内的元素排序，它可以按照它们的插入顺序地顺序提取。

要强加一个不同的顺序（例如，升序或降序），可是使用 TreeSet 类。

21.2.3 TreeSet

SortedSet 是 Set 的一个子接口，NavigableSet 拓展了 SortedSet，TreeSet 实现了 SortedSet 接口。

SortedSet 是 Set 的子接口，它可以确保集合中的元素是有序的。它的方法：

• first（）返回集合中的第一个元素
• last（） 返回集合中的最后一个元素
• headSet(toElement) 返回集合中元素小于 toElement 的那部分
• trilSet(fromElement) 返回集合中大于或等于 fromElement 的那一部分。

NavigableSet 提供方法：

• lower(e)：返回小于一个给定元素的元素
• floor(e)：返回小于等于一个给定元素的元素
• ceiling(e)：返回大于或等于一个给定元素的元素
• higher(e)：返回大于一个给定元素的元素
• pollFirst()：删除第一个元素
• pollLast()：删除最后一个元素

21.3 比较集合和线性表的性能

• 在无重复元素进行排序方面，集合比线性表更加高效。
• 在通过索引来访问元素方面，线性表非常有用。

线性表中的元素可以通过索引来访问。而集合不支持索引，因为集合中的元素是 无序的。要遍历集合中的所有元素，使用 foreach 循环。

21.5 映射表

映射表（map）是一个依照键/值对储存元素的容器。它提供了通过键快速获取、删除和更新键/值对的功能。

可以使用三个具体的类来创建一个映射表：HashMap（散列映射表）、LinkedHashMap（链式散列映射表）、TreeMap（树形映射表）。

键很像下标，在 List 中，下标是整数，而在 Map 中，键可以是任意类型的对象。映射表中不能有重复地键，每个键对应一个值。

<<interface>> java.util.Map<K,V>
//更新
+clear(): void
+put(key: K, value: V): V
+putAll(m: Map<? extends K, ? extends V>): void
+remove(key: Object): V

//查询
+contaionsKey(key: Object): boolean
+containsValue(value: Object):  boolean
+isEmpty(): boolean
+size(): int

//获取键集合、获取值集合
+keySet(): Set<K>
+value(): Collection<V>

+entrySet(): Set<Map.Entry<K,V>>
+get(key: Object): V

Entry 是 Map 接口的一个内部接口

<<interface>> java.util.Map.Entry<K, V>
+getKey(): K
+getValue(): V
+setValue(value: V): void

对于定位一个值、插入一个条目以及删除一个条目而言，HashMap 类是高效的。

HashMap 类中的条目是没有顺序的。

LinkedHashMap 类用链表实现来拓展 HashMap 类，它支持映射表中条目的排序。

在 LinedHashMap 中，元素既可以按照它们插入映射表的顺序排序（插入排序（insertion order）），也可以按照它们被最后一次访问时的顺序排序，从最早到最晚（访问顺序（access order））。

TreeMap 类在历遍排好顺序的键时很有效。

SortedMap 是 Map 的一个子接口，使用它可确保映射表中的条目是排好序的。它的一些方法：

• firstKey()：返回映射表中的第一个键
• lastKey()：返回映射表中的最后一个键
• headMap(toKey)：返回键小于 toKey 的那部分映射表
• tailMap(fromKey)：返回键冬雨或等于 fromKey 的那部分映射表

NavigableMap 继承了 SortedMap，提供以下方法：

• lowerKey(key)
• floorKey(key)
• ceilingKey(key)
• higherKey(key)
• pollFirstEntry()
• pollLastEntry()

在 Java 2 以前，一般使用 java.util.Hashtable 来映射键和值。为了适应 Java 合集框架，Java 对 Hashtable 进行了重新设计，但是，为了向后兼容保留了所有的方法。Hashtable 实现了 Map 接口，除了 Hashtable 的更新方法时同步的外，它与 HashMap 的用法是一样的。

END