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 24 import java.io.IOException; 25 import java.io.ObjectInputStream; 26 import java.io.ObjectOutputStream; 27 import java.util.Collection; 28 import java.util.HashMap; 29 import java.util.Map; 30 import java.util.Set; 31 32 /** 33 * Implementation of {@link Multimap} using hash tables. 34 * 35 * <p>The multimap does not store duplicate key-value pairs. Adding a new 36 * key-value pair equal to an existing key-value pair has no effect. 37 * 38 * <p>Keys and values may be null. All optional multimap methods are supported, 39 * and all returned views are modifiable. 40 * 41 * <p>This class is not threadsafe when any concurrent operations update the 42 * multimap. Concurrent read operations will work correctly. To allow concurrent 43 * update operations, wrap your multimap with a call to {@link 44 * Multimaps#synchronizedSetMultimap}. 45 * 46 * @author Jared Levy 47 * @since 2.0 (imported from Google Collections Library) 48 */ 49 @GwtCompatible(serializable = true, emulated = true) 50 public final class HashMultimap<K, V> extends AbstractSetMultimap<K, V> { 51 private static final int DEFAULT_VALUES_PER_KEY = 2; 52 53 @VisibleForTesting 54 transient int expectedValuesPerKey = DEFAULT_VALUES_PER_KEY; 55 56 /** 57 * Creates a new, empty {@code HashMultimap} with the default initial 58 * capacities. 59 */ create()60 public static <K, V> HashMultimap<K, V> create() { 61 return new HashMultimap<K, V>(); 62 } 63 64 /** 65 * Constructs an empty {@code HashMultimap} with enough capacity to hold the 66 * specified numbers of keys and values without rehashing. 67 * 68 * @param expectedKeys the expected number of distinct keys 69 * @param expectedValuesPerKey the expected average number of values per key 70 * @throws IllegalArgumentException if {@code expectedKeys} or {@code 71 * expectedValuesPerKey} is negative 72 */ create( int expectedKeys, int expectedValuesPerKey)73 public static <K, V> HashMultimap<K, V> create( 74 int expectedKeys, int expectedValuesPerKey) { 75 return new HashMultimap<K, V>(expectedKeys, expectedValuesPerKey); 76 } 77 78 /** 79 * Constructs a {@code HashMultimap} with the same mappings as the specified 80 * multimap. If a key-value mapping appears multiple times in the input 81 * multimap, it only appears once in the constructed multimap. 82 * 83 * @param multimap the multimap whose contents are copied to this multimap 84 */ create( Multimap<? extends K, ? extends V> multimap)85 public static <K, V> HashMultimap<K, V> create( 86 Multimap<? extends K, ? extends V> multimap) { 87 return new HashMultimap<K, V>(multimap); 88 } 89 HashMultimap()90 private HashMultimap() { 91 super(new HashMap<K, Collection<V>>()); 92 } 93 HashMultimap(int expectedKeys, int expectedValuesPerKey)94 private HashMultimap(int expectedKeys, int expectedValuesPerKey) { 95 super(Maps.<K, Collection<V>>newHashMapWithExpectedSize(expectedKeys)); 96 Preconditions.checkArgument(expectedValuesPerKey >= 0); 97 this.expectedValuesPerKey = expectedValuesPerKey; 98 } 99 HashMultimap(Multimap<? extends K, ? extends V> multimap)100 private HashMultimap(Multimap<? extends K, ? extends V> multimap) { 101 super(Maps.<K, Collection<V>>newHashMapWithExpectedSize( 102 multimap.keySet().size())); 103 putAll(multimap); 104 } 105 106 /** 107 * {@inheritDoc} 108 * 109 * <p>Creates an empty {@code HashSet} for a collection of values for one key. 110 * 111 * @return a new {@code HashSet} containing a collection of values for one key 112 */ createCollection()113 @Override Set<V> createCollection() { 114 return Sets.<V>newHashSetWithExpectedSize(expectedValuesPerKey); 115 } 116 117 /** 118 * @serialData expectedValuesPerKey, number of distinct keys, and then for 119 * each distinct key: the key, number of values for that key, and the 120 * key's values 121 */ 122 @GwtIncompatible("java.io.ObjectOutputStream") writeObject(ObjectOutputStream stream)123 private void writeObject(ObjectOutputStream stream) throws IOException { 124 stream.defaultWriteObject(); 125 stream.writeInt(expectedValuesPerKey); 126 Serialization.writeMultimap(this, stream); 127 } 128 129 @GwtIncompatible("java.io.ObjectInputStream") readObject(ObjectInputStream stream)130 private void readObject(ObjectInputStream stream) 131 throws IOException, ClassNotFoundException { 132 stream.defaultReadObject(); 133 expectedValuesPerKey = stream.readInt(); 134 int distinctKeys = Serialization.readCount(stream); 135 Map<K, Collection<V>> map = Maps.newHashMapWithExpectedSize(distinctKeys); 136 setMap(map); 137 Serialization.populateMultimap(this, stream, distinctKeys); 138 } 139 140 @GwtIncompatible("Not needed in emulated source") 141 private static final long serialVersionUID = 0; 142 } 143