BiMap
Map can implement the mapping of key -> value. If you want the mapping of value -> key, you need to define two maps and update them simultaneously, which is not elegant. Guava provides BiMap support to support bidirectional mapping relationships, commonly used implementations includeHashMap, EnumBiMap, EnumHashBiMap...。
And it strictly guarantees uniqueness to key and value. If you add the same value or key value using the put method, an exception will be thrown: If you add it using the forcePut method, the original value will be overwritten.
BiMap<String, Integer> biMap = ();
("A", 100);
// Delete the existing KV and add the KV again
("A", 200);
// Get the reverse map
BiMap<Integer, String> inverse = ();
("{}", (100));Here we mainly use HashBiMap for analysis
Member variables
private static final double LOAD_FACTOR = 1.0D;
// BiEntry is an implementation class for the interface in HashBiMap. There are two BiEntry defined here. One is to use the Key to find the value, and the other is to use the value to find the key.
private transient <K, V>[] hashTableKToV;
private transient <K, V>[] hashTableVToK;
private transient int size;
private transient int mask;
private transient int modCount;
private transient BiMap<V, K> inverse;HashMap does the value corresponding to the unique key value, but Bimap does the unique key value, and the value value must also be unique, so it is convenient to find the value from the key and find the key from the value.
private static final class BiEntry<K, V> extends ImmutableEntry<K, V> {
//The hash value of key
final int keyHash;
//The hash value of value
final int valueHash;
@Nullable
//The variables made for the key linked list point to the next node
<K, V> nextInKToVBucket;
@Nullable
//Variables that are made for the value linked list pointing to the next node
<K, V> nextInVToKBucket;
BiEntry(K key, int keyHash, V value, int valueHash) {
super(key, value);
= keyHash;
= valueHash;
}
}Compare HashMap's Node source code:
static class Node<K,V> implements <K,V> {
//Because the function implemented by HashMap only requires the key to find the value, so the hash value here is the hash value of the key by default
final int hash;
final K key;
V value;
//The linked list in HashMap is just a key linked list, so you only need a variable pointing to the next node
Node<K,V> next;
}Construction method
//Passing in the expected container length
private HashBiMap(int expectedSize) {
(expectedSize);
}You can see that the constructor is private, so there must be a static method constructor in the class that will use this private constructor.
This constructor calls the init method, you can look at the source code of the init method:
private void init(int expectedSize) {
(expectedSize, "expectedSize");
//The closedTableSize method is used to achieve the expected actual value
int tableSize = (expectedSize, 1.0D);
//Initialize the array of key and value storage linked list
= (tableSize);
= (tableSize);
//Initialize mask to the maximum subscript value of the array
= tableSize - 1;
//Initialize modCount value to 0
= 0;
//Initialize size value is 0
= 0;
}Static method constructor
public static <K, V> HashBiMap<K, V> create() {
//Call another create constructor, expect length to be 16
return create(16);
}
public static <K, V> HashBiMap<K, V> create(int expectedSize) {
//Create a HashBiMap with expectedSize directly
return new HashBiMap(expectedSize);
}
public static <K, V> HashBiMap<K, V> create(Map<? extends K, ? extends V> map) {
//Create a biMap of the same length as the incoming map
HashBiMap bimap = create(());
//Then assign all the values passed in map to the new BiMap
(map);
return bimap;
}Add features
There are two types of adding functions, one is the put method and the other is the forcePut method:
public V put(@Nullable K key, @Nullable V value) {
return (key, value, false);
}
public V forcePut(@Nullable K key, @Nullable V value) {
return (key, value, true);
}
It can be seen that these two methods call the put method of this class at the same time, but the third parameter of these two methods is different, one is ture and the other is false. Take a look at the source code of put and see what the third parameter is useful.
private V put(@Nullable K key, @Nullable V value, boolean force) {
//Get the hash value of the passed key
int keyHash = hash(key);
//Get the hash value passed in value
int valueHash = hash(value);
//Search whether this node exists based on the value of the key and its hash value. The seekByKey method is to traverse the linked list on the subscript mapped by this keyhash to search.
oldEntryForKey = (key, keyHash);
if(oldEntryForKey != null && valueHash == && (value, )) {
//If this key value exists and the value is also equal, return this value
return value;
} else {
// Use seekByValue to find out whether this value exists
oldEntryForValue = (value, valueHash);
if(oldEntryForValue != null) {
//If it exists, determine whether force (the third parameter) is false
if(!force) {//Value already exists, so we need to determine whether forced insertion is allowed
//If force (third parameter) is false
//The exception is thrown directly
String newEntry1 = ((value));
throw new IllegalArgumentException((new StringBuilder(23 + ())).append("value already present: ").append(newEntry1).toString());
}
//If force (third parameter) is true, delete this node. This method is to delete it in two-way direction.
(oldEntryForValue);
}
//If the key exists, delete this node
if(oldEntryForKey != null) {
(oldEntryForKey);
}
// Create a BiEntry based on key, value, keyHash, valueHash
newEntry = new (key, keyHash, value, valueHash);
//Insert this node.
(newEntry);
//Insert it, refresh it to see if the capacity needs to be expanded
();
return oldEntryForKey == null?null:;
}
}private void insert(<K, V> entry) {
// Calculate the subscript position of this node in the key container
int keyBucket = & ;
// Make the keynext of the current node point to the current subscript position
= [keyBucket];
// Assign the current node to this subscript position
[keyBucket] = entry;
//value is like key
int valueBucket = & ;
= [valueBucket];
[valueBucket] = entry;
//size plus 1
++;
++;
}Multimap
Supports mapping keys to multiple values without definitionMap<K, List<V>> or Map<K, Set<V>>This form. Implementation classes includeArrayListMultimap, HashMultimap, LinkedListMultimap, TreeMultimap...
// List implementation
ListMultimap<String, Integer> listMultimap = ().arrayListValues().build();
// Collection implementation
SetMultimap<String, Integer> setMultimap = ().hashSetValues().build();
("A", 1);
("A", 2);
("B", 1);
// {A=[1, 2], B=[1, 2]}
("{}", listMultimap);
// [1, 2], if it does not exist, it returns an empty set
("{}", ("A"));
// [1, 2] Remove all values associated with key
List<Integer> valList = ("A");
// Returns the view of a normal map, only supports remove, cannot put, and the original listMultimap will be updated.
Map<String, Collection<Integer>> map = ();HashMultimap constructor
Because his constructor is private, all he will have static method constructors:
public static <K, V> HashMultimap<K, V> create() {
//new a HashMultimap, no value is passed in
return new HashMultimap();
}
public static <K, V> HashMultimap<K, V> create(int expectedKeys, int expectedValuesPerKey) {
//new a HashHultimap, passing in two values, one is the length of the expected key, and the other is the length of the expected value
return new HashMultimap(expectedKeys, expectedValuesPerKey);
}
public static <K, V> HashMultimap<K, V> create(Multimap<? extends K, ? extends V> multimap) {
//Pass in a Multimap value
return new HashMultimap(multimap);
}All three constructors call private constructors, and the source code of private constructors is as follows:
private HashMultimap() {
//New a new map and then hand it over to the parent class for processing
super(new HashMap());
}
private HashMultimap(int expectedKeys, int expectedValuesPerKey) {
//Get a map of expectedKeys and hand it over to the parent class for processing
super((expectedKeys));
(expectedValuesPerKey >= 0);
= expectedValuesPerKey;
}
private HashMultimap(Multimap<? extends K, ? extends V> multimap) {
//Get the map of the length of a multimap and hand it over to the parent class for processing
super((().size()));
(multimap);
}All three private constructors call the parent class's constructor method. Next, look at the constructor source code of the parent class and find that the data structure of the last Multimap is also reflected in the AbstractMapBasedMultimap class, so look at the constructor variables of this class:
//The underlying data structure is a key as an Object class, and the value as a container
private transient Map<K, Collection<V>> map;
//Total Multimap length
private transient int totalSize;
protected AbstractMapBasedMultimap(Map<K, Collection<V>> map) {
(());
= map;
}Implementation of put method
public boolean put(@Nullable K key, @Nullable V value) {
//First check whether this key value exists in the map container.
Collection collection = (Collection)(key);
//If the collection is null, it means that this key value does not exist in the map container
if(collection == null) {
//Create a container based on this key
collection = (key);
// Then put the value in this container
if((value)) {
++;
(key, collection);
return true;
} else {
throw new AssertionError("New Collection violated the Collection spec");
}
//If this container exists, put the value directly into the value
} else if((value)) {
++;
return true;
} else {
return false;
}
}Implementation of get method
public Collection<V> get(@Nullable K key) {
//First check whether this key value exists in the map container.
Collection collection = (Collection)(key);
//If null, create a container for it
if(collection == null) {
collection = (key);
}
//Finding and returning a collection class based on the wrapCollection method of this class
return (key, collection);
}Multiset
Multiset is a new collection type that can add equal elements multiple times, which can be regarded as an unordered list or as a map of stored elements and corresponding number of key-value pairs.[E1: cnt1; E2:cnt2]. Common implementations includeHashMultiset, TreeMultiset, LinkedHashMultiset...
Multiset<String> multiset = ();
("A");
("A");
("B");
// Output: [A x 2, B]
("{}", multiset);
// Total number of elements
("{}", ());
// No repeating the number of elements
("{}", ().size());
// Set element count
("A", 3);
// Get the number of elements
("{}", ("A"));Interface source code
public interface Multiset<E> extends Collection<E> {
//Return the number of elements of the given parameter
int count(@Nullable Object var1);
//Add a specified number of elements to it
int add(@Nullable E var1, int var2);
//Remove the corresponding number of elements
int remove(@Nullable Object var1, int var2);
//Set the number of repetitions of a certain element
int setCount(E var1, int var2);
//Modify the element that matches the original number of repetitions to the new number of repetitions
boolean setCount(E var1, int var2, int var3);
//Put different elements into a Set
Set<E> elementSet();
//Similar to return Set<>. The included Entry supports using getElement() and getCount()
Set<<E>> entrySet();
boolean equals(@Nullable Object var1);
int hashCode();
String toString();
//Return to the iterator
Iterator<E> iterator();
//Judge whether there is an element
boolean contains(@Nullable Object var1);
//Judge whether all elements in the collection exist
boolean containsAll(Collection<?> var1);
//Add elements
boolean add(E var1);
//Delete an element
boolean remove(@Nullable Object var1);
//Delete all elements in the collection
boolean removeAll(Collection<?> var1);
boolean retainAll(Collection<?> var1);
public interface Entry<E> {
E getElement();
int getCount();
boolean equals(Object var1);
int hashCode();
String toString();
}
}The implementation of methods in the Multiset interface is in the AbstractMapBasedMultiset abstract class, and the following is a storage data structure for the AbstractMapBasedMultiset class. Add, remove, count and iterator implementation analysis
Storage data structure
//You can see that the actual storage structure is a Map, the key is the storage element, and the Count type storage is the number of the key element. Take a look at the Count source code:
private transient Map<E, Count> backingMap;
final class Count implements Serializable {
//Record the current number
private int value;
//Construction method, assign value to variable
Count(int value) {
= value;
}
//Get the current number
public int get() {
return ;
}
//Add the specified number, add the value after return the added value
public int getAndAdd(int delta) {
int result = ;
= result + delta;
return result;
}
//Add the specified number, return first, add it
public int addAndGet(int delta) {
return += delta;
}
//Set the current number directly
public void set(int newValue) {
= newValue;
}
//Set the new value first and return this value size
public int getAndSet(int newValue) {
int result = ;
= newValue;
return result;
}
public int hashCode() {
return ;
}
public boolean equals(@Nullable Object obj) {
return obj instanceof Count && ((Count)obj).value == ;
}
public String toString() {
return ();
}
}Construction method
protected AbstractMapBasedMultiset(Map<E, Count> backingMap) {
//The stored map can be any type of map
= (Map)(backingMap);
//Get the current Multiset length
= (long)();
}add method
public int add(@Nullable E element, int occurrences) {
//If you want to add 0
if(occurrences == 0) {
//If there is, return the number of this element, otherwise return 0
return (element);
} else {
(occurrences > 0, "occurrences cannot be negative: %s", new Object[]{(occurrences)});
//Find Count in the map according to the element you want to insert
Count frequency = (Count)(element);
int oldCount;
//If the Count corresponding to the key is null
if(frequency == null) {
//Set the original data to 0
oldCount = 0;
//Add this element and the corresponding Count to the map
(element, new Count(occurrences));
} else {
//Get the original number
oldCount = ();
//Calculate the new number
long newCount = (long)oldCount + (long)occurrences;
(newCount <= 2147483647L, "too many occurrences: %s", new Object[]{(newCount)});
//Add occurences for the Count corresponding to the key
(occurrences);
}
//Add the current size to occurences
+= (long)occurrences;
//Return the original data
return oldCount;
}
}Remove method
public int remove(@Nullable Object element, int occurrences) {
//If you want to delete 0
if(occurrences == 0) {
//Return the current number of this element, if it does not exist in the container, return 0
return (element);
} else {
(occurrences > 0, "occurrences cannot be negative: %s", new Object[]{(occurrences)});
//Get his Count as the key based on the value to be deleted
Count frequency = (Count)(element);
//If the corresponding Count is null, return 0
if(frequency == null) {
return 0;
} else {
//Get the current number
int oldCount = ();
int numberRemoved;
//If the original number is greater than the number you want to delete
if(oldCount > occurrences) {
numberRemoved = occurences;
} else {
//If the original number is less than the number you want to delete
numberRemoved = oldCount;
//Did this element directly in the map
(element);
}
//Set the Count corresponding to this element
(-numberRemoved);
-= (long)numberRemoved;
return oldCount;
}
}
}Count method
public int count(@Nullable Object element) {
// Use the incoming as the key to find the corresponding Count in the map container
Count frequency = (Count)(, element);
//If this Count is empty, return 0, otherwise return the value in Count
return frequency == null?0:();
}Iterator
public Iterator<E> iterator() {
return new ();
}
There is a class in Multiset that implements the Iterator interface:
private class MapBasedMultisetIterator implements Iterator<E> {
final Iterator<<E, Count>> entryIterator;
<E, Count> currentEntry;
int occurencesLeft;
boolean canRemove;
MapBasedMultisetIterator() {
//Get the iterator of the current map container
= ().iterator();
}
//Judge whether there are still elements based on the current iterator
public boolean hasNext() {
return > 0 || ();
}
public E next() {
//If occurrencesLeft is 0, it means that it is now at the beginning, or the previous element has completed
if( == 0) {
//The iterator gets an element downward
= ()();
//Get the current number of elements
= ((Count)()).get();
}
//Because it is to obtain an element, subtract this one
--;
= true;
return ();
}
public void remove() {
();
int frequency = ((Count)()).get();
if(frequency <= 0) {
throw new ConcurrentModificationException();
} else {
if(((Count)()).addAndGet(-1) == 0) {
();
}
$110();
= false;
}
}
}The advantage of this iterator is that storing multiple identical values will not occupy multiple places, but will only occupy 1 place.
Previous recommendations
- "SpringBoot" EasyExcel implements the import and export of millions of data
- "SpringBoot" The most complete SpringBoot commentary in history
- Detailed explanation of Spring Framework IoC Core
- A long article of ten thousand words will take you to explore all the expansion points in Spring
- How to implement a general interface current limiting, heavy-weight and anti-shake mechanism
- A long article of ten thousand words will take you into the underlying data structure of Redis
- Analysis of the most comprehensive principle of volatile keyword