1 /*
2 * Copyright (C) 2007 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import com.google.common.annotations.GwtCompatible;
20 import com.google.common.annotations.GwtIncompatible;
21 import com.google.common.annotations.VisibleForTesting;
22 import com.google.common.base.Preconditions;
23 import java.io.IOException;
24 import java.io.ObjectInputStream;
25 import java.io.ObjectOutputStream;
26 import java.util.Collection;
27 import java.util.Map;
28 import java.util.Set;
29
30 /**
31 * Implementation of {@link Multimap} using hash tables.
32 *
33 * <p>The multimap does not store duplicate key-value pairs. Adding a new key-value pair equal to an
34 * existing key-value pair has no effect.
35 *
36 * <p>Keys and values may be null. All optional multimap methods are supported, and all returned
37 * views are modifiable.
38 *
39 * <p>This class is not threadsafe when any concurrent operations update the multimap. Concurrent
40 * read operations will work correctly if the last write <i>happens-before</i> any reads. To allow
41 * concurrent update operations, wrap your multimap with a call to {@link
42 * Multimaps#synchronizedSetMultimap}.
43 *
44 * <p><b>Warning:</b> Do not modify either a key <i>or a value</i> of a {@code HashMultimap} in a
45 * way that affects its {@link Object#equals} behavior. Undefined behavior and bugs will result.
46 *
47 * @author Jared Levy
48 * @since 2.0
49 */
50 @GwtCompatible(serializable = true, emulated = true)
51 public final class HashMultimap<K, V> extends HashMultimapGwtSerializationDependencies<K, V> {
52 private static final int DEFAULT_VALUES_PER_KEY = 2;
53
54 @VisibleForTesting transient int expectedValuesPerKey = DEFAULT_VALUES_PER_KEY;
55
56 /**
57 * Creates a new, empty {@code HashMultimap} with the default initial capacities.
58 *
59 * <p>This method will soon be deprecated in favor of {@code
60 * MultimapBuilder.hashKeys().hashSetValues().build()}.
61 */
62 public static <K, V> HashMultimap<K, V> create() {
63 return new HashMultimap<>();
64 }
65
66 /**
67 * Constructs an empty {@code HashMultimap} with enough capacity to hold the specified numbers of
68 * keys and values without rehashing.
69 *
70 * <p>This method will soon be deprecated in favor of {@code
71 * MultimapBuilder.hashKeys(expectedKeys).hashSetValues(expectedValuesPerKey).build()}.
72 *
73 * @param expectedKeys the expected number of distinct keys
74 * @param expectedValuesPerKey the expected average number of values per key
75 * @throws IllegalArgumentException if {@code expectedKeys} or {@code expectedValuesPerKey} is
76 * negative
77 */
78 public static <K, V> HashMultimap<K, V> create(int expectedKeys, int expectedValuesPerKey) {
79 return new HashMultimap<>(expectedKeys, expectedValuesPerKey);
80 }
81
82 /**
83 * Constructs a {@code HashMultimap} with the same mappings as the specified multimap. If a
84 * key-value mapping appears multiple times in the input multimap, it only appears once in the
85 * constructed multimap.
86 *
87 * <p>This method will soon be deprecated in favor of {@code
88 * MultimapBuilder.hashKeys().hashSetValues().build(multimap)}.
89 *
90 * @param multimap the multimap whose contents are copied to this multimap
91 */
92 public static <K, V> HashMultimap<K, V> create(Multimap<? extends K, ? extends V> multimap) {
93 return new HashMultimap<>(multimap);
94 }
95
96 private HashMultimap() {
97 this(12, DEFAULT_VALUES_PER_KEY);
98 }
99
100 private HashMultimap(int expectedKeys, int expectedValuesPerKey) {
101 super(Platform.<K, Collection<V>>newHashMapWithExpectedSize(expectedKeys));
102 Preconditions.checkArgument(expectedValuesPerKey >= 0);
103 this.expectedValuesPerKey = expectedValuesPerKey;
104 }
105
106 private HashMultimap(Multimap<? extends K, ? extends V> multimap) {
107 super(Platform.<K, Collection<V>>newHashMapWithExpectedSize(multimap.keySet().size()));
108 putAll(multimap);
109 }
110
111 /**
112 * {@inheritDoc}
113 *
114 * <p>Creates an empty {@code HashSet} for a collection of values for one key.
115 *
116 * @return a new {@code HashSet} containing a collection of values for one key
117 */
118 @Override
119 Set<V> createCollection() {
120 return Platform.<V>newHashSetWithExpectedSize(expectedValuesPerKey);
121 }
122
123 /**
124 * @serialData expectedValuesPerKey, number of distinct keys, and then for each distinct key: the
125 * key, number of values for that key, and the key's values
126 */
127 @GwtIncompatible // java.io.ObjectOutputStream
128 private void writeObject(ObjectOutputStream stream) throws IOException {
129 stream.defaultWriteObject();
130 Serialization.writeMultimap(this, stream);
131 }
132
133 @GwtIncompatible // java.io.ObjectInputStream
134 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
135 stream.defaultReadObject();
136 expectedValuesPerKey = DEFAULT_VALUES_PER_KEY;
137 int distinctKeys = Serialization.readCount(stream);
138 Map<K, Collection<V>> map = Platform.newHashMapWithExpectedSize(12);
139 setMap(map);
140 Serialization.populateMultimap(this, stream, distinctKeys);
141 }
142
143 @GwtIncompatible // Not needed in emulated source
144 private static final long serialVersionUID = 0;
145 }