Reading good source code is one of the most important ways to improve your programming skills. If there is a wrong place, welcome to correct ~ reproduced please indicate the source www.imooc.com/u/125243.
preface
Come straight to the point, there are mountains beyond mountains…
A brief introduction to TreeMap and the class diagram.
Well, a TreeMap is an ordered set of key-value pairs (this introduction is simple enough).
TreeMap implements the NavigableMap interface, which in turn inherits the Map interface indirectly through sortedMap. NavigableMap defines a set of navigation methods that are different from HashMap, but also sequential.
The similarities and differences between TreeMap and HashMap will probably be mentioned in each of the following chapters.
If you are not familiar with HashMap, you can check out the following hashmap-jdk1.8 and the red-black tree application in HashMap -jdk1.8.
Next, please sit back and get ready to go.
basis
As always, if you don’t want to start with a bunch of complicated methods, you should start with variables.
Member variables
/** * if the treemap is null, the natural order is adopted. ** @serial */ Private Final comparator <? super K> comparator; Private transient Entry<K,V> root; /** * private TRANSIENT int size = 0; /** * private TRANSIENT int modCount = 0;Copy the codeFrom the variables, you can easily see that Treemap is somewhat similar to a HashMap, except that
- HashMap 1, hash bucket + linked list/red-black tree implementation 2, unordered
- TreeMap (1) is implemented based on a red-black tree (2) is ordered by a specified comparator or natural order
Let’s look at the constructors
The constructor
/** * All keys must implement the Comparable interface. ** * All keys must be Comparable. {@code k1.compareTo(k2)} cannot throw {@code ClassCastException} * If you try to put a key in the map that violates the constraint, such as: Public TreeMap() {@code */ public TreeMap() {comparator = null; } /** * Constructs an empty/new map for the given comparator * All keys inserted into the map must be comparable by the comparator * (since the comparator is provided, Comparable) * * * @param comparator If null, use natural order */ public TreeMap(comparator <? super K> comparator) { this.comparator = comparator; } /** * Construct an empty treemap based on the natural order of the given map and key. * * The time complexity of the method is N *log(n) * * @param m Map * @throws ClassCastException If the key does not have comparability or collation, throw this exception * @throws NullPointerException Throws NPE */ public TreeMap(map <? extends K, ? extends V> m) { comparator = null; PutAll (m); } /** * given a sortedMap, Construct a new Treemap * * method using the same sort method to run at line limited time * * @param m sortedMap * @throws NullPointerException if the specified map is null TreeMap(SortedMap<K, ? Extends V> m) {// get sortedMap's comparator. Try {// Call buildFromSorted to store m buildFromSorted(m.slist (), m.tryset ().iterator(), null, null); } catch (java.io.IOException cannotHappen) { } catch (ClassNotFoundException cannotHappen) { } }Copy the codeOne of the most impressive constructors is the constraint on the key
If a comparator is not specified, the key stored in the map must implement the Comparable interface
The purpose of this constraint is to use comparability to maintain the sequential nature of Treemap.
The above constructors, putAll and buildFromSorted, are not followed up for detailed analysis and are presented in the functional methods.
Red and black tree
The TreeMap code is essentially the same as the HashMap code, but the structure of the code is still quite different. (I think TreeMap’s red-black tree code is much more readable than HashMap’s.)
Node definition
Again, we use a static inner class to define tree nodes, similar to the definition in HashMap, but relatively straightforward without much analysis.
static final class Entry<K,V> implements Map.Entry<K,V> { K key; V value; Entry<K,V> left; Entry<K,V> right; Entry<K,V> parent; boolean color = BLACK; /** * Create a new cell node based on the given key/value/parent (black) * subtree null ** / Entry(K key, V value, Entry<K,V> parent) {this.key = key; this.value = value; this.parent = parent; } /** * return key ** @return key */ public K getKey() {return key; } /** * @return the value associated with the key */ public V getValue() {return value; Public V setValue(V value) {V oldValue = this.value; this.value = value; return oldValue; } /** * public Boolean equals(Object o) {if (! (o instanceof Map.Entry)) return false; Map.Entry<? ,? > e = (Map.Entry<? ,? >)o; return valEquals(key,e.getKey()) && valEquals(value,e.getValue()); } /** * hashcode */ public int hashCode() { int keyHash = (key==null ? 0 : key.hashCode()); int valueHash = (value==null ? 0 : value.hashCode()); return keyHash ^ valueHash; } /** * toString */ public String toString() { return key + "=" + value; }}Copy the codeleft-handed
Left-handedness is similar to that of a HashMap, except that the HashMap entry has a root to point to the root node, whereas in TreeMap root is a member variable.
Private void rotateLeft(Entry<K,V> p) {// Null ignores if (p! <K,V> r = p.right; // replace the left subtree of r with the right subtree of p. // If the left subtree of r exists // then the parent of the left subtree of r points to p if (r.eft! = null) r.left.parent = p; // the parent of r refers to the parent of P. // In essence, r replaces p. // If (p.parent == null) // then r is the root node root = r; Else if (p.parent.left == p) // If the parent of p exists and p is the left subtree // set r to the left subtree p.parent.left = r; Else // Otherwise set to right subtree p.parent.right = r; //p becomes the left subtree of r. // Modify the reference p.parent = r; }}Copy the codeRight hand
Private void rotateRight(Entry<K,V> p) {// Null ignores if (p! L Entry<K,V> l = p. eft; // replace the left subtree of p with the right subtree of L. P if (l.right! = p if (l.right! = p if (l.right! = null) l.right.parent = p; // change the position of l and p l.parent = p.parent; If (p.parent == null) // If (p.parent == null) // Then l is root = l; Else if (p.parent.right == p) // If the parent of p exists and p is the original right subtree // Set l after p to the right subtree p.parent.right = l; // Set it to the left subtree else p.arent. left = l; // modify reference l.light = p; p.parent = l; }}Copy the codeInsert the balance
The implementation of the insert balancing method is what I call a more readable method than HashMap. TreeMap encapsulates node relational operations as separate methods, such as getting a parent node, a left subtree, a right subtree, and so on. This makes the meaning very clear, and it is easy to confuse the source code if it is referenced like a HashMap.
/** From CLR */ private void fixAfterInsertion(Entry<K,V> x) { //x exists and c is not root and the parent of x is red while (x! = null && x ! Color == RED) {if (parentOf(x) == leftOf(parentOf(x)))) {// Fetch the right child tree of the grandfather node Entry<K,V> y = rightOf(parentOf(parentOf(x))); If (colorOf(y) == RED) {setColor(parentOf(x), BLACK); setColor(parentOf(x), BLACK); SetColor (y, BLACK); // The grandfather node becomes RED setColor(parentOf(parentOf(x)), RED); ParentOf (parentOf(x)); } else {// if (x == rightOf(parentOf(x))) {//x references to parent x = parentOf(x); / / sinistral rotateLeft (x); } // Change the parent node of x to BLACK setColor(parentOf(x), BLACK); // the parent node of x becomes RED setColor(parentOf(parentOf(x)), RED); / / right rotateRight (parentOf (parentOf (x))); }} else {Entry<K,V> y = leftOf(parentOf(parentOf(x))); If (colorOf(y) == RED) {setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else {if (x == leftOf(parentOf(x))) {x = parentOf(x); / / right rotateRight (x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); / / sinistral rotateLeft (parentOf (parentOf (x))); } } } root.color = BLACK; }Copy the codeDelete the balance
Delete balance is similar, code writing is more standard, in order to highlight my lazy, I will not add comments, the code posted, predestiny people to understand.
/** From CLR */ private void fixAfterDeletion(Entry<K,V> x) { while (x ! = root && colorOf(x) == BLACK) { if (x == leftOf(parentOf(x))) { Entry<K,V> sib = rightOf(parentOf(x)); if (colorOf(sib) == RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateLeft(parentOf(x)); sib = rightOf(parentOf(x)); } if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { setColor(sib, RED); x = parentOf(x); } else { if (colorOf(rightOf(sib)) == BLACK) { setColor(leftOf(sib), BLACK); setColor(sib, RED); rotateRight(sib); sib = rightOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(rightOf(sib), BLACK); rotateLeft(parentOf(x)); x = root; } } else { // symmetric Entry<K,V> sib = leftOf(parentOf(x)); if (colorOf(sib) == RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateRight(parentOf(x)); sib = leftOf(parentOf(x)); } if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { setColor(sib, RED); x = parentOf(x); } else { if (colorOf(leftOf(sib)) == BLACK) { setColor(rightOf(sib), BLACK); setColor(sib, RED); rotateLeft(sib); sib = leftOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(leftOf(sib), BLACK); rotateRight(parentOf(x)); x = root; } } } setColor(x, BLACK); }Copy the codeTreeMap’s red-black tree code is intended to show that TreeMap’s implementation is more readable than HashMap, but it is essentially the same, so we will not go into details about the process of inserting and removing balances. If you are interested in using a HashMap, you can use a red black tree to create a HashMap.
Function method
Let’s take a look at the methods and see how they are implemented internally.
put
TreeMap stores the specified key-value pairs in TreeMap. Unlike HashMap, which scatters elements into hash buckets using HashCode, TreeMap stores elements in a red-black tree in a comparator/natural order to ensure order.
Let’s start with the PUT method.
/** * store the specified key pair * if the specified key exists, * * @param key key with which the specified value is to be associated * @param value value to be Associated with the specified key * * @return value {@code key} @throws ClassCastException If the specified key is not comparable. * @throws NullPointerException NPE * */ public V put(K key, V value) {// Root Entry<K,V> t = root; // If (t == null) {// If (t == null) {// If (t == null) {// If (t == null); // type (and possibly null) check // Initializing a node root = new Entry<>(key, value, null); //size + 1 size = 1; // change count + 1 modCount++; // return null return null; } // If TreeMap is not null // define the comparison value int CMP; // Define the parent Entry<K,V> parent; // Separate the Comparator and compare the path Comparator<? super K> cpr = comparator; // If there is a Comparator if (CPR! Do {parent = t; do {parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; Else // If the same key is found, return t.setValue(value); } while (t ! = null); If (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; Do {parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t ! = null); } // Create new node Entry<K,V> e = new Entry<>(key, value, parent); If (CMP < 0) parent. Left = e; else parent.right = e; // Insertion insertion (e); //size + 1 size++; // change count + 1 modCount++; // return null; // Return null; }Copy the codeAfter looking at the put, read the putAll in the unparsed constructor as well.
/** * Stores the specified map elements to the current treemap ** @param map map * @throws ClassCastException Key is invalid (see constructor section) * @throws NullPointerException NullPointerException NullPointerException NullPointerException NullPointerException NPE */ Public void putAll(map <? extends K, ? Extends V> map) {int mapSize = map.size(); // Treemap is empty and the specified map is not empty and the map is collatable. =0 &&map instanceof SortedMap) {// get the Comparator<? > c = ((SortedMap<? ,? >)map).comparator(); / / determine whether Comparator is consistent with the current if (c = = Comparator | | (c! = null &&c.quals (comparator)) {// count + 1 ++modCount; BuildFromSorted (mapSize, map.entryset ().iterator(), null, null); } catch (java.io.IOException cannotHappen) { } catch (ClassNotFoundException cannotHappen) { } return; }} // Call putAll super.putall (map); }Copy the codeIf (size==0 && mapSize!) if (size==0 && mapSize!) if (size==0 && mapSize! =0 && map Instanceof SortedMap). If it is, it takes out the comparator and calls buildFromSorted. If it is not, it calls putAll.
Two questions remain: what does buildFromSorted and putAll do to store collection elements?
The following step by step analysis, starting from the parent class putAll.
/** * {@inheritdoc} ** I'm not good at translating. * * @implSpec * This implementation iterates over the specified map's * <tt>entrySet()</tt> collection, and calls this map's <tt>put</tt> * operation once for each entry returned by the iteration. * * <p>Note that this implementation throws an * <tt>UnsupportedOperationException</tt> if this map does not support * the <tt>put</tt> operation and the specified map is nonempty. * * @throws UnsupportedOperationException {@inheritDoc} * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} * @throws IllegalArgumentException {@inheritDoc} */ public void putAll(Map<? extends K, ? extends V> m) { for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) put(e.getKey(), e.getValue()); }Copy the codeIs that obvious? If (size==0 && mapSize! =0 && map instanceof SortedMap), then the putAll method of the parent class is called: through a loop, elements are placed one by one in Treemap. Put here is the put method analyzed at the beginning of this chapter.
So, that leaves us with the question, if this is true, what does buildFromSorted do?
/** ** Linear time tree construction algorithm (based on sorting data) * can accept key-value pairs from iterators/streams * There are many ways to enter, but it still seems better than the other options (PS: I don't know what the other options are) ** the method accepts 4 formats: * * 1) Map.Entries iterator (it! = null, defaultVal == null). = null, defaultVal ! (it == null, defaultVal == NULL). * 4) Serialized key stream (it == null, defaultVal! * * @param size key/or number of key-value pairs * @param it is not null. New entries are created through this iterator * @param STR is not null, and new entries are created through serialized streams * to be precise, @param defaultVal is not null, which is the default value. * @throws java.io.IOException. This does not happen if STR is null * @throws ClassNotFoundException It is possible to throw this exception when reading an object. This does not happen if STR is null */ private void buildFromSorted(int size, Iterator<? > it, java.io.ObjectInputStream str, V defaultVal) throws java.io.IOException, ClassNotFoundException {// set size this.size = size; ComputeRedLevel computeRedLevel computs the level of a complete binary tree based on the number of nodes. Root = buildFromSorted(0, 0, size-1, computeRedLevel(size), it, STR, defaultVal); } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - / * * * * the red node hierarchy (fully binary tree hierarchy) * * * / private starting from 0 static int computeRedLevel(int sz) { int level = 0; for (int m = sz - 1; m >= 0; m = m / 2 - 1) level++; return level; } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - / / / * * * is the actual implementation of buildFromSorted method recursion, the real implementation method (before is to help the method). * compare with previous methods, The same parameter name has the same meaning * Added parameter description below * * It is assumed that the tree graph comparator and size fields are set before calling this method. (It ignores these two fields). * * @param level Specifies the current tree level. The initial call should be 0. * @param LO subtree's first node index. The initialization should be 0. * @param hi subtree tail node index. The initialization should be size-1 * @param redLevel the node should be the redLevel, Must be equal to size and computeRedLevel */ @suppressWarnings ("unchecked") Private final Entry<K,V> buildFromSorted(int level, int lo, int hi, int redLevel, Iterator<? > it, Java. IO. ObjectInputStream STR, V defaultVal) throws Java. IO. IOException, ClassNotFoundException {/ * * strategies: The root node is the element closest to the middle node. To get it, first we have to recursively build the entire left subtree to grab all the elements * then we can move on to the right subtree * * The lo and li arguments are extracting the minimum and maximum indices of the iterator/stream for the current subtree, * they don't really have indexes, we just process them sequentially, Make sure items are processed in the appropriate order. If (hi < lo) return null; //mid=(lo+hi)/2; Int mid = (lo + hi) >>> 1; // Entry<K,V> left = null; If (lo < mid) left = buildFromSorted(level+1, LO, mid, redLevel, it, STR, defaultVal); if (lo < mid) left = buildFromSorted(level+1, LO, mid, redLevel, it, STR, defaultVal); // extract key and/or value from iterator or stream; V value; // Use iterator if (it! If (defaultVal==null) {map.entry <? ,? > entry = (Map.Entry<? ,? >)it.next(); key = (K)entry.getKey(); value = (V)entry.getValue(); } else {// have default key = (K)it.next(); value = defaultVal; }} else {// use stream // use stream key = (K) str.readObject(); value = (defaultVal ! = null ? defaultVal : (V) str.readObject()); } // Create node Entry<K,V> middle = new Entry<>(key, value, null); // Color nodes in non-full bottommost level red if (level == redLevel) middle. Color = red; If (left! = null) {// middle. Left = left; // Modify reference left. Parent = middle; } if (mid < hi) {Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel, it, STR, defaultVal); middle.right = right; right.parent = middle; } return middle; return middle; }Copy the codeThis concludes the analysis of TreeMap put related methods, with a few points to comb through
- 1.
putMethod Insert balance is performed after elements are placed in a specific position in a red-black tree according to the comparator/natural order - 2,
putAllThere are actually two cases, one is iterating out the element and calling the superclassputThe other is the callbuildFromSortedComplete the TreeMap construction - 3, call
buildFromSortedThe input parameter must beSortedMap(There are other restrictions, see the if condition above) - 4. BuildFromSorted has one
computeRedLevel, is used to compute the red node hierarchy. - 5. Practical implementation
buildFromSortedMethod, is a recursive call process, through middle, recursive construction of left and right subtrees to complete the construction of the entire tree.
Go On, and here’s how to remove.
remove
/** * Removes the specified key-value pair from treemap based on the specified key if it exists ** @param key The key of the key-value pair to be removed * @return and the old value associated with {@code key} * if {@code key}. Throws ClassCastException. The specified key cannot be compared with the key in the map. * @throws NullPointerException when the key specified by the Treemap is null and the natural ordering/Comparator does not allow null keys. Discard NPE */ public V remove(Object key) {// Obtain the specified element node Entry<K,V> p = getEntry(key); If (p == null) return null; V oldValue = p.value; // Delete element deleteEntry(p); // return oldValue; }Copy the codeThe remove method body contains two key calls, getEntry and deleteEntry.
** @throws ClassCastException if the specified key cannot be compared with the map. Throws this exception * @throws NullPointerException when the specified key is null and the Treemap uses natural sorting /comparator to exclude null keys. NPE */ final Entry<K,V> getEntry(Object key) {// Offload comparator-based version for sake of performance // If (comparator! GetEntryUsingComparator return getEntryUsingComparator(key); if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; Entry<K,V> p = root; // While (p! = null) {// int CMP = k.compareTo(p.key); If (CMP < 0) p = p.left; else if (cmp > 0) p = p.right; Else // If the comparison results are equal, return p; } return null; } // continue with the getEntryUsingComparator method /** * get the version of the element by using the comparator. Separate it from genEntry (neatness and performance beautiful~) * (It's not worth it for most methods, which rely less on comparator performance, but here it is, It is worth it) */ Final Entry<K,V> getEntryUsingComparator(Object key) {@suppressWarnings ("unchecked") K K = (K) key; // Get the Comparator<? super K> cpr = comparator; if (cpr ! = null) { Entry<K,V> p = root; // Loop from the root while (p! Int CMP = cpr.compare(k, p.key); If (CMP < 0) p = p; if (CMP < 0) p = p; else if (cmp > 0) p = p.right; else return p; } } return null; }Copy the codeFind the element method is relatively easy to understand, but can not miss the deleteEntry after the search delete method, in fact, here deleteEntry is a red and black tree node delete operation, before also seems to have analyzed, here or the code and comments posted, maybe you like me is also a little lazy? Good lazy people innovate because they don’t want to reinvent the wheel.)
Private void deleteEntry(Entry<K,V> p) {// first, modCount++; size--; If strictly internal, copy p's elements to P and then make p to succeed. // If strictly internal, copy P's elements to P, Then point p to the case where both the left and right subtrees exist. = null && p.right ! Succeeded (p) {// Get Entry<K,V> s = succeeded (p); // The associated value of the post-node is assigned to p.key = s.key; p.value = s.value; //p refers to s p = s; } // p has 2 children // Start fixup at replacement node, if it exists. // Get Entry<K,V> replacement = (p.lift! = null ? p.left : p.right); // Determine whether the replacement node exists if (replacement! = null) {// Link replacement to parent // modify parent reference replacement. Parent = p.parent; If (p arent == null) root = replacement; if (p arent == null) root = replacement; Else if (p == p.parent.left) // Then change the reference of the left child tree of the parent node to the new replacement node p.parent.left = replacement; Else // Otherwise modify the right subtree reference p.prent. right = replacement; // Null out links so they are OK to use by fixAfterDeletion. So that the later delete balance processing p.left = P.light = p.arent = null; If (p.color == BLACK) fixAfterDeletion(replacement); // Fix replacement // If p is BLACK, delete deletion (replacement). // If the replacement node does not exist, } else if (p.parent == null) {// return if we are the only node. } else {// No children. Use self as phantom replacement and unlink. If (p.color == BLACK) // If (p.color == BLACK) // If (p.color == BLACK), delete fixAfterDeletion(p); // the parent of p exists // determine whether p is the left or right subtree of the parent node // modify the reference if (p.parent! = null) { if (p == p.parent.left) p.parent.left = null; else if (p == p.parent.right) p.parent.right = null; p.parent = null; Succeeded /** * Returns the succeeded nodes if they exist, or null if they do not */ static <K,V> treemap. Entry<K,V> t (Entry<K,V> t) {//t is null, If (t == null) return null; Else if (t. light! = null) {// Get the right subtree Entry<K,V> p = t. light; // loop through and loop through the left subtree, fetching the last while (p.left! = null) p = p.left; return p; } else {// The left subtree exists // The parent node Entry<K,V> p = t.parent; //ch points to t Entry<K,V> ch = t; // loop (as long as the parent exists and ch(t) is the right subtree of the parent) while (p! = null && ch == p.right) { ch = p; p = p.parent; } return p; If t is the right subtree of the parent node, then t is the right subtree of the parent node. If t is the right subtree of the parent node, then t is the right subtree of the parent nodeCopy the codeget
(it’s even…
If you look closely at the remove chapter, you can actually skip this chapter.
Because GET is a facade method, the actual implementation is also provided by getEntry.
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
Copy the codecontainsKey/containsValue
Check whether a TreeMap has a key or value.
Check whether the element is null based on the key.
Value is not the same as key, but the logic is clear. First fetch the first element, then loop over, compare the specified value with the value of each element, return if the same.
public boolean containsKey(Object key) { return getEntry(key) ! = null; } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- public Boolean containsValue (Object value) {/ / iteration judgment for (Entry > < K, V e = getFirstEntry(); e ! = null; e = successor(e)) if (valEquals(value, e.value)) return true; return false; }Copy the codeforEach
The loop iterates and takes the specified action for each element.
The loop iteration is the same as containsValue, except that containsValue performs a judgment on each element, while forEach performs an action on each element.
@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
int expectedModCount = modCount;
for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
action.accept(e.key, e.value);
if (expectedModCount != modCount) {
throw new ConcurrentModificationException();
}
}
}
Copy the codeentrySet
I wasn’t going to analyze this, because the full analysis is too long.
But since it is so long, still care about this section ~
We use entrySet a lot. There’s nothing interesting about entrySet. It’s very simple. There’s an entrySet variable inside, and if it’s not initialized, it’s new, if it’s initialized, it’s returned.
public Set<Map.Entry<K,V>> entrySet() { EntrySet es = entrySet; return (es ! = null) ? es : (entrySet = new EntrySet()); }Copy the codeThe EntrySet data structure is an inner class of TreeMap that inherits AbstractSet and implements related methods.
Treemap.java 1057 line //Entry defines class EntrySet extends AbstractSet< map. Entry<K,V>> {/** * returns iterator */ public Iterator< map.entry <K,V>> Iterator () {getFirstEntry < map.entry <K,V>> Iterator () {getFirstEntry < map.entry <K,V>> Iterator () {getFirstEntry < map.entry <K,V>> Iterator () {getFirstEntry < map.entry <K,V>> Iterator () {getFirstEntry < map.entry <K,V>> Iterator () { //TreeMap 1238 line return new EntryIterator(getFirstEntry()); Public Boolean contains(Object o) {if (! (o instanceof Map.Entry)) return false; Map.Entry<? ,? > entry = (Map.Entry<? ,? >) o; Object value = entry.getValue(); Entry<K,V> p = getEntry(entry.getKey()); return p ! = null && valEquals(p.getValue(), value); } /** * public Boolean remove(Object o) {if (! (o instanceof Map.Entry)) return false; Map.Entry<? ,? > entry = (Map.Entry<? ,? >) o; Object value = entry.getValue(); Entry<K,V> p = getEntry(entry.getKey()); if (p ! = null && valEquals(p.getValue(), value)) { deleteEntry(p); return true; } return false; } public int size() { return TreeMap.this.size(); } public void clear() { TreeMap.this.clear(); } public Spliterator<Map.Entry<K,V>> spliterator() { return new EntrySpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0); }}Copy the codeEntrySet is an entrySet analysis of entrySet and entrySet is an entrySet analysis of entrySet.
It’s getting late. Let’s get off and go to bed.
conclusion
Well, there’s no summary, it’s all up there.
Slip away, slip away. Give it a thumbs up.