001    /*
002     * Copyright (C) 2007 The Guava Authors
003     *
004     * Licensed under the Apache License, Version 2.0 (the "License");
005     * you may not use this file except in compliance with the License.
006     * You may obtain a copy of the License at
007     *
008     * http://www.apache.org/licenses/LICENSE-2.0
009     *
010     * Unless required by applicable law or agreed to in writing, software
011     * distributed under the License is distributed on an "AS IS" BASIS,
012     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013     * See the License for the specific language governing permissions and
014     * limitations under the License.
015     */
016    
017    package com.google.common.collect;
018    
019    import com.google.common.annotations.GwtCompatible;
020    import com.google.common.annotations.GwtIncompatible;
021    import com.google.common.annotations.VisibleForTesting;
022    import com.google.common.base.Preconditions;
023    
024    import java.io.IOException;
025    import java.io.ObjectInputStream;
026    import java.io.ObjectOutputStream;
027    import java.util.Collection;
028    import java.util.HashMap;
029    import java.util.Map;
030    import java.util.Set;
031    
032    /**
033     * Implementation of {@link Multimap} using hash tables.
034     *
035     * <p>The multimap does not store duplicate key-value pairs. Adding a new
036     * key-value pair equal to an existing key-value pair has no effect.
037     *
038     * <p>Keys and values may be null. All optional multimap methods are supported,
039     * and all returned views are modifiable.
040     *
041     * <p>This class is not threadsafe when any concurrent operations update the
042     * multimap. Concurrent read operations will work correctly. To allow concurrent
043     * update operations, wrap your multimap with a call to {@link
044     * Multimaps#synchronizedSetMultimap}.
045     *
046     * @author Jared Levy
047     * @since 2.0 (imported from Google Collections Library)
048     */
049    @GwtCompatible(serializable = true, emulated = true)
050    public final class HashMultimap<K, V> extends AbstractSetMultimap<K, V> {
051      private static final int DEFAULT_VALUES_PER_KEY = 8;
052    
053      @VisibleForTesting
054      transient int expectedValuesPerKey = DEFAULT_VALUES_PER_KEY;
055    
056      /**
057       * Creates a new, empty {@code HashMultimap} with the default initial
058       * capacities.
059       */
060      public static <K, V> HashMultimap<K, V> create() {
061        return new HashMultimap<K, V>();
062      }
063    
064      /**
065       * Constructs an empty {@code HashMultimap} with enough capacity to hold the
066       * specified numbers of keys and values without rehashing.
067       *
068       * @param expectedKeys the expected number of distinct keys
069       * @param expectedValuesPerKey the expected average number of values per key
070       * @throws IllegalArgumentException if {@code expectedKeys} or {@code
071       *      expectedValuesPerKey} is negative
072       */
073      public static <K, V> HashMultimap<K, V> create(
074          int expectedKeys, int expectedValuesPerKey) {
075        return new HashMultimap<K, V>(expectedKeys, expectedValuesPerKey);
076      }
077    
078      /**
079       * Constructs a {@code HashMultimap} with the same mappings as the specified
080       * multimap. If a key-value mapping appears multiple times in the input
081       * multimap, it only appears once in the constructed multimap.
082       *
083       * @param multimap the multimap whose contents are copied to this multimap
084       */
085      public static <K, V> HashMultimap<K, V> create(
086          Multimap<? extends K, ? extends V> multimap) {
087        return new HashMultimap<K, V>(multimap);
088      }
089    
090      private HashMultimap() {
091        super(new HashMap<K, Collection<V>>());
092      }
093    
094      private HashMultimap(int expectedKeys, int expectedValuesPerKey) {
095        super(Maps.<K, Collection<V>>newHashMapWithExpectedSize(expectedKeys));
096        Preconditions.checkArgument(expectedValuesPerKey >= 0);
097        this.expectedValuesPerKey = expectedValuesPerKey;
098      }
099    
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       */
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")
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")
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    }