Guava源码学习(四)新集合类型

时间:2020-12-21 20:47:22

基于版本:Guava 22.0

Wiki:New collection types

 

0. 简介

Guava提供了很多好用的集合工具,比如Multiset和BiMap,本文介绍了这些新集合类型的使用方式与实现原理。

 

1. Multiset

  a. 简介

  一般的Set会对相同元素去重,而Multiset则会记下某个元素重复出现的次数。可以理解为Multiset内部维护了一个HashMap,对每个元素的重复次数进行计数,每次插入或者删除元素,都会更新这个HashMap。

  b. Multiset类图

Guava源码学习(四)新集合类型

  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的类图

  Guava源码学习(四)新集合类型

  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类图

Guava源码学习(四)新集合类型

  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();
}
....
}