基于版本：Guava 22.0
Wiki：New collection types
0. 简介
Guava提供了很多好用的集合工具，比如Multiset和BiMap，本文介绍了这些新集合类型的使用方式与实现原理。
1. Multiset
a. 简介
一般的Set会对相同元素去重，而Multiset则会记下某个元素重复出现的次数。可以理解为Multiset内部维护了一个HashMap，对每个元素的重复次数进行计数，每次插入或者删除元素，都会更新这个HashMap。
b. Multiset类图
c. Multiset接口
int size();
int count(@Nullable @CompatibleWith("E") Object element);
int add(@Nullable E element, int occurrences);
int remove(@Nullable @CompatibleWith("E") Object element, int occurrences);
int setCount(E element, int count);
boolean setCount(E element, int oldCount, int newCount);
Set<E> elementSet();
Set<Entry<E>> entrySet();
default void forEachEntry(ObjIntConsumer<? super E> action)
boolean equals(@Nullable Object object);
int hashCode();
String toString();
Iterator<E> iterator();
boolean contains(@Nullable Object element);
boolean containsAll(Collection<?> elements);
boolean add(E element);
boolean remove(@Nullable Object element);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
default void forEach(Consumer<? super E> action)
default Spliterator<E> spliterator()
Multiset的子类很多，后续只介绍最有代表性的HashMultiset的实现
d. HashMultiset的类图
e. HashMultiset.add方法
Multiset.add
@CanIgnoreReturnValue
@Override
boolean add(E element); AbstractMultiset.add
@CanIgnoreReturnValue
@Override
public boolean add(@Nullable E element) {
add(element, 1);
return true;
} @CanIgnoreReturnValue
@Override
public int add(@Nullable E element, int occurrences) {
throw new UnsupportedOperationException();
}
AbstractMapBasedMultiset.add
@CanIgnoreReturnValue
@Override
public int add(@Nullable E element, int occurrences) {
if (occurrences == 0) {
return count(element);
}
checkArgument(occurrences > 0, "occurrences cannot be negative: %s", occurrences);
Count frequency = backingMap.get(element);
int oldCount;
if (frequency == null) {
oldCount = 0;
backingMap.put(element, new Count(occurrences));
} else {
oldCount = frequency.get();
long newCount = (long) oldCount + (long) occurrences;
checkArgument(newCount <= Integer.MAX_VALUE, "too many occurrences: %s", newCount);
frequency.add(occurrences);
}
size += occurrences;
return oldCount;
}
从add方法中，我们就能看出HashMultiset的基本逻辑：内部维护了一个Map，每次add key的时候，更新Map中key对应的value（计数器）
2. BiMap
a. 简介
一般的Map是维护了从key到value的单向映射，某些场景下我们可能会需要双向映射。一般的做法是同时维护两个Map，一个Map的key是另外一个Map的value。但是这样麻烦而且容易出错。为了解决这一需求，Guava提供了BiMap接口与若干实现类。
b. BiMap类图
c. BiMap接口
V put(@Nullable K key, @Nullable V value); /**
* An alternate form of {@code put} that silently removes any existing entry
* with the value {@code value} before proceeding with the {@link #put}
* operation. If the bimap previously contained the provided key-value
* mapping, this method has no effect.
*
* <p>Note that a successful call to this method could cause the size of the
* bimap to increase by one, stay the same, or even decrease by one.
*
* <p><b>Warning:</b> If an existing entry with this value is removed, the key
* for that entry is discarded and not returned.
*
* @param key the key with which the specified value is to be associated
* @param value the value to be associated with the specified key
* @return the value which was previously associated with the key, which may
* be {@code null}, or {@code null} if there was no previous entry
*/
@CanIgnoreReturnValue
@Nullable
V forcePut(@Nullable K key, @Nullable V value); void putAll(Map<? extends K, ? extends V> map);
Set<V> values(); /**
* Returns the inverse view of this bimap, which maps each of this bimap's
* values to its associated key. The two bimaps are backed by the same data;
* any changes to one will appear in the other.
*
* <p><b>Note:</b>There is no guaranteed correspondence between the iteration
* order of a bimap and that of its inverse.
*
* @return the inverse view of this bimap
*/
BiMap<V, K> inverse();
跟一般的Map的区别在于加黑标出的forcePut与inverse方法
forcePut：在BiMap中，如果你想把键映射到已经存在的值，会抛出IllegalArgumentException异常。如果对特定值，你想要强制替换它的键，需要使用forcePut方法
inverse：返回的BiMap是原BiMap的反转
d. HashBiMap的基本原理
内部维护了两个等长Entry数组hashTableKToV与hashTableVToK，采用链地址法解决哈希冲突，每次操作会同时维护这两个数组。在插入hashTableVToK时如果value已经存在且不为强制更新，则抛出异常。
e. HashBiMap.put
private V put(@Nullable K key, @Nullable V value, boolean force) {
int keyHash = smearedHash(key);
int valueHash = smearedHash(value);
BiEntry<K, V> oldEntryForKey = seekByKey(key, keyHash);//去hashTableKToV里根据key寻找Entry
if (oldEntryForKey != null
&& valueHash == oldEntryForKey.valueHash
&& Objects.equal(value, oldEntryForKey.value)) {
return value;//Entry已经存在，无需更新，函数可以直接返回
}
BiEntry<K, V> oldEntryForValue = seekByValue(value, valueHash);//去hashTableVToK里根据value选择Entry
if (oldEntryForValue != null) {
if (force) {//如果是强制更新，则删除关联的Entry
delete(oldEntryForValue);
} else {//抛出错误，否则会出现一个value对应多个key的情况，inverse后无法处理
throw new IllegalArgumentException("value already present: " + value);
}
}
BiEntry<K, V> newEntry = new BiEntry<K, V>(key, keyHash, value, valueHash);//创建新BiEntry
if (oldEntryForKey != null) {//更新key对应的value的情况
delete(oldEntryForKey);//先删除老的BiEntry
insert(newEntry, oldEntryForKey);//插入新的BiEntry
oldEntryForKey.prevInKeyInsertionOrder = null;
oldEntryForKey.nextInKeyInsertionOrder = null;
rehashIfNecessary();//扩容
return oldEntryForKey.value;
} else {//插入新键值对的情况
insert(newEntry, null);
rehashIfNecessary();//扩容
return null;
}
}
private void delete(BiEntry<K, V> entry) {
int keyBucket = entry.keyHash & mask;//删除hashTableKToV中的Entry
BiEntry<K, V> prevBucketEntry = null;
for (BiEntry<K, V> bucketEntry = hashTableKToV[keyBucket];
true;
bucketEntry = bucketEntry.nextInKToVBucket) {
if (bucketEntry == entry) {
if (prevBucketEntry == null) {
hashTableKToV[keyBucket] = entry.nextInKToVBucket;
} else {
prevBucketEntry.nextInKToVBucket = entry.nextInKToVBucket;
}
break;
}
prevBucketEntry = bucketEntry;
}
int valueBucket = entry.valueHash & mask;//删除hashTableVToK中的Entry
prevBucketEntry = null;
for (BiEntry<K, V> bucketEntry = hashTableVToK[valueBucket];
true;
bucketEntry = bucketEntry.nextInVToKBucket) {
if (bucketEntry == entry) {
if (prevBucketEntry == null) {
hashTableVToK[valueBucket] = entry.nextInVToKBucket;
} else {
prevBucketEntry.nextInVToKBucket = entry.nextInVToKBucket;
}
break;
}
prevBucketEntry = bucketEntry;
}
if (entry.prevInKeyInsertionOrder == null) {
firstInKeyInsertionOrder = entry.nextInKeyInsertionOrder;
} else {
entry.prevInKeyInsertionOrder.nextInKeyInsertionOrder = entry.nextInKeyInsertionOrder;
}
if (entry.nextInKeyInsertionOrder == null) {
lastInKeyInsertionOrder = entry.prevInKeyInsertionOrder;
} else {
entry.nextInKeyInsertionOrder.prevInKeyInsertionOrder = entry.prevInKeyInsertionOrder;
}
size--;
modCount++;
}
private void insert(BiEntry<K, V> entry, @Nullable BiEntry<K, V> oldEntryForKey) {
int keyBucket = entry.keyHash & mask;
entry.nextInKToVBucket = hashTableKToV[keyBucket];
hashTableKToV[keyBucket] = entry;
int valueBucket = entry.valueHash & mask;
entry.nextInVToKBucket = hashTableVToK[valueBucket];
hashTableVToK[valueBucket] = entry;
if (oldEntryForKey == null) {
entry.prevInKeyInsertionOrder = lastInKeyInsertionOrder;
entry.nextInKeyInsertionOrder = null;
if (lastInKeyInsertionOrder == null) {
firstInKeyInsertionOrder = entry;
} else {
lastInKeyInsertionOrder.nextInKeyInsertionOrder = entry;
}
lastInKeyInsertionOrder = entry;
} else {
entry.prevInKeyInsertionOrder = oldEntryForKey.prevInKeyInsertionOrder;
if (entry.prevInKeyInsertionOrder == null) {
firstInKeyInsertionOrder = entry;
} else {
entry.prevInKeyInsertionOrder.nextInKeyInsertionOrder = entry;
}
entry.nextInKeyInsertionOrder = oldEntryForKey.nextInKeyInsertionOrder;
if (entry.nextInKeyInsertionOrder == null) {
lastInKeyInsertionOrder = entry;
} else {
entry.nextInKeyInsertionOrder.prevInKeyInsertionOrder = entry;
}
}
size++;
modCount++;
}
f. HashBiMap.inverse
@Override
public BiMap<V, K> inverse() {
return (inverse == null) ? inverse = new Inverse() : inverse;
} private final class Inverse extends IteratorBasedAbstractMap<V, K>
implements BiMap<V, K>, Serializable {
BiMap<K, V> forward() {
return HashBiMap.this;//原来的正向的HashBiMap
} @Override
public int size() {
return size;
} @Override
public void clear() {
forward().clear();//调用原来的HashBiMap的方法
} @Override
public boolean containsKey(@Nullable Object value) {
return forward().containsValue(value);
} @Override
public K get(@Nullable Object value) {
return Maps.keyOrNull(seekByValue(value, smearedHash(value)));
} @CanIgnoreReturnValue
@Override
public K put(@Nullable V value, @Nullable K key) {
return putInverse(value, key, false);
} @Override
public K forcePut(@Nullable V value, @Nullable K key) {
return putInverse(value, key, true);
} @Override
public K remove(@Nullable Object value) {
BiEntry<K, V> entry = seekByValue(value, smearedHash(value));
if (entry == null) {
return null;
} else {
delete(entry);
entry.prevInKeyInsertionOrder = null;
entry.nextInKeyInsertionOrder = null;
return entry.key;
}
} @Override
public BiMap<K, V> inverse() {
return forward();//直接返回原HashBiMap
} @Override
public Set<V> keySet() {
return new InverseKeySet();
}
....
}