    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    }