新集合类型

Guava引入了很多JDK没有的、但我们发现非常有用的新集合类型。这些新类型是为了和JDK集合框架共存,而没有往JDK集合抽象中硬塞其他概念。作为一般规则,Guava集合非常精准地遵循了JDK接口契约。

Multiset

统计一个词在文档中出现了多少次,传统的做法是这样的:

Map<String, Integer> counts = new HashMap<String, Integer>();
for (String word : words) {
    Integer count = counts.get(word);
    if (count == null) {
        counts.put(word, 1);
    } else {
        counts.put(word, count + 1);
    }
}

这种写法很笨,也容易出错,并且不支持同时收集多种统计信息,如总词数。我们可以做的更好。

Guava提供了一个新集合类型Multiset,它可以多次添加相等的元素。维基百科从数学角度这样定义 Multiset:”集合[set]概念的延伸,它的元素可以重复出现…与集合[set]相同而与元组[tuple]相反的是,Multiset元素的顺序是无关紧要的:Multiset{a, a, b}和{a, b, a}是相等的”。——译者注:这里所说的集合[set]是数学上的概念,Multiset继承自JDK中的Collection接口,而不是Set接口,所以包含重复元素并没有违反原有的接口契约。

可以用两种方式看待 Multiset:

  • 没有元素顺序限制的 ArrayList
  • Map<E, Integer>,键为元素,值为计数

Guava的Multiset API也结合考虑了这两种方式:
当把Multiset看成普通的Collection时,它表现得就像无序的ArrayList:

  • add(E) 添加单个元素
  • iterator() 返回一个迭代器,包含Multiset的所有元素(包括重复的元素)
  • size() 返回元素的总个数(包括重复的元素)

当把Multiset看作Map<E, Integer>时,它还提供了符合性能期望的查询操作:

  • count(Object) 返回给定元素的计数。HashMultiset.count的复杂度为O(1),TreeMultiset.count的复杂度为O(log n)。
  • entrySet() 返回Set<Multiset.Entry>,和Map的entrySet类似。
  • elementSet() 返回所有不重复元素的Set,和Map的keySet()类似。
  • 所有Multiset实现的内存消耗随着不重复元素的个数线性增长。

值得注意的是,除了极少数情况,Multiset和JDK中原有的Collection接口契约完全一致,具体来说,TreeMultiset在判断元素是否相等时,与 TreeSet一样用compare,而不是Object.equals。另外特别注意,Multiset.addAll(Collection)可以添加Collection中的所有元素并进行计数,这比用for循环往Map添加元素和计数方便多了。

  • count(E)
    给定元素在Multiset中的计数
  • elementSet()
    Multiset中不重复元素的集合,类型为Set
  • entrySet()
    和Map的entrySet类似,返回Set<Multiset.Entry>,其中包含的Entry支持getElement()和getCount()方法
  • add(E, int)
    增加给定元素在Multiset中的计数
  • remove(E, int)
    减少给定元素在Multiset中的计数
  • setCount(E, int)
    设置给定元素在Multiset中的计数,不可以为负数
  • size()
    返回集合元素的总个数(包括重复的元素)

Multiset不是Map

请注意,Multiset不是 Map<E, Integer>,虽然Map可能是某些Multiset实现的一部分。准确来说Multiset是一种Collection类型,并履行了 Collection接口相关的契约。关于Multiset和Map的显著区别还包括:

  • Multiset 中的元素计数只能是正数。任何元素的计数都不能为负,也不能是 0。elementSet()和 entrySet()视图中也不会有这样的元素。
  • multiset.size()返回集合的大小,等同于所有元素计数的总和。对于不重复元素的个数,应使用elementSet().size()方法。(add(E)把 multiset.size()增加1)
  • multiset.iterator()会迭代重复元素,因此迭代长度等于multiset.size()。
  • Multiset 支持直接增加、减少或设置元素的计数。setCount(elem, 0)等同于移除所有element。
  • 对multiset中没有的元素,multiset.count(elem)始终返回0。

Multiset实现

Guava 提供了多种 Multiset 的实现,大致对应 JDK 中 Map 的各种实现:

Map对应的Multiset是否支持null元素
HashMapHashMultiset
TreeMapTreeMultiset是(如果 comparator 支持的话)
LinkedHashMapLinkedHashMultiset
ConcurrentHashMapConcurrentHashMultiset
ImmutableMapImmutableMultiset

SortedMultiset

SortedMultiset是Multiset接口的变种,它支持高效地获取指定范围的子集。比方说,你可以用latencies.subMultiset(0,BoundType.CLOSED, 100, BoundType.OPEN).size()来统计你的站点中延迟在 100 毫秒以内的访问,然后把这个值和latencies.size()相比,以获取这个延迟水平在总体访问中的比例。

TreeMultiset实现SortedMultiset接口。在撰写本文档时,ImmutableSortedMultiset还在测试和GWT的兼容性。

Multimap

每个有经验的Java程序员都在某处实现过Map<K, List>或Map<K, Set>,并且要忍受这个结构的笨拙。例如,Map<K, Set>通常用来表示非标定有向图。Guava的Multimap可以很容易地把一个键映射到多个值。换句话说,Multimap是把键映射到任意多个值的一般方式。

可以用两种方式思考 Multimap 的概念:”键-单个值映射”的集合:

a->1
a->2
a->4
b->3
c->5

或者”键-值集合映射”的映射:

a->[1, 2, 4]
b->3
c->5

一般来说,Multimap接口应该用第一种方式看待,但asMap()视图返回Map<K, Collection>,让你可以按另一种方式看待Multimap。重要的是,不会有任何键映射到空集合:一个键要么至少到一个值,要么根本就不在Multimap中。

很少会直接使用Multimap接口,更多时候你会用ListMultimap或SetMultimap接口,它们分别把键映射到List或Set。

构建

最直接的方法创建Multimap是使用MultimapBuilder,它允许你配置想要的keys和values。例如:

// creates a ListMultimap with tree keys and array list values
ListMultimap<String, Integer> treeListMultimap =
    MultimapBuilder.treeKeys().arrayListValues().build();

// creates a SetMultimap with hash keys and enum set values
SetMultimap<Integer, MyEnum> hashEnumMultimap =
    MultimapBuilder.hashKeys().enumSetValues(MyEnum.class).build();

您也可以选择直接在实现类上使用create()方法,但这并不鼓励,建议使用MultimapBuilder。

修改Multimap

Multimap.get(key)以集合形式返回键所对应的值视图,即使没有任何对应的值,也会返回空集合。ListMultimap.get(key)返回 List,SetMultimap.get(key)返回Set。

对值视图集合进行的修改最终都会反映到底层的Multimap。例如:

Set<Person> aliceChildren = childrenMultimap.get(alice);
aliceChildren.clear();
aliceChildren.add(bob);
aliceChildren.add(carol);

其他(更直接地)修改 Multimap 的方法有:

方法签名描述等价于
put(K, V)添加键到单个值的映射multimap.get(key).add(value)
putAll(K, Iterable)依次添加键到多个值的映射Iterables.addAll(multimap.get(key), values)
remove(K, V)移除键到值的映射;如果有这样的键值并成功移除,返回 true。multimap.get(key).remove(value)
removeAll(K)清除键对应的所有值,返回的集合包含所有之前映射到 K 的值,但修改这个集合就不会影响 Multimap 了。multimap.get(key).clear()
replaceValues(K, Iterable)清除键对应的所有值,并重新把 key 关联到 Iterable 中的每个元素。返回的集合包含所有之前映射到 K 的值。multimap.get(key).clear(); Iterables.addAll(multimap.get(key), values)

Multimap的视图

Multimap还支持若干强大的视图:

  • asMap为 Multimap<K, V>提供Map<K,Collection>形式的视图。返回的Map支持remove操作,并且会反映到底层的Multimap,但它不支持put或putAll操作。更重要的是,如果你想为Multimap中没有的键返回null,而不是一个新的、可写的空集合,你就可以使用asMap().get(key)。(你可以并且应当把 asMap.get(key)返回的结果转化为适当的集合类型——如SetMultimap.asMap.get(key)的结果转为Set,ListMultimap.asMap.get(key)的结果转为List——Java类型系统不允许ListMultimap直接为asMap.get(key)返回List——译者注:也可以用Multimaps中的asMap静态方法帮你完成类型转换)
  • entries用 Collection<Map.Entry<K, V>>返回Multimap中所有”键-单个值映射”——包括重复键。(对SetMultimap,返回的是Set)
  • keySet用 Set 表示Multimap中所有不同的键。
  • keys用 Multiset表示Multimap中的所有键,每个键重复出现的次数等于它映射的值的个数。可以从这个Multiset中移除元素,但不能做添加操作;移除操作会反映到底层的Multimap。
  • values()用一个”扁平”的Collection包含Multimap中的所有值。这有一点类似于Iterables.concat(multimap.asMap().values()),但它直接返回了单个Collection,而不像 multimap.asMap().values()那样是按键区分开的 Collection。

Multimap不是Map

Multimap<K, V>不是Map<K,Collection>,虽然某些Multimap实现中可能使用了map。它们之间的显著区别包括:

  • Multimap.get(key)总是返回非null、但是可能空的集合。这并不意味着Multimap为相应的键花费内存创建了集合,而只是提供一个集合视图方便你为键增加映射值——译者注:如果有这样的键,返回的集合只是包装了Multimap中已有的集合;如果没有这样的键,返回的空集合也只是持有Multimap 引用的栈对象,让你可以用来操作底层的Multimap。因此,返回的集合不会占据太多内存,数据实际上还是存放在Multimap中。
  • 如果你更喜欢像Map那样,为Multimap中没有的键返回 null,请使用 asMap()视图获取一个Map<K, Collection>。(或者用静态方法 Multimaps.asMap()为 ListMultimap 返回一个 Map<K, List>。对于SetMultimap和SortedSetMultimap,也有类似的静态方法存在)
  • 当且仅当有值映射到键时,Multimap.containsKey(key)才会返回true。尤其需要注意的是,如果键k之前映射过一个或多个值,但它们都被移除后,Multimap.containsKey(key)会返回false。
  • Multimap.entries()返回 Multimap 中所有”键-单个值映射”——包括重复键。如果你想要得到所有”键-值集合映射”,请使用asMap().entrySet()。
  • Multimap.size()返回所有”键-单个值映射”的个数,而非不同键的个数。要得到不同键的个数,请改用Multimap.keySet().size()。

Multimap的各种实现

Multimap提供了多种形式的实现。在大多数要使用Map<K, Collection>的地方,你都可以使用它们:

实现键行为类似值行为类似
ArrayListMultimapHashMapArrayList
HashMultimapHashMapHashSet
LinkedListMultimap*LinkedHashMap*LinkedList*
LinkedHashMultimap**LinkedHashMapLinkedHashMap
TreeMultimapTreeMapTreeSet
ImmutableListMultimapImmutableMapImmutableList
ImmutableSetMultimapImmutableMapImmutableSet

除了两个不可变形式的实现,其他所有实现都支持null键和null值

*LinkedListMultimap.entries()保留了所有键和值的迭代顺序。详情见doc链接。

**LinkedHashMultimap 保留了映射项的插入顺序,包括键插入的顺序,以及键映射的所有值的插入顺序。

请注意,并非所有的 Multimap 都和上面列出的一样,使用 Map<K, Collection>来实现(特别是,一些Multimap实现用了自定义的hashTable,以最小化开销)

如果你想要更大的定制化,请用 Multimaps.newMultimap(Map, Supplier)或list和set版本,使用自定义的Collection、List 或Set实现Multimap。

BiMap

传统上,实现键值对的双向映射需要维护两个单独的map,并保持它们间的同步。但这种方式很容易出错,而且对于值已经在map中的情况,会变得非常混乱。例如:

Map<String, Integer> nameToId = Maps.newHashMap();
Map<Integer, String> idToName = Maps.newHashMap();

nameToId.put("Bob", 42);
idToName.put(42, "Bob");
// what happens if "Bob" or 42 are already present?
// weird bugs can arise if we forget to keep these in sync...

BiMap<K, V>是特殊的Map<K, V>:

  • 可以用inverse()反转BiMap<K, V>的键值映射
  • 保证值是唯一的,因此values()返回 Set 而不是普通的Collection

在BiMap中,如果你想把键映射到已经存在的值,会抛出IllegalArgumentException异常。如果对特定值,你想要强制替换它的键,请使用BiMap.forcePut(key, value)。

BiMap<String, Integer> userId = HashBiMap.create();
...

String userForId = userId.inverse().get(id);

BiMap的各种实现

键–值实现值–键实现对应的BiMap实现
HashMapHashMapHashBiMap
ImmutableMapImmutableMapImmutableBiMap
EnumMapEnumMapEnumBiMap
EnumMapHashMapEnumHashBiMap
注:Maps 类中还有一些诸如 synchronizedBiMap 的 BiMap 工具方法.

Table

Table<Vertex, Vertex, Double> weightedGraph = HashBasedTable.create();
weightedGraph.put(v1, v2, 4);
weightedGraph.put(v1, v3, 20);
weightedGraph.put(v2, v3, 5);

weightedGraph.row(v1); // returns a Map mapping v2 to 4, v3 to 20
weightedGraph.column(v3); // returns a Map mapping v1 to 20, v2 to 5

通常来说,当你想使用多个键做索引的时候,你可能会用类似Map<FirstName, Map<LastName, Person>>的实现,这种方式很丑陋,使用上也不友好Guava为此提供了新集合类型Table,它有两个支持所有类型的键:”行”和”列”。Table提供多种视图,以便你从各种角度使用它:

  • rowMap():用Map<R, Map<C, V>>表现Table<R, C, V>。同样的,rowKeySet()返回”行”的集合Set。
  • row(r):用Map<C, V>返回给定”行”的所有列,对这个map进行的写操作也将写入Table中。
  • 类似的列访问方法:columnMap()columnKeySet()column(c)。(基于列的访问会比基于的行访问稍微低效点)
  • cellSet():用元素类型为Table.Cell<R, C, V>的Set表现 Table<R, C, V>。Cell 类似于Map.Entry,但它是用行和列两个键区分的。

Table有如下几种实现:

  • HashBasedTable:本质上用HashMap<R, HashMap<C, V>>实现;
  • TreeBasedTable:本质上用TreeMap<R, TreeMap<C,V>>实现;
  • ImmutableTable:本质上用ImmutableMap<R, ImmutableMap<C, V>>实现;注:ImmutableTable对稀疏或密集的数据集都有优化。
  • ArrayTable:要求在构造时就指定行和列的大小,本质上由一个二维数组实现,以提升访问速度和密集 Table 的内存利用率。ArrayTable与其他Table的工作原理有点不同,请参见Javadoc了解详情。

ClassToInstanceMap

ClassToInstanceMap 是一种特殊的Map:它的键是类型,而值是符合键所指类型的对象。

为了扩展 Map 接口,ClassToInstanceMap额外声明了两个方法:T getInstance(Class) 和 T putInstance(Class, T),从而避免强制类型转换,同时保证了类型安全。

ClassToInstanceMap有唯一的泛型参数,通常称为 B,代表Map支持的所有类型的上界。例如:

ClassToInstanceMap<Number> numberDefaults = MutableClassToInstanceMap.create();
numberDefaults.putInstance(Integer.class, Integer.valueOf(0));

从技术上讲,从技术上讲,ClassToInstanceMap<B> 实现了 Map<Class<? extends B>, B>——或者换句话说,是一个映射 B 的子类型到对应实例的 Map。这让 ClassToInstanceMap 包含的泛型声明有点令人困惑,但请记住 B 始终是 Map 所支持类型的上界——通常 B 就是 Object。

对于 ClassToInstanceMap,Guava 提供了两种有用的实现:MutableClassToInstanceMap 和 ImmutableClassToInstanceMap。

RangeSet

RangeSet描述了一组不相连的、非空的区间。当把一个区间添加到可变的RangeSet时,所有相连的区间会被合并,空区间会被忽略。例如:

RangeSet<Integer> rangeSet = TreeRangeSet.create();
rangeSet.add(Range.closed(1, 10)); // {[1, 10]}
rangeSet.add(Range.closedOpen(11, 15)); // disconnected range: {[1, 10], [11, 15)}
rangeSet.add(Range.closedOpen(15, 20)); // connected range; {[1, 10], [11, 20)}
rangeSet.add(Range.openClosed(0, 0)); // empty range; {[1, 10], [11, 20)}
rangeSet.remove(Range.open(5, 10)); // splits [1, 10]; {[1, 5], [10, 10], [11, 20)}

请注意,要合并Range.closed(1, 10)和Range.closedOpen(11, 15)这样的区间,你需要首先用Range.canonical(DiscreteDomain)对区间进行预处理,例如DiscreteDomain.integers()。

注:RangeSet不支持GWT,也不支持JDK5和更早版本;因为,RangeSet需要充分利用JDK6中NavigableMap的特性。

RangeSet的视图

RangeSet的实现支持非常广泛的视图:

  • complement():返回RangeSet的补集视图。complement也是RangeSet类型,包含了不相连的、非空的区间。
  • subRangeSet(Range):返回RangeSet与给定Range的交集视图。这扩展了传统排序集合中的headSet、subSet 和 tailSet 操作。
  • asRanges():用Set表现RangeSet,这样可以遍历其中的Range。
  • asSet(DiscreteDomain)(仅ImmutableRangeSet支持):用ImmutableSortedSet表现RangeSet,以区间中所有元素的形式而不是区间本身的形式查看。(这个操作不支持DiscreteDomain和RangeSet都没有上边界,或都没有下边界的情况)

RangeSet的查询方法

为了方便操作,RangeSet直接提供了若干查询方法,其中最突出的有:

  • contains(C):RangeSet 最基本的操作,判断RangeSet中是否有任何区间包含给定元素。
  • rangeContaining(C):返回包含给定元素的区间;若没有这样的区间,则返回null。
  • encloses(Range):简单明了,判断RangeSet中是否有任何区间包括给定区间。
  • span():返回包括RangeSet中所有区间的最小区间。

RangeMap

RangeMap 描述了”不相交的、非空的区间”到特定值的映射。和 RangeSet 不同,RangeMap 不会合并相邻的映射,即便相邻的区间映射到相同的值。例如:

RangeMap<Integer, String> rangeMap = TreeRangeMap.create();
rangeMap.put(Range.closed(1, 10), "foo"); // {[1, 10] => "foo"}
rangeMap.put(Range.open(3, 6), "bar"); // {[1, 3] => "foo", (3, 6) => "bar", [6, 10] => "foo"}
rangeMap.put(Range.open(10, 20), "foo"); // {[1, 3] => "foo", (3, 6) => "bar", [6, 10] => "foo", (10, 20) => "foo"}
rangeMap.remove(Range.closed(5, 11)); // {[1, 3] => "foo", (3, 5) => "bar", (11, 20) => "foo"}

RangeMap 的视图

RangeMap 提供两个视图:

  • asMapOfRanges():用Map<Range, V>表现RangeMap。这可以用来遍历RangeMap。
  • subRangeMap(Range):用RangeMap 类型返回RangeMap 与给定Range的交集视图。这扩展了传统的headMap、subMap和tailMap操作。

【腾讯云】境外1核2G服务器低至2折,半价续费券限量免费领取!
https://cloud.tencent.com/act/cps/redirect?redirect=1068&cps_key=e4b50f6c64a4480367f8a8d16fd07c5a&from=console

标签: Guava, Multiset, Multimap, BiMap

添加新评论