您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
这期内容当中小编将会给大家带来有关TreeMap怎么在Java中使用，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。
Java主要应用于：1. web开发；2. Android开发；3. 客户端开发；4. 网页开发；5. 企业级应用开发；6. Java大数据开发；7.游戏开发等。
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable
public interface NavigableMap<K,V> extends SortedMap<K,V> {TreeMap
继承了AbstractMap
实现了NavigableMap，而NavigableMap接口继承了SortedMap接口,SortedMap接口表示其实现类是一个有序集合
实现了Cloneable，所以支持对象克隆
实现了Serializable，所以支持对象序列化
comparator
/** * The comparator used to maintain order in this tree map, or * null if it uses the natural ordering of its keys. * * @serial */ private final Comparator<? super K> comparator;
外部指定的比较器。在创建TreeMap对象时可以指定。如果指定了比较器，则TreeMap插入键值对时，按照comparator比较排序。
root
private transient Entry<K,V> root;
root指代TreeMap底层红黑树的根节点。 root的类型Entry<K,V>就是红黑树节点的类型。
红黑树数据结构的实现就依赖于Entry<K,V>
size
/** * The number of entries in the tree */ private transient int size = 0;
表示TreeMap集合中键值对个数。
modCount
/** * The number of structural modifications to the tree. */ private transient int modCount = 0;
表示TreeMap集合被结构化修改的次数。用于迭代器迭代过程中检测集合是否被结构化修改，若是，则fail-fast。
Entry<K,V>
Entry<K,V>是红黑树节点的代码实现，是实现红黑树数据结构的基础。
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;
/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
/**
* Returns the key.
*
* @return the key
*/
public K getKey() {
return key;
}
/**
* Returns the value associated with the key.
*
* @return the value associated with the key
*/
public V getValue() {
return value;
}
/**
* Replaces the value currently associated with the key with the given
* value.
*
* @return the value associated with the key before this method was
* called
*/
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());
}
public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
public String toString() {
return key + "=" + value;
}
}成员变量
K key,V value分别是TreeMap集合中存储的键值对的键和值
Entry<K,V> left 代表当前节点的左子节点
Entry<K,V> right 代表当前节点的右子节点
Entry<K,V> parent 代表当前节点的父节点
boolean color 代表当前节点的颜色，默认是黑色，为true
构造器
Entry<K,V>只提供了一个构造器 Entry(K key, V value, Entry<K,V> parent)
即：创建一个红黑树节点，只需要指定其存储的键值信息，以及其父节点引用。不需要指定左孩子和右孩子，以及颜色。
成员方法
提供了getKey()方法返回当前节点的key值。
提供了getValue()，setValue(V v)分别用于获取Value，以及覆盖Value后返回oldValue
重写了equals()方法用于判断两个红黑树节点是否相同。逻辑是：两个红黑树节点的key要么都为null，要么equals结果true，且，value要么都为null,要么equals结果为true。
重写了hashCode()方法。
重写了toString()方法。
public TreeMap()
public TreeMap() {
comparator = null;
}无参构造器，即不指定比较器的构造器。
注意，此时插入集合的键值对的key的类型必须实现Comparable接口，即提供自然排序能力，否则会报错类型转换异常。
public TreeMap(Comparator<? super K> comparator)
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}指定比较器的构造器。
指定的比较器用于比较key，且comparator指定了泛型，即比较器比较的元素的类型必须是K或者K的父类类型。
public TreeMap(Map<? extends K, ? extends V> m)
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}将非TreeMap集合转为TreeMap集合构造器
public TreeMap(SortedMap<K, ? extends V> m)
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}将有序Map集合转为TreeMap集合
public V get(Object key)
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}TreeMap的get方法用于获取指定key的value。如果指定key没有对应的红黑树节点，则返回null，否则返回对应红黑树节点的value。
可以看到get方法实现依赖于getEntry(Object key)方法。
getEntry(Object key)方法是根据指定key找对应的红黑树节点并返回该节点。
final Entry<K,V> getEntry(Object key)
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)//如果外部指定了比较器
return getEntryUsingComparator(key);//则使用指定比较器来查找
if (key == null)//如果外部没有指定比较器，且要查找的key为null，则抛出空指针异常
throw new NullPointerException();
@SuppressWarnings("unchecked")//此时外部没有指定构造器，且要查的Key不为null
Comparable<? super K> k = (Comparable<? super K>) key;//检查Key的类型是否实现了Comparable接口，即是否实现了自然排序，如果实现了，则此处可以强转成功，否则会报错类型转换异常
Entry<K,V> p = root;
while (p != null) {//从红黑树根节点开始使用key本身的自然排序进行比较
int cmp = k.compareTo(p.key);
if (cmp < 0)//如果要查找的key小于树节点的key，则说明要找的key在当前节点的左子树上，则下次遍历从左子树的根节点开始
p = p.left;
else if (cmp > 0)//如果要查找的key大于树节点的key，则说明要找的key在当前节点的右子树上，则下次遍历从右子树的根节点开始
p = p.right;
else//如果要查找的key等于树节点的key，则该节点就是要找的，直接返回该节点
return p;
}
return null;//如果上面遍历没有找到对应Key的节点，则返回null
}
final Entry<K,V> getEntryUsingComparator(Object key) {//使用指定比较器来查找，逻辑基本和自然排序查找一样，只是这里使用了比较器排序查找
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
return null;
}
public V put(K key, V value)
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
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);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}final int compare(Object k1, Object k2) {
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
}public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}TreeMap的put方法用于插入一个键值对，
当插入的key在集合中不存在时，则put表示新增键值对，并返回null；
当插入的key在集合中存在时，则put表示覆盖已存在key对应的value，并返回老value。
private void fixAfterInsertion(Entry<K,V> x)
private void fixAfterInsertion(Entry<K,V> x) {//x是被插入的红黑树节点
x.color = RED;//默认被插入的节点都是红色
while (x != null && x != root && x.parent.color == RED) {//如果被插入节点不是根节点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(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 == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
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);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;//如果被插入的节点是根节点，则节点颜色改为黑色
}上述就是小编为大家分享的TreeMap怎么在Java中使用了，如果刚好有类似的疑惑，不妨参照上述分析进行理解。如果想知道更多相关知识，欢迎关注亿速云行业资讯频道。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。