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
017package com.google.common.collect;
018
019import com.google.common.annotations.GwtCompatible;
020import com.google.common.annotations.GwtIncompatible;
021import com.google.common.annotations.VisibleForTesting;
022import com.google.common.base.Preconditions;
023
024import java.io.IOException;
025import java.io.ObjectInputStream;
026import java.io.ObjectOutputStream;
027import java.util.Collection;
028import java.util.HashMap;
029import java.util.Map;
030import 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
048 */
049@GwtCompatible(serializable = true, emulated = true)
050public final class HashMultimap<K, V> extends AbstractSetMultimap<K, V> {
051  private static final int DEFAULT_VALUES_PER_KEY = 2;
052
053  @VisibleForTesting transient int expectedValuesPerKey = DEFAULT_VALUES_PER_KEY;
054
055  /**
056   * Creates a new, empty {@code HashMultimap} with the default initial
057   * capacities.
058   */
059  public static <K, V> HashMultimap<K, V> create() {
060    return new HashMultimap<K, V>();
061  }
062
063  /**
064   * Constructs an empty {@code HashMultimap} with enough capacity to hold the
065   * specified numbers of keys and values without rehashing.
066   *
067   * @param expectedKeys the expected number of distinct keys
068   * @param expectedValuesPerKey the expected average number of values per key
069   * @throws IllegalArgumentException if {@code expectedKeys} or {@code
070   *      expectedValuesPerKey} is negative
071   */
072  public static <K, V> HashMultimap<K, V> create(int expectedKeys, int expectedValuesPerKey) {
073    return new HashMultimap<K, V>(expectedKeys, expectedValuesPerKey);
074  }
075
076  /**
077   * Constructs a {@code HashMultimap} with the same mappings as the specified
078   * multimap. If a key-value mapping appears multiple times in the input
079   * multimap, it only appears once in the constructed multimap.
080   *
081   * @param multimap the multimap whose contents are copied to this multimap
082   */
083  public static <K, V> HashMultimap<K, V> create(Multimap<? extends K, ? extends V> multimap) {
084    return new HashMultimap<K, V>(multimap);
085  }
086
087  private HashMultimap() {
088    super(new HashMap<K, Collection<V>>());
089  }
090
091  private HashMultimap(int expectedKeys, int expectedValuesPerKey) {
092    super(Maps.<K, Collection<V>>newHashMapWithExpectedSize(expectedKeys));
093    Preconditions.checkArgument(expectedValuesPerKey >= 0);
094    this.expectedValuesPerKey = expectedValuesPerKey;
095  }
096
097  private HashMultimap(Multimap<? extends K, ? extends V> multimap) {
098    super(Maps.<K, Collection<V>>newHashMapWithExpectedSize(multimap.keySet().size()));
099    putAll(multimap);
100  }
101
102  /**
103   * {@inheritDoc}
104   *
105   * <p>Creates an empty {@code HashSet} for a collection of values for one key.
106   *
107   * @return a new {@code HashSet} containing a collection of values for one key
108   */
109  @Override
110  Set<V> createCollection() {
111    return Sets.<V>newHashSetWithExpectedSize(expectedValuesPerKey);
112  }
113
114  /**
115   * @serialData expectedValuesPerKey, number of distinct keys, and then for
116   *     each distinct key: the key, number of values for that key, and the
117   *     key's values
118   */
119  @GwtIncompatible("java.io.ObjectOutputStream")
120  private void writeObject(ObjectOutputStream stream) throws IOException {
121    stream.defaultWriteObject();
122    Serialization.writeMultimap(this, stream);
123  }
124
125  @GwtIncompatible("java.io.ObjectInputStream")
126  private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
127    stream.defaultReadObject();
128    expectedValuesPerKey = DEFAULT_VALUES_PER_KEY;
129    int distinctKeys = Serialization.readCount(stream);
130    Map<K, Collection<V>> map = Maps.newHashMap();
131    setMap(map);
132    Serialization.populateMultimap(this, stream, distinctKeys);
133  }
134
135  @GwtIncompatible("Not needed in emulated source")
136  private static final long serialVersionUID = 0;
137}