【Guava】BiMap&Multimap&Multiset

BiMap

Map 可以实现 key -> value 的映射，假如想要 value -> key 的映射，就需要定义两个 Map，并且同步更新，很不优雅。Guava 提供了 BiMap 支持支持双向的映射关系，常用实现有HashMap, EnumBiMap, EnumHashBiMap...。
而它对key和value严格的保证唯一性。假如使用put方法添加雷同的value值或key值则会抛出异常：java.lang.IllegalArgumentException，假如使用forcePut方法添加则会覆盖掉原来的value值。

1. BiMap<String, Integer> biMap = HashBiMap.create();
2. biMap.put("A", 100);
4. // 删除已存在的 KV，重新添加 KV
5. biMap.forcePut("A", 200);
7. // 获取反向映射
8. BiMap<Integer, String> inverse = biMap.inverse();
9. log.debug("{}", inverse.get(100));

复制代码

这里主要使用HashBiMap 举行分析
成员变量

1. private static final double LOAD_FACTOR = 1.0D;
2. // BiEntry是HashBiMap中为的Map.Entry接口的实现类，这里定义了两个BiEntry，一个是实现使用Key找到value的，另一个是实现使用value找到key的
3. private transient HashBiMap.BiEntry<K, V>[] hashTableKToV;
4. private transient HashBiMap.BiEntry<K, V>[] hashTableVToK;
5. private transient int size;
6. private transient int mask;
7. private transient int modCount;
8. private transient BiMap<V, K> inverse;

复制代码

HashMap做的是唯一key值对应的value可以不唯一，而Bimap做的是唯一key值，value值也要唯一，方便从key找到value，从value找到key

1. private static final class BiEntry<K, V> extends ImmutableEntry<K, V> {
2.     //key的hash值
3.     final int keyHash;
4.     //value的hash值
5.     final int valueHash;
6.     @Nullable
7.     //为key链表做的指向下一个节点的变量
8.     HashBiMap.BiEntry<K, V> nextInKToVBucket;
9.     @Nullable
10.     //为value链表做的指向下一个节点的变量
11.     HashBiMap.BiEntry<K, V> nextInVToKBucket;
12.     BiEntry(K key, int keyHash, V value, int valueHash) {
13.         super(key, value);
14.         this.keyHash = keyHash;
15.         this.valueHash = valueHash;
16.     }
17. }

复制代码

对比一下HashMap的Node源码：

1. static class Node<K,V> implements Map.Entry<K,V> {
2.     //因为HashMap实现的功能只需要key找到value，所以这里的hash值默认就是key的hash值
3.     final int hash;
4.     final K key;
5.     V value;
6.     //在HashMap中的链表只做key的链表就好，所以只需要一个指向下一个节点的变量
7.     Node<K,V> next;
8. }

复制代码

构造方法

1. //传入期望容器长度
2. private HashBiMap(int expectedSize) {
3.     this.init(expectedSize);
4. }

复制代码

可以看到构造方法是私有的，以是在类中一定会有静态方法构造器会用到这个私有的构造方法。
这个构造方法调用了init方法，可以看一下init方法的源码：

1. private void init(int expectedSize) {
2.     CollectPreconditions.checkNonnegative(expectedSize, "expectedSize");
3.     //经过closedTableSize方法运算达到期望的实际值
4.     int tableSize = Hashing.closedTableSize(expectedSize, 1.0D);
5.     //初始化key和value存储链表的数组
6.     this.hashTableKToV = this.createTable(tableSize);
7.     this.hashTableVToK = this.createTable(tableSize);
8.     //初始化mask为数组最大小标值
9.     this.mask = tableSize - 1;
10.     //初始化modCount值为0
11.     this.modCount = 0;
12.     //初始化size值为0
13.     this.size = 0;
14. }

复制代码

静态方法构造器

1. public static <K, V> HashBiMap<K, V> create() {
2.     //调用另一个create构造器，期望长度为16
3.     return create(16);
4. }
5. public static <K, V> HashBiMap<K, V> create(int expectedSize) {
6.     //直接创建一个长度为expectedSize的HashBiMap
7.     return new HashBiMap(expectedSize);
8. }
9. public static <K, V> HashBiMap<K, V> create(Map<? extends K, ? extends V> map) {
10.     //创建一个与传入map相同长度的biMap
11.     HashBiMap bimap = create(map.size());
12.     //然后将传入map的值全部赋值给新的BiMap
13.     bimap.putAll(map);
14.     return bimap;
15. }

复制代码

Multiset的接口中方法的实现在AbstractMapBasedMultiset抽象类中，下面针对AbstractMapBasedMultiset类的存储数据结构。add、remove、count和迭代器的实现举行分析
存储数据结构

1. public V put(@Nullable K key, @Nullable V value) {
2.     return this.put(key, value, false);
3. }
4. public V forcePut(@Nullable K key, @Nullable V value) {
5.     return this.put(key, value, true);
6. }

复制代码

构造方法

1. private V put(@Nullable K key, @Nullable V value, boolean force) {
2.     //获取传入key的hash值
3.     int keyHash = hash(key);
4.     //获取传入value的hash值
5.     int valueHash = hash(value);
6.     //根据key的值和它的hash值查找是否存在这个节点，seekByKey方法就是遍历了这个keyhash所映射的下标上的链表进行查找。
7.     HashBiMap.BiEntry oldEntryForKey = this.seekByKey(key, keyHash);
8.     if(oldEntryForKey != null && valueHash == oldEntryForKey.valueHash && Objects.equal(value, oldEntryForKey.value)) {
9.         //如果这个key值存在，并且value也相等，则返回这个value
10.         return value;
11.     } else {
12.         //使用seekByValue查找这个value是否存在
13.         HashBiMap.BiEntry oldEntryForValue = this.seekByValue(value, valueHash);
14.         if(oldEntryForValue != null) {
15.                         //如果存在，则判断force（第三个参数）是否为false
16.             if(!force) {//Value已经存在了，因此要判断是否允许强制插入
17.                 //如果force（第三个参数）为false
18.                 //则直接抛出异常
19.                 String newEntry1 = String.valueOf(String.valueOf(value));
20.                 throw new IllegalArgumentException((new StringBuilder(23 + newEntry1.length())).append("value already present: ").append(newEntry1).toString());
21.             }
22.             //如果force（第三个参数）为true，则删除这个节点，这个方法是双向删除
23.             this.delete(oldEntryForValue);
24.         }
25.         //如果key存在，则删除这个节点
26.         if(oldEntryForKey != null) {
27.             this.delete(oldEntryForKey);
28.         }
29.         //根据key，value，keyHash，valueHash创建一个BiEntry
30.         HashBiMap.BiEntry newEntry = new HashBiMap.BiEntry(key, keyHash, value, valueHash);
31.         //插入这个节点。
32.         this.insert(newEntry);
33.         //插入完成，刷新一下，看看是否需要扩容
34.         this.rehashIfNecessary();
35.         return oldEntryForKey == null?null:oldEntryForKey.value;
36.     }
37. }

复制代码

add方法

1. private void insert(HashBiMap.BiEntry<K, V> entry) {
2.     //计算出这个节点在key容器中的下标位置
3.     int keyBucket = entry.keyHash & this.mask;
4.     //使当前节点的keynext指向当前下标位置上
5.     entry.nextInKToVBucket = this.hashTableKToV[keyBucket];
6.     //将当前节点赋值给这个下标位置
7.     this.hashTableKToV[keyBucket] = entry;
9.     //value如key一样
10.     int valueBucket = entry.valueHash & this.mask;
11.     entry.nextInVToKBucket = this.hashTableVToK[valueBucket];
12.     this.hashTableVToK[valueBucket] = entry;
13.     //size加1
14.     ++this.size;
15.     ++this.modCount;
16. }

复制代码

Count方法

1. // 列表实现
2. ListMultimap<String, Integer> listMultimap = MultimapBuilder.hashKeys().arrayListValues().build();
3. // 集合实现
4. SetMultimap<String, Integer> setMultimap = MultimapBuilder.treeKeys().hashSetValues().build();
6. listMultimap.put("A", 1);
7. listMultimap.put("A", 2);
8. listMultimap.put("B", 1);
9. // {A=[1, 2], B=[1, 2]}
10. log.debug("{}", listMultimap);
11. // [1, 2]，不存在则返回一个空集合
12. log.debug("{}", listMultimap.get("A"));
13. // [1, 2] 移除 key 关联的所有 value
14. List<Integer> valList = listMultimap.removeAll("A");
16. // 返回普通 map 的视图，仅支持 remove，不能 put，且会更新原始的 listMultimap
17. Map<String, Collection<Integer>> map = listMultimap.asMap();

复制代码

迭代器

1. public static <K, V> HashMultimap<K, V> create() {
2.         //new一个HashMultimap，不传入任何值
3.     return new HashMultimap();
4. }
5. public static <K, V> HashMultimap<K, V> create(int expectedKeys, int expectedValuesPerKey) {
6.         //new一个HashHultimap，传入两个值，一个是期望key的长度，另一个是期望value的长度
7.     return new HashMultimap(expectedKeys, expectedValuesPerKey);
8. }
9. public static <K, V> HashMultimap<K, V> create(Multimap<? extends K, ? extends V> multimap) {
10.         //传入一个Multimap值
11.     return new HashMultimap(multimap);
12. }

复制代码

Multiset中有一个实现了Iterator接口的类：
[code]private class MapBasedMultisetIterator implements Iterator {    final Iterator entryIterator;    java.util.Map.Entry currentEntry;    int occurrencesLeft;    boolean canRemove;    MapBasedMultisetIterator() {        //获取当前map容器的迭代器        this.entryIterator = AbstractMapBasedMultiset.this.backingMap.entrySet().iterator();    }    //根据当前迭代器判断是否另有元素    public boolean hasNext() {        return this.occurrencesLeft > 0 || this.entryIterator.hasNext();    }    public E next() {        //假如occurrencesLeft为0，则说明现在处于刚开始，或上一个元素完成        if(this.occurrencesLeft == 0) {            //迭代器向下获取一个元素            this.currentEntry = (java.util.Map.Entry)this.entryIterator.next();            //获取到当前元素的个数            this.occurrencesLeft = ((Count)this.currentEntry.getValue()).get();        }        //因为是获取一个元素，以是减去这一个        --this.occurrencesLeft;        this.canRemove = true;        return this.currentEntry.getKey();    }    public void remove() {        CollectPreconditions.checkRemove(this.canRemove);        int frequency = ((Count)this.currentEntry.getValue()).get();        if(frequency