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