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.jspecify.annotations.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) 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>You may also consider the equivalent {@code 063 * MultimapBuilder.hashKeys().hashSetValues().build()}, which provides more control over the 064 * underlying data structure. 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>You may also consider the equivalent {@code 076 * MultimapBuilder.hashKeys(expectedKeys).hashSetValues(expectedValuesPerKey).build()}, which 077 * provides more control over the underlying data structure. 078 * 079 * @param expectedKeys the expected number of distinct keys 080 * @param expectedValuesPerKey the expected average number of values per key 081 * @throws IllegalArgumentException if {@code expectedKeys} or {@code expectedValuesPerKey} is 082 * negative 083 */ 084 public static <K extends @Nullable Object, V extends @Nullable Object> HashMultimap<K, V> create( 085 int expectedKeys, int expectedValuesPerKey) { 086 return new HashMultimap<>(expectedKeys, expectedValuesPerKey); 087 } 088 089 /** 090 * Constructs a {@code HashMultimap} with the same mappings as the specified multimap. If a 091 * key-value mapping appears multiple times in the input multimap, it only appears once in the 092 * constructed multimap. 093 * 094 * <p>You may also consider the equivalent {@code 095 * MultimapBuilder.hashKeys().hashSetValues().build(multimap)}, which provides more control over 096 * the underlying data structure. 097 * 098 * @param multimap the multimap whose contents are copied to this multimap 099 */ 100 public static <K extends @Nullable Object, V extends @Nullable Object> HashMultimap<K, V> create( 101 Multimap<? extends K, ? extends V> multimap) { 102 return new HashMultimap<>(multimap); 103 } 104 105 private HashMultimap() { 106 this(12, DEFAULT_VALUES_PER_KEY); 107 } 108 109 private HashMultimap(int expectedKeys, int expectedValuesPerKey) { 110 super(Platform.<K, Collection<V>>newHashMapWithExpectedSize(expectedKeys)); 111 Preconditions.checkArgument(expectedValuesPerKey >= 0); 112 this.expectedValuesPerKey = expectedValuesPerKey; 113 } 114 115 private HashMultimap(Multimap<? extends K, ? extends V> multimap) { 116 super(Platform.<K, Collection<V>>newHashMapWithExpectedSize(multimap.keySet().size())); 117 putAll(multimap); 118 } 119 120 /** 121 * {@inheritDoc} 122 * 123 * <p>Creates an empty {@code HashSet} for a collection of values for one key. 124 * 125 * @return a new {@code HashSet} containing a collection of values for one key 126 */ 127 @Override 128 Set<V> createCollection() { 129 return Platform.<V>newHashSetWithExpectedSize(expectedValuesPerKey); 130 } 131 132 /** 133 * @serialData expectedValuesPerKey, number of distinct keys, and then for each distinct key: the 134 * key, number of values for that key, and the key's values 135 */ 136 @GwtIncompatible // java.io.ObjectOutputStream 137 @J2ktIncompatible 138 private void writeObject(ObjectOutputStream stream) throws IOException { 139 stream.defaultWriteObject(); 140 Serialization.writeMultimap(this, stream); 141 } 142 143 @GwtIncompatible // java.io.ObjectInputStream 144 @J2ktIncompatible 145 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 146 stream.defaultReadObject(); 147 expectedValuesPerKey = DEFAULT_VALUES_PER_KEY; 148 int distinctKeys = Serialization.readCount(stream); 149 Map<K, Collection<V>> map = Platform.newHashMapWithExpectedSize(12); 150 setMap(map); 151 Serialization.populateMultimap(this, stream, distinctKeys); 152 } 153 154 @GwtIncompatible // Not needed in emulated source 155 @J2ktIncompatible 156 private static final long serialVersionUID = 0; 157}