1.TreeMap的底层是使用红黑树实现的,支持排序,实现了map接口,键值对形式。
2.构造器:
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
/**
* The comparator used to maintain order in this tree ma***ull if it uses the natural ordering of its keys.
*
* @serial
*/
private final Comparator<? super K> comparator;//比较器,由于基于红黑树实现,所以本身满足条件;
private transient Entry<K,V> root;
/**
* The number of entries in the tree
*/
private transient int size = 0;
/**
* The number of structural modifications to the tree.
*/
private transient int modCount = 0;
/**
* Constructs a new, empty tree map, using the natural ordering of its
* keys. All keys inserted into the map must implement the {@link
* Comparable} interface. Furthermore, all such keys must be
* <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
* a {@code ClassCastException} for any keys {@code k1} and
* {@code k2} in the map. If the user attempts to put a key into the
* map that violates this constraint (for example, the user attempts to
* put a string key into a map whose keys are integers), the
* {@code put(Object key, Object value)} call will throw a
* {@code ClassCastException}.
*/
public TreeMap() {
comparator = null;
}
/**
* Constructs a new, empty tree map, ordered according to the given
* comparator. All keys inserted into the map must be <em>mutually
* comparable</em> by the given comparator: {@code comparator.compare(k1,
* k2)} must not throw a {@code ClassCastException} for any keys
* {@code k1} and {@code k2} in the map. If the user attempts to put
* a key into the map that violates this constraint, the {@code put(Object
* key, Object value)} call will throw a
* {@code ClassCastException}.
*
* @param comparator the comparator that will be used to order this map.
* If {@code null}, the {@linkplain Comparable natural
* ordering} of the keys will be used.
*/
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
/**
* Constructs a new tree map containing the same mappings as the given
* map, ordered according to the <em>natural ordering</em> of its keys.
* All keys inserted into the new map must implement the {@link
* Comparable} interface. Furthermore, all such keys must be
* <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
* a {@code ClassCastException} for any keys {@code k1} and
* {@code k2} in the map. This method runs in n*log(n) time.
*
* @param m the map whose mappings are to be placed in this map
* @throws ClassCastException if the keys in m are not {@link Comparable},
* or are not mutually comparable
* @throws NullPointerException if the specified map is null
*/
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
/**
* Constructs a new tree map containing the same mappings and
* using the same ordering as the specified sorted map. This
* method runs in linear time.
*
* @param m the sorted map whose mappings are to be placed in this map,
* and whose comparator is to be used to sort this map
* @throws NullPointerException if the specified map is null
*/
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException | ClassNotFoundException cannotHappen) {
}
}
上面使用了比较器,这个比较器会在put方法中经常使用,调用compare方法,treeMap的核心就在这边。如果没有传入比较器,那么就将待比较的两个对象转型,也就是默认实现了Comparable<? super K>接口,也就是使用jvm自带的比较器去比较两个对象。如果传入了比较器,那么就是用比较器的compare方法去比较两个对象;
put方法:
compare()方法: