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; 023import java.io.IOException; 024import java.io.ObjectInputStream; 025import java.io.ObjectOutputStream; 026import java.util.Collection; 027import java.util.Map; 028import java.util.Set; 029import org.checkerframework.checker.nullness.qual.Nullable; 030 031/** 032 * Implementation of {@link Multimap} using hash tables. 033 * 034 * <p>The multimap does not store duplicate key-value pairs. Adding a new key-value pair equal to an 035 * existing key-value pair has no effect. 036 * 037 * <p>Keys and values may be null. All optional multimap methods are supported, and all returned 038 * views are modifiable. 039 * 040 * <p>This class is not threadsafe when any concurrent operations update the multimap. Concurrent 041 * read operations will work correctly if the last write <i>happens-before</i> any reads. To allow 042 * concurrent update operations, wrap your multimap with a call to {@link 043 * Multimaps#synchronizedSetMultimap}. 044 * 045 * <p><b>Warning:</b> Do not modify either a key <i>or a value</i> of a {@code HashMultimap} in a 046 * way that affects its {@link Object#equals} behavior. Undefined behavior and bugs will result. 047 * 048 * @author Jared Levy 049 * @since 2.0 050 */ 051@GwtCompatible(serializable = true, emulated = true) 052@ElementTypesAreNonnullByDefault 053public final class HashMultimap<K extends @Nullable Object, V extends @Nullable Object> 054 extends HashMultimapGwtSerializationDependencies<K, V> { 055 private static final int DEFAULT_VALUES_PER_KEY = 2; 056 057 @VisibleForTesting transient int expectedValuesPerKey = DEFAULT_VALUES_PER_KEY; 058 059 /** 060 * Creates a new, empty {@code HashMultimap} with the default initial capacities. 061 * 062 * <p>This method will soon be deprecated in favor of {@code 063 * MultimapBuilder.hashKeys().hashSetValues().build()}. 064 */ 065 public static <K extends @Nullable Object, V extends @Nullable Object> 066 HashMultimap<K, V> create() { 067 return new HashMultimap<>(); 068 } 069 070 /** 071 * Constructs an empty {@code HashMultimap} with enough capacity to hold the specified numbers of 072 * keys and values without rehashing. 073 * 074 * <p>This method will soon be deprecated in favor of {@code 075 * MultimapBuilder.hashKeys(expectedKeys).hashSetValues(expectedValuesPerKey).build()}. 076 * 077 * @param expectedKeys the expected number of distinct keys 078 * @param expectedValuesPerKey the expected average number of values per key 079 * @throws IllegalArgumentException if {@code expectedKeys} or {@code expectedValuesPerKey} is 080 * negative 081 */ 082 public static <K extends @Nullable Object, V extends @Nullable Object> HashMultimap<K, V> create( 083 int expectedKeys, int expectedValuesPerKey) { 084 return new HashMultimap<>(expectedKeys, expectedValuesPerKey); 085 } 086 087 /** 088 * Constructs a {@code HashMultimap} with the same mappings as the specified multimap. If a 089 * key-value mapping appears multiple times in the input multimap, it only appears once in the 090 * constructed multimap. 091 * 092 * <p>This method will soon be deprecated in favor of {@code 093 * MultimapBuilder.hashKeys().hashSetValues().build(multimap)}. 094 * 095 * @param multimap the multimap whose contents are copied to this multimap 096 */ 097 public static <K extends @Nullable Object, V extends @Nullable Object> HashMultimap<K, V> create( 098 Multimap<? extends K, ? extends V> multimap) { 099 return new HashMultimap<>(multimap); 100 } 101 102 private HashMultimap() { 103 this(12, DEFAULT_VALUES_PER_KEY); 104 } 105 106 private HashMultimap(int expectedKeys, int expectedValuesPerKey) { 107 super(Platform.<K, Collection<V>>newHashMapWithExpectedSize(expectedKeys)); 108 Preconditions.checkArgument(expectedValuesPerKey >= 0); 109 this.expectedValuesPerKey = expectedValuesPerKey; 110 } 111 112 private HashMultimap(Multimap<? extends K, ? extends V> multimap) { 113 super(Platform.<K, Collection<V>>newHashMapWithExpectedSize(multimap.keySet().size())); 114 putAll(multimap); 115 } 116 117 /** 118 * {@inheritDoc} 119 * 120 * <p>Creates an empty {@code HashSet} for a collection of values for one key. 121 * 122 * @return a new {@code HashSet} containing a collection of values for one key 123 */ 124 @Override 125 Set<V> createCollection() { 126 return Platform.<V>newHashSetWithExpectedSize(expectedValuesPerKey); 127 } 128 129 /** 130 * @serialData expectedValuesPerKey, number of distinct keys, and then for each distinct key: the 131 * key, number of values for that key, and the key's values 132 */ 133 @GwtIncompatible // java.io.ObjectOutputStream 134 private void writeObject(ObjectOutputStream stream) throws IOException { 135 stream.defaultWriteObject(); 136 Serialization.writeMultimap(this, stream); 137 } 138 139 @GwtIncompatible // java.io.ObjectInputStream 140 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 141 stream.defaultReadObject(); 142 expectedValuesPerKey = DEFAULT_VALUES_PER_KEY; 143 int distinctKeys = Serialization.readCount(stream); 144 Map<K, Collection<V>> map = Platform.newHashMapWithExpectedSize(12); 145 setMap(map); 146 Serialization.populateMultimap(this, stream, distinctKeys); 147 } 148 149 @GwtIncompatible // Not needed in emulated source 150 private static final long serialVersionUID = 0; 151}