Java:TreeMap类小记
对 Java 中的 TreeMap类,做一个微不足道的小小小小记
概述
前言:之前已经小小分析了一波 HashMap类、HashTable类、ConcurrentHashMap类、LinkedHashMap类,现在再小小分析一下TreeMap类
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
// ...
}
TreeMap 的实现就是红黑树数据结构,也就说是一棵自平衡的排序二叉树,这样就可以保证当需要快速检索指定节点,更具key找节点的时间复杂度在为 O(logn) 级别
TreeMap 中的每个 Entry 都被当成“红黑树”的一个节点对待;
// 红黑树节点定义
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; // 红/黑
// ... 省略一下构造方法/get/set方法
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;
}
}
需要说明的是,关于红黑树的构建,调整等操作,这些主要涉及的是数据结构方面的知识点,这里不做过多分析。
实现原理
成员属性
// 由于TreeMap实现的是红黑树数据结构,而其是通过 key 进行比较的,从而达到有序的状态
private final Comparator<? super K> comparator;
// 树的根节点
private transient Entry<K,V> root;
// 集合大小
private transient int size = 0;
// 存储结构被修改的次数
private transient int modCount = 0;
// 红黑树节点定义
static final class Entry<K,V> implements Map.Entry<K,V> {
// 上面已经给出了
}
构造方法
// 1. 无定义比较方式的构造方法
public TreeMap() {
comparator = null;
}
// 2. 自定义比较器的构造方法
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
// 3. 用已知Map对象为TreeMap
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
// 4. 构造已知的SortedMap对象为TreeMap
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) {
}
}
put 方法
public V put(K key, V value) {
// 获取根节点
Entry<K,V> t = root;
if (t == null) {
// 如果根节点为空,则该元素置为根节点
// ☆compare☆后续分析
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; // t就是root
// 调用比较器对象的compare()方法,该方法返回一个整数
cmp = cpr.compare(key, t.key);
if (cmp < 0)
// 待插入元素的key"小于"当前位置元素的key,则查询左子树
t = t.left;
else if (cmp > 0)
// 待插入元素的key"大于"当前位置元素的key,则查询右子树
t = t.right;
else
// "相等"则替换其value。
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)
// 待插入元素的key"小于"当前位置元素的key,则查询左子树
t = t.left;
else if (cmp > 0)
// 待插入元素的key"大于"当前位置元素的key,则查询右子树
t = t.right;
else
// "相等"则替换其value。
return t.setValue(value);
} while (t != null);
}
// 根据key找到父节点后新建一个节点
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0) // 根据比较的结果来确定放在左子树还是右子树
parent.left = e;
else
parent.right = e;
// 由于在插入节点后,红黑树的平衡性会被打破,因此会通过左旋/右旋进行调整的
fixAfterInsertion(e);
size++; // 集合大小+1
modCount++; // 集合结构被修改次数+1
return null;
}
后续的删除节点其实也是大同小异,也就不看了,推荐一篇博文:
https://blog.csdn.net/jtcode_is_my_partner/article/details/81408392
里面讲了修复的过程
compare
使得 TreeMap 能有序的主要原因就是这个比较,把新增节点与 根节点/左子节点/右子节点 不断的比较,直到找到合适的位置进行插入
先给出 compare 方法:
private final Comparator<? super K> comparator;
final int compare(Object k1, Object k2) {
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
}
案例1:使用默认的比较器
TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("aaa", 1);
treeMap.put("bbb", 2);
treeMap.put("ddd", 4);
treeMap.put("ccc", 3);
// 可见默认的就是string的comparator
Comparator<? super String> comparator = treeMap.comparator();
Set<Map.Entry<String, Integer>> entries = treeMap.entrySet();
for (Map.Entry<String, Integer> entry: entries){
System.out.println(entry.getKey() +":"+ entry.getValue());
}
// 输出:
// aaa:1
// bbb:2
// ccc:3
// ddd:4
案例2:自定义比较器
关于比较器的定义方式,可见:Java:常用的容器小记:Comparable 与 Comparator 两个接口的区别
// 升序:
TreeMap<Integer, String> treeMap = new TreeMap<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1-o2;
}
});
treeMap.put(1, "aaa"); // 输出顺序:1
treeMap.put(2, "bbb"); // 输出顺序:2
treeMap.put(4, "ddd"); // 输出顺序:3
treeMap.put(3, "ccc"); // 输出顺序:4
Set<Map.Entry<Integer, String>> entries = treeMap.entrySet();
for (Map.Entry<Integer, String> entry: entries){
System.out.println(entry.getKey() +":"+ entry.getValue());
}
// 降序
TreeMap<Integer, String> treeMap = new TreeMap<>((o1, o2) -> o2-o1);
treeMap.put(1, "aaa"); // 输出顺序:4
treeMap.put(2, "bbb"); // 输出顺序:3
treeMap.put(4, "ddd"); // 输出顺序:2
treeMap.put(3, "ccc"); // 输出顺序:1
// 可见默认的就是string的comparator
Comparator<? super Integer> comparator = treeMap.comparator();
Set<Map.Entry<Integer, String>> entries = treeMap.entrySet();
for (Map.Entry<Integer, String> entry: entries){
System.out.println(entry.getKey() +":"+ entry.getValue());
}
get 方法
根据key获取元素
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
// 如果有自定义比较器对象,就按照自定义规则遍历二叉树
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
return p;
}
return null;
}
// 获取第一个元素/最小的元素
public Map.Entry<K,V> firstEntry() {
return exportEntry(getFirstEntry());
}
// 根据二叉搜索树的性质,最左边的节点为最小的节点
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
参考
https://blog.csdn.net/jtcode_is_my_partner/article/details/81408392
https://blog.csdn.net/qq_32166627/article/details/72773293
Java:TreeMap类小记的更多相关文章
-
Java API —— TreeMap类
1.TreeMap类概述 键是红黑树结构,可以保证键的排序和唯一性 2.TreeMap案例 TreeMap<String,String> T ...
-
JAVA中的数据结构——集合类(线性表:Vector、Stack、LinkedList、set接口;键值对:Hashtable、Map接口<;HashMap类、TreeMap类>;)
Java的集合可以分为两种,第一种是以数组为代表的线性表,基类是Collection:第二种是以Hashtable为代表的键值对. ... 线性表,基类是Collection: 数组类: person ...
-
Java:ConcurrentHashMap类小记-3(JDK8)
Java:ConcurrentHashMap类小记-3(JDK8) 结构说明 // 所有数据都存在table中, 只有当第一次插入时才会被加载,扩容时总是以2的倍数进行 transient volat ...
-
Java:ConcurrentHashMap类小记-2(JDK7)
Java:ConcurrentHashMap类小记-2(JDK7) 对 Java 中的 ConcurrentHashMap类,做一个微不足道的小小小小记,分三篇博客: Java:ConcurrentH ...
-
Java:ConcurrentHashMap类小记-1(概述)
Java:ConcurrentHashMap类小记-1(概述) 对 Java 中的 ConcurrentHashMap类,做一个微不足道的小小小小记,分三篇博客: Java:ConcurrentHas ...
-
Java:HashMap类小记
Java:HashMap类小记 对 Java 中的 HashMap类,做一个微不足道的小小小小记 概述 HashMap:存储数据采用的哈希表结构,元素的存取顺序不能保证一致.由于要保证键的唯一.不重复 ...
-
Java:HashTable类小记
Java:HashTable类小记 对 Java 中的 HashTable类,做一个微不足道的小小小小记 概述 public class Hashtable<K,V> extends Di ...
-
Java:LinkedHashMap类小记
Java:LinkedHashMap类小记 对 Java 中的 LinkedHashMap类,做一个微不足道的小小小小记 概述 public class LinkedHashMap<K,V> ...
-
Java:LinkedList类小记
Java:LinkedList类小记 对 Java 中的 LinkedList类,做一个微不足道的小小小小记 概述 java.util.LinkedList 集合数据存储的结构是循环双向链表结构.方便 ...
随机推荐
-
jQuery高级编程
jquery高级编程1.jquery入门2.Javascript基础3.jQuery核心技术 3.1 jQuery脚本的结构 3.2 非侵扰事JavaScript 3.3 jQuery框架的结构 3. ...
-
DateEdit和TimeEdit用法
DateEdit 控件默认情况下,显示的只有日期,没有时间.下面介绍2中日期和时间同时显示的方法: 1.Properties.VistaDisplayMode 为true, 2.Properties. ...
-
IO流的练习 —— 创建用户注册、登陆案例
把上次用集合做的时候的分析拿出来 需求: 用户登录注册案例 按照如下操作,可以让我们更符合面向对象思想: A:这个案例有哪些类 B:每个类中又有哪些东西 C:类与类之间的关系 分析: A:这个案例有哪 ...
-
流媒体学习三-------SIP消息结构详解
SIP消息由三部分组成,即:开始行(start line).消息头(header).正文(body)Start-line:请求行Request-line 消息为 request消息时使用reques ...
-
Metro中控件WebView访问外部的网页显示一片空白
Metro中控件WebView访问外部的网页显示一片空白 解决方案: 下载安装了Initex.Software.Proxifier.v3.21.Standard.Edition.Incl.Keyma ...
-
python深入走路
Python描述符(descriptor)解密 http://www.geekfan.net/7862/
-
洛谷 P3399 丝绸之路
题目背景 张骞于公元前138年曾历尽艰险出使过西域.加强了汉朝与西域各国的友好往来.从那以后,一队队骆驼商队在这漫长的商贸大道上行进,他们越过崇山峻岭,将中国的先进技术带向中亚.西亚和欧洲,将那里的香 ...
-
Android初步 简单demo
刚入门不久,没学JAVA,从C++转过来的,C++的QT和安卓简直有异曲同工之妙,为了加深自己对安卓的理解,特写博客以记录,望大神们多多指点. 效果图,刚入门的话,肯定要熟悉基本的控件的使用,这跟我学 ...
-
大型分布式C++框架《二:大包处理过程》
本来这一篇是打算写包头在分布式平台中的具体变换过程的.其实文章已经写好了.但是想了这个应该是不能随便发表的.毕竟如果知道了一个包的具体每个字节的意义.能伪造包来攻击系统.其次来介绍一个包的具体变换过程 ...
-
e.target 和 e.srcElement 的使用问题
ie 下的event.srcElement从字面上可以看出来有以下关键字:事件.源(它的意思就是:当前事件的源), 我们可以调用他的各种属性就像:document.getElementById(&qu ...