基于红黑树（Red-Black tree）的 NavigableMap 实现；键的排序由构造方法决定：自然排序，Comparator排序；非线程安全（仅改变与现有键关联的值不是结构上的修改）；线程安全的最好方法是在创建的时候包装成线程安全的
1 SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
迭代器与LinkedList相似。
构造器，基本属性：
1 public class TreeMap<K,V> 2 extends AbstractMap<K,V> 3 implements NavigableMap<K,V>, Cloneable, java.io.Serializable 4 { 5 6 //比较器，如果是null就是自然顺序 7 private final Comparator<? super K> comparator; 8 9 //根Entry 10 private transient Entry<K,V> root; 11 12 //Entry个数 13 private transient int size = 0; 14 15 //结构性修改次数 16 private transient int modCount = 0; 17 18 //构造一个空的tree map，使用键的自然顺序，键必须是实现了Comparable， 19 public TreeMap() { 20 comparator = null; 21 } 22 23 //构造一个空的tree map，键按给定的比较器排序， 24 public TreeMap(Comparator<? super K> comparator) { 25 this.comparator = comparator; 26 } 27 28 //构造一个与给定映射具有相同映射关系的新的tree map，该映射根据其键的自然顺序进行排序 29 public TreeMap(Map<? extends K, ? extends V> m) { 30 comparator = null; 31 putAll(m); 32 } 33 34 //构造一个与给定映射具有相同映射关系的新的tree map，该映射根据其m的键的比较器进行排序 35 public TreeMap(SortedMap<K, ? extends V> m) { 36 comparator = m.comparator(); 37 try { 38 buildFromSorted(m.size(), m.entrySet().iterator(), null, null); 39 } catch (java.io.IOException cannotHappen) { 40 } catch (ClassNotFoundException cannotHappen) { 41 } 42 } 43 。。。。。。 44 }
void putAll(Map<? extends K, ? extends V> map)；
V put(K key, V value)；
void fixAfterInsertion(Entry<K,V> x)
关于红黑树的详解可以参考这篇博文： https://www.cnblogs.com/CarpenterLee/p/5503882.html
有些概念的东西可以参考这篇博文： https://blog.csdn.net/sun_tttt/article/details/65445754
例如红黑树的删除，先寻找该结点的后继结点，然后互换值，但不互换颜色，最后再调整！
1 //将指定映射中的所有映射关系复制到此映射中。这些映射关系将替换此映射所有当前为指定映射的所有键所包含的映射关系。 2 public void putAll(Map<? extends K, ? extends V> map) { 3 int mapSize = map.size(); 4 if (size==0 && mapSize!=0 && map instanceof SortedMap) {//map是键有排序的map 5 Comparator<?> c = ((SortedMap<?,?>)map).comparator(); 6 if (c == comparator || (c != null && c.equals(comparator))) { 7 ++modCount; 8 try { 9 buildFromSorted(mapSize, map.entrySet().iterator(), 10 null, null); 11 } catch (java.io.IOException cannotHappen) { 12 } catch (ClassNotFoundException cannotHappen) { 13 } 14 return; 15 } 16 } 17 super.putAll(map);// 18 } 19 20 AbstractMap抽象map的方法 21 public void putAll(Map<? extends K, ? extends V> m) { 22 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) 23 put(e.getKey(), e.getValue()); 24 } 25 26 //将key和value存放在map里，如果map里有相同的key，旧的value被替换 27 public V put(K key, V value) { 28 Entry<K,V> t = root;//根节点 29 if (t == null) {//如果根节点没有值，就把当前值作为根节点 30 compare(key, key); // type (and possibly null) check 31 32 root = new Entry<>(key, value, null); 33 size = 1; 34 modCount++; 35 return null; 36 } 37 int cmp; 38 Entry<K,V> parent; 39 // split comparator and comparable paths 40 Comparator<? super K> cpr = comparator; 41 if (cpr != null) {//比较器不是空 42 do { 43 parent = t; 44 cmp = cpr.compare(key, t.key); 45 if (cmp < 0) 46 t = t.left; 47 else if (cmp > 0) 48 t = t.right; 49 else 50 return t.setValue(value); 51 } while (t != null); 52 } 53 else {//比较器是空，使用自然顺序比较器 54 if (key == null) 55 throw new NullPointerException(); 56 @SuppressWarnings("unchecked") 57 Comparable<? super K> k = (Comparable<? super K>) key; 58 do { 59 parent = t; 60 cmp = k.compareTo(t.key);//key与key的父的key比较 61 if (cmp < 0)//如果小于，节点在t的左侧 62 t = t.left;//将t置为t的左侧节点 63 else if (cmp > 0) 64 t = t.right; 65 else //如果相等，新value替换旧value 66 return t.setValue(value); 67 } while (t != null);//t节点不是空 68 } 69 Entry<K,V> e = new Entry<>(key, value, parent); 70 if (cmp < 0) 71 parent.left = e; 72 else 73 parent.right = e; 74 fixAfterInsertion(e);//红黑树插入新结点后调整 75 size++; 76 modCount++; 77 return null; 78 } 79 80 final int compare(Object k1, Object k2) { 81 return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2) 82 : comparator.compare((K)k1, (K)k2); 83 } 84 85 //红黑树插入新结点后调整 86 private void fixAfterInsertion(Entry<K,V> x) { 87 x.color = RED; 88 89 while (x != null && x != root && x.parent.color == RED) {//x的父的颜色是红色 90 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {//x的父==x的父的父的左侧 91 Entry<K,V> y = rightOf(parentOf(parentOf(x)));//y=x的父的父的右侧 92 if (colorOf(y) == RED) {//y的颜色是红色 93 setColor(parentOf(x), BLACK);//x的父置为黑色 94 setColor(y, BLACK);//y置为黑色 95 setColor(parentOf(parentOf(x)), RED);//x的父的父置为红色 96 x = parentOf(parentOf(x));//x=x的父的父 97 } else {//y的颜色是黑色 98 if (x == rightOf(parentOf(x))) {//x==x的父的右侧 99 x = parentOf(x);//x=x的父 100 rotateLeft(x);//左旋 101 } 102 setColor(parentOf(x), BLACK); 103 setColor(parentOf(parentOf(x)), RED); 104 rotateRight(parentOf(parentOf(x)));//右旋 105 } 106 } else { 107 Entry<K,V> y = leftOf(parentOf(parentOf(x))); 108 if (colorOf(y) == RED) { 109 setColor(parentOf(x), BLACK); 110 setColor(y, BLACK); 111 setColor(parentOf(parentOf(x)), RED); 112 x = parentOf(parentOf(x)); 113 } else { 114 if (x == leftOf(parentOf(x))) { 115 x = parentOf(x); 116 rotateRight(x); 117 } 118 setColor(parentOf(x), BLACK); 119 setColor(parentOf(parentOf(x)), RED); 120 rotateLeft(parentOf(parentOf(x))); 121 } 122 } 123 } 124 root.color = BLACK; 125 } 126 127 //左旋 128 private void rotateLeft(Entry<K,V> p) { 129 if (p != null) { 130 Entry<K,V> r = p.right; 131 p.right = r.left; 132 if (r.left != null) 133 r.left.parent = p; 134 r.parent = p.parent; 135 if (p.parent == null) 136 root = r; 137 else if (p.parent.left == p) 138 p.parent.left = r; 139 else 140 p.parent.right = r; 141 r.left = p; 142 p.parent = r; 143 } 144 } 145 146 //右旋 147 private void rotateRight(Entry<K,V> p) { 148 if (p != null) { 149 Entry<K,V> l = p.left; 150 p.left = l.right; 151 if (l.right != null) l.right.parent = p; 152 l.parent = p.parent; 153 if (p.parent == null) 154 root = l; 155 else if (p.parent.right == p) 156 p.parent.right = l; 157 else p.parent.left = l; 158 l.right = p; 159 p.parent = l; 160 } 161 }
buildFromSorted：（待解决）
1 //采用递归的思路，先构建后节点的左子树，在构建好节点的右子树，最后和节点组合成一个完整的子树。 2 private void buildFromSorted(int size, Iterator<?> it, 3 java.io.ObjectInputStream str, 4 V defaultVal) 5 throws java.io.IOException, ClassNotFoundException { 6 this.size = size; 7 root = buildFromSorted(0, 0, size-1, computeRedLevel(size), 8 it, str, defaultVal); 9 } 10 11 12 /** 13 * Recursive "helper method" that does the real work of the 14 * previous method. Identically named parameters have 15 * identical definitions. Additional parameters are documented below. 16 * It is assumed that the comparator and size fields of the TreeMap are 17 * already set prior to calling this method. (It ignores both fields.) 18 * 19 * @param level the current level of tree. Initial call should be 0.//当前树的级别 20 * @param lo the first element index of this subtree. Initial should be 0.//子树的第一个元素 21 * @param hi the last element index of this subtree. Initial should be //子树的最后一个元素 22 * size-1. 23 * @param redLevel the level at which nodes should be red. 24 * Must be equal to computeRedLevel for tree of this size. 25 */ 26 @SuppressWarnings("unchecked") 27 private final Entry<K,V> buildFromSorted(int level, int lo, int hi, 28 int redLevel, 29 Iterator<?> it, 30 java.io.ObjectInputStream str, 31 V defaultVal) 32 throws java.io.IOException, ClassNotFoundException { 33 /* 34 * Strategy: The root is the middlemost element. To get to it, we 35 * have to first recursively construct the entire left subtree, 36 * so as to grab all of its elements. We can then proceed with right 37 * subtree. 38 * 39 * The lo and hi arguments are the minimum and maximum 40 * indices to pull out of the iterator or stream for current subtree. 41 * They are not actually indexed, we just proceed sequentially, 42 * ensuring that items are extracted in corresponding order. 43 */ 44 45 if (hi < lo) return null; 46 47 int mid = (lo + hi) >>> 1; 48 49 Entry<K,V> left = null; 50 if (lo < mid) 51 left = buildFromSorted(level+1, lo, mid - 1, redLevel, 52 it, str, defaultVal); 53 54 // extract key and/or value from iterator or stream 55 K key; 56 V value; 57 if (it != null) { 58 if (defaultVal==null) { 59 Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next(); 60 key = (K)entry.getKey(); 61 value = (V)entry.getValue(); 62 } else { 63 key = (K)it.next(); 64 value = defaultVal; 65 } 66 } else { // use stream 67 key = (K) str.readObject(); 68 value = (defaultVal != null ? defaultVal : (V) str.readObject()); 69 } 70 71 Entry<K,V> middle = new Entry<>(key, value, null); 72 73 // color nodes in non-full bottommost level red 74 if (level == redLevel) 75 middle.color = RED; 76 77 if (left != null) { 78 middle.left = left; 79 left.parent = middle; 80 } 81 82 if (mid < hi) { 83 Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel, 84 it, str, defaultVal); 85 middle.right = right; 86 right.parent = middle; 87 } 88 89 return middle; 90 }
Entry<K,V> getEntry(Object key)；successor(Entry<K,V> t)
1 //键值对个数 2 public int size() { 3 return size; 4 } 5 6 //是否包含指定的key 7 public boolean containsKey(Object key) { 8 return getEntry(key) != null; 9 } 10 11 final Entry<K,V> getEntry(Object key) { 12 // Offload comparator-based version for sake of performance 13 if (comparator != null) 14 return getEntryUsingComparator(key); 15 if (key == null) 16 throw new NullPointerException(); 17 @SuppressWarnings("unchecked") 18 Comparable<? super K> k = (Comparable<? super K>) key; 19 Entry<K,V> p = root; 20 while (p != null) { 21 int cmp = k.compareTo(p.key); 22 if (cmp < 0) //key<p.key,p=p.left 23 p = p.left; 24 else if (cmp > 0)//key>p.key,p=p.right 25 p = p.right; 26 else //key=p.key,key=p 27 return p; 28 } 29 return null; 30 } 31 总结：比结点值大，向结点右边找，比结点值小，向结点左边找 32 33 //使用指定的比较器查找key 34 final Entry<K,V> getEntryUsingComparator(Object key) { 35 @SuppressWarnings("unchecked") 36 K k = (K) key; 37 Comparator<? super K> cpr = comparator; 38 if (cpr != null) { 39 Entry<K,V> p = root; 40 while (p != null) { 41 int cmp = cpr.compare(k, p.key); 42 if (cmp < 0) 43 p = p.left; 44 else if (cmp > 0) 45 p = p.right; 46 else 47 return p; 48 } 49 } 50 return null; 51 } 52 53 //map是否含有指定的value 54 public boolean containsValue(Object value) { 55 for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) 56 if (valEquals(value, e.value)) 57 return true; 58 return false; 59 } 60 61 //返回treemap的第一个结点，如果treemap是null，则返回null 62 final Entry<K,V> getFirstEntry() { 63 Entry<K,V> p = root; 64 if (p != null) 65 while (p.left != null) 66 p = p.left; 67 return p; 68 } 69 70 //寻找结点后继 71 static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) { 72 if (t == null) 73 return null; 74 else if (t.right != null) { 75 Entry<K,V> p = t.right; 76 while (p.left != null) 77 p = p.left; 78 return p; 79 } else { 80 Entry<K,V> p = t.parent; 81 Entry<K,V> ch = t; 82 while (p != null && ch == p.right) { 83 ch = p; 84 p = p.parent; 85 } 86 return p; 87 } 88 } 89 90 总结：t的右子树不空，则t的后继是其右子树中最小的那个元素。 91 t的右孩子为空，则t的后继是其第一个向左走的祖先。
getCeilingEntry, getFloorEntry, getHigherEntry, getLowerEntry
1 //两个值是否相等 2 static final boolean valEquals(Object o1, Object o2) { 3 return (o1==null ? o2==null : o1.equals(o2)); 4 } 5 6 //指定的key返回value ，如果map不包含key，返回null 7 public V get(Object key) { 8 Entry<K,V> p = getEntry(key); 9 return (p==null ? null : p.value); 10 } 11 12 //查询treemap比较器 13 public Comparator<? super K> comparator() { 14 return comparator; 15 } 16 17 //返回treemap的第一个结点的key，如果是null，抛出错误 18 public K firstKey() { 19 return key(getFirstEntry()); 20 } 21 22 //返回treemap的最后一个结点的key，如果是null，抛出错误 23 public K lastKey() { 24 return key(getLastEntry()); 25 } 26 27 //返回treemap的最后一个结点，如果treemap是null，则返回null 28 final Entry<K,V> getLastEntry() { 29 Entry<K,V> p = root; 30 if (p != null) 31 while (p.right != null) 32 p = p.right; 33 return p; 34 } 35 36 public Map.Entry<K,V> ceilingEntry(K key) { 37 return exportEntry(getCeilingEntry(key)); 38 } 39 40 //返回一个简单的不可变的结点 41 static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) { 42 return (e == null) ? null : 43 new AbstractMap.SimpleImmutableEntry<>(e); 44 } 45 46 AbstractMap类 47 //以指定的结点创建一个相同的结点 48 public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) { 49 this.key = entry.getKey(); 50 this.value = entry.getValue(); 51 } 52 53 public K ceilingKey(K key) { 54 return keyOrNull(getCeilingEntry(key)); 55 } 56 57 static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) { 58 return (e == null) ? null : e.key; 59 } 60 61 62 //指定的key返回结点；如果没有，则返回比key大的最小的结点； 63 //若不存在(即TreeMap中所有节点的键都比key大)，就返回null” 64 final Entry<K,V> getCeilingEntry(K key) { 65 Entry<K,V> p = root; 66 while (p != null) { 67 int cmp = compare(key, p.key); 68 if (cmp < 0) { 69 if (p.left != null) 70 p = p.left; 71 else 72 return p; 73 } else if (cmp > 0) { 74 if (p.right != null) { 75 p = p.right; 76 } else { 77 Entry<K,V> parent = p.parent; 78 Entry<K,V> ch = p; 79 while (parent != null && ch == parent.right) { 80 ch = parent; 81 parent = parent.parent; 82 } 83 return parent; 84 } 85 } else 86 return p; 87 } 88 return null; 89 } 90 91 //指定的key返回结点；如果没有，则返回比key小的最大的结点； 92 //若不存在(即TreeMap中所有节点的键都比key小)，就返回null” 93 final Entry<K,V> getFloorEntry(K key) { 94 Entry<K,V> p = root; 95 while (p != null) { 96 int cmp = compare(key, p.key); 97 if (cmp > 0) { 98 if (p.right != null) 99 p = p.right; 100 else 101 return p; 102 } else if (cmp < 0) { 103 if (p.left != null) { 104 p = p.left; 105 } else { 106 Entry<K,V> parent = p.parent; 107 Entry<K,V> ch = p; 108 while (parent != null && ch == parent.left) { 109 ch = parent; 110 parent = parent.parent; 111 } 112 return parent; 113 } 114 } else 115 return p; 116 117 } 118 return null; 119 } 120 121 //返回比key大的最小的结点； 122 //若不存在(即TreeMap中所有节点的键都比key小)，就返回null” 123 final Entry<K,V> getHigherEntry(K key) { 124 Entry<K,V> p = root; 125 while (p != null) { 126 int cmp = compare(key, p.key); 127 if (cmp < 0) { 128 if (p.left != null) 129 p = p.left; 130 else 131 return p; 132 } else { 133 if (p.right != null) { 134 p = p.right; 135 } else { 136 Entry<K,V> parent = p.parent; 137 Entry<K,V> ch = p; 138 while (parent != null && ch == parent.right) { 139 ch = parent; 140 parent = parent.parent; 141 } 142 return parent; 143 } 144 } 145 } 146 return null; 147 } 148 149 //返回比key小的最大的结点； 150 //若不存在(即TreeMap中所有节点的键都比key大)，就返回null” 151 final Entry<K,V> getLowerEntry(K key) { 152 Entry<K,V> p = root; 153 while (p != null) { 154 int cmp = compare(key, p.key); 155 if (cmp > 0) { 156 if (p.right != null) 157 p = p.right; 158 else 159 return p; 160 } else { 161 if (p.left != null) { 162 p = p.left; 163 } else { 164 Entry<K,V> parent = p.parent; 165 Entry<K,V> ch = p; 166 while (parent != null && ch == parent.left) { 167 ch = parent; 168 parent = parent.parent; 169 } 170 return parent; 171 } 172 } 173 } 174 return null; 175 } 176 177 //删除映射根据指定的key，如果存在 178 public V remove(Object key) { 179 Entry<K,V> p = getEntry(key); 180 if (p == null) 181 return null; 182 183 V oldValue = p.value; 184 deleteEntry(p); 185 return oldValue; 186 } 187 188 //删除所有结点 189 public void clear() { 190 modCount++; 191 size = 0; 192 root = null; 193 } 194 195 //返回此 TreeMap 实例的浅表副本。（键和值本身不被复制。） 196 public Object clone() { 197 TreeMap<?,?> clone; 198 try { 199 clone = (TreeMap<?,?>) super.clone(); 200 } catch (CloneNotSupportedException e) { 201 throw new InternalError(e); 202 } 203 204 // Put clone into "virgin" state (except for comparator) 205 //将clone至于原始状态（除了比较器） 206 clone.root = null; 207 clone.size = 0; 208 clone.modCount = 0; 209 clone.entrySet = null; 210 clone.navigableKeySet = null; 211 clone.descendingMap = null; 212 213 // Initialize clone with our mappings 214 try { 215 clone.buildFromSorted(size, entrySet().iterator(), null, null); 216 } catch (java.io.IOException cannotHappen) { 217 } catch (ClassNotFoundException cannotHappen) { 218 } 219 220 return clone; 221 } 222 223 public Map.Entry<K,V> firstEntry() { 224 return exportEntry(getFirstEntry()); 225 } 226 227 public Map.Entry<K,V> lastEntry() { 228 return exportEntry(getLastEntry()); 229 } 230 231 //弹出第一个结点 232 public Map.Entry<K,V> pollFirstEntry() { 233 Entry<K,V> p = getFirstEntry(); 234 Map.Entry<K,V> result = exportEntry(p); 235 if (p != null) 236 deleteEntry(p); 237 return result; 238 } 239 240 //弹出最后一个结点 241 public Map.Entry<K,V> pollLastEntry() { 242 Entry<K,V> p = getLastEntry(); 243 Map.Entry<K,V> result = exportEntry(p); 244 if (p != null) 245 deleteEntry(p); 246 return result; 247 } 248 249 public Map.Entry<K,V> lowerEntry(K key) { 250 return exportEntry(getLowerEntry(key)); 251 } 252 253 public K lowerKey(K key) { 254 return keyOrNull(getLowerEntry(key)); 255 } 256 257 public Map.Entry<K,V> floorEntry(K key) { 258 return exportEntry(getFloorEntry(key)); 259 } 260 261 public K floorKey(K key) { 262 return keyOrNull(getFloorEntry(key)); 263 } 264 265 public K ceilingKey(K key) { 266 return keyOrNull(getCeilingEntry(key)); 267 } 268 269 public Map.Entry<K,V> higherEntry(K key) { 270 return exportEntry(getHigherEntry(key)); 271 } 272 273 public K higherKey(K key) { 274 return keyOrNull(getHigherEntry(key)); 275 }
遍历treemap的key，value，entry：
1 private transient EntrySet entrySet; 2 private transient KeySet<K> navigableKeySet; 3 private transient NavigableMap<K,V> descendingMap; 4 5 //key集合 6 public Set<K> keySet() { 7 return navigableKeySet(); 8 } 9 10 //key集合（正序：map添加key的正向顺序） 11 public NavigableSet<K> navigableKeySet() { 12 KeySet<K> nks = navigableKeySet; 13 return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this)); 14 } 15 16 //key集合（降序：map添加key的反向顺序） 17 public NavigableSet<K> descendingKeySet() { 18 return descendingMap().navigableKeySet(); 19 } 20 21 //映射的值的集合，顺序和key的顺应一致（正序：map添加key的正向顺序） 22 public Collection<V> values() { 23 Collection<V> vs = values; 24 return (vs != null) ? vs : (values = new Values()); 25 } 26 27 //映射的结点的集合，顺序和key的顺应一致（正序：map添加key的正向顺序） 28 public Set<Map.Entry<K,V>> entrySet() { 29 EntrySet es = entrySet; 30 return (es != null) ? es : (entrySet = new EntrySet()); 31 } 32 33 public NavigableMap<K, V> descendingMap() { 34 NavigableMap<K, V> km = descendingMap; 35 return (km != null) ? km : 36 (descendingMap = new DescendingSubMap<>(this, 37 true, null, true, 38 true, null, true)); 39 } 40 41 //返回此映射的部分视图，其键的范围从 fromKey 到 toKey。 42 如果 fromKey 和 toKey 相等，则返回的映射为空，除非 fromExclusive 和 toExclusive 都为 true。 43 返回的映射受此映射支持，因此返回映射中的更改将反映在此映射中，反之亦然。 44 返回的映射支持此映射支持的所有可选映射操作。 45 如果试图在返回映射的范围之外插入一个键，或者构造一个任一端点位于其范围之外的子映射， 46 则返回的映射将抛出 IllegalArgumentException。 47 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, 48 K toKey, boolean toInclusive) { 49 return new AscendingSubMap<>(this, 50 false, fromKey, fromInclusive, 51 false, toKey, toInclusive); 52 } 53 54 //返回此映射的部分视图，其键小于（或等于，如果 inclusive 为 true）toKey。 55 返回的映射受此映射支持，因此返回映射中的更改将反映在此映射中，反之亦然。 56 返回的映射支持此映射支持的所有可选映射操作。 57 如果试图在返回映射的范围之外插入一个键，则返回的映射将抛出 IllegalArgumentException。 58 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) { 59 return new AscendingSubMap<>(this, 60 true, null, true, 61 false, toKey, inclusive); 62 } 63 64 //同上 65 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) { 66 return new AscendingSubMap<>(this, 67 false, fromKey, inclusive, 68 true, null, true); 69 } 70 71 public SortedMap<K,V> subMap(K fromKey, K toKey) { 72 return subMap(fromKey, true, toKey, false); 73 } 74 75 76 public SortedMap<K,V> headMap(K toKey) { 77 return headMap(toKey, false); 78 } 79 80 public SortedMap<K,V> tailMap(K fromKey) { 81 return tailMap(fromKey, true); 82 } 83 84 //替换指定key，和值的值 85 @Override 86 public boolean replace(K key, V oldValue, V newValue) { 87 Entry<K,V> p = getEntry(key); 88 if (p!=null && Objects.equals(oldValue, p.value)) { 89 p.value = newValue; 90 return true; 91 } 92 return false; 93 } 94 95 //替换指定key的值 96 @Override 97 public V replace(K key, V value) { 98 Entry<K,V> p = getEntry(key); 99 if (p!=null) { 100 V oldValue = p.value; 101 p.value = value; 102 return oldValue; 103 } 104 return null; 105 } 106 107 //类似ArrayList 108 @Override 109 public void forEach(BiConsumer<? super K, ? super V> action) { 110 Objects.requireNonNull(action); 111 int expectedModCount = modCount; 112 for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) { 113 action.accept(e.key, e.value); 114 115 if (expectedModCount != modCount) { 116 throw new ConcurrentModificationException(); 117 } 118 } 119 }
replaceAll：替换所有的值
1 @Override 2 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 3 Objects.requireNonNull(function); 4 int expectedModCount = modCount; 5 6 for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) { 7 e.value = function.apply(e.key, e.value); 8 9 if (expectedModCount != modCount) { 10 throw new ConcurrentModificationException(); 11 } 12 } 13 }
demo：
1 public static void main(String[] args) { 2 TreeMap<String,Object> treeMap= new TreeMap(); 3 treeMap.put("1",1); 4 treeMap.put("2",3); 5 treeMap.put("3",3); 6 treeMap.put("4",3); 7 treeMap.put("5",3); 8 9 BiFunction ff = new BiFunction<String, Integer, Object>() { 10 @Override 11 public Integer apply(String str,Integer v) { 12 return 2; 13 } 14 }; 15 treeMap.replaceAll(ff); 16 System.out.println(treeMap); 17 }
结果：
1 {1=2, 2=2, 3=2, 4=2, 5=2}
TreeMap有Values、EntrySet、KeySet、PrivateEntryIterator、EntryIterator、ValueIterator、KeyIterator、DescendingKeyIterator、NavigableSubMap、AscendingSubMap、DescendingSubMap、SubMap、Entry共十三个内部类。可以参考这篇博客：https://blog.csdn.net/jzhf2012/article/details/8540713