Java:TreeMap类小记

时间:2022-12-31 23:21:31

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类小记的更多相关文章

  1. Java API —— TreeMap类

    1.TreeMap类概述         键是红黑树结构,可以保证键的排序和唯一性 2.TreeMap案例         TreeMap<String,String>         T ...

  2. JAVA中的数据结构——集合类(线性表:Vector、Stack、LinkedList、set接口;键值对:Hashtable、Map接口&lt&semi;HashMap类、TreeMap类&gt&semi;)

    Java的集合可以分为两种,第一种是以数组为代表的线性表,基类是Collection:第二种是以Hashtable为代表的键值对. ... 线性表,基类是Collection: 数组类: person ...

  3. Java:ConcurrentHashMap类小记-3&lpar;JDK8&rpar;

    Java:ConcurrentHashMap类小记-3(JDK8) 结构说明 // 所有数据都存在table中, 只有当第一次插入时才会被加载,扩容时总是以2的倍数进行 transient volat ...

  4. Java:ConcurrentHashMap类小记-2&lpar;JDK7&rpar;

    Java:ConcurrentHashMap类小记-2(JDK7) 对 Java 中的 ConcurrentHashMap类,做一个微不足道的小小小小记,分三篇博客: Java:ConcurrentH ...

  5. Java:ConcurrentHashMap类小记-1&lpar;概述&rpar;

    Java:ConcurrentHashMap类小记-1(概述) 对 Java 中的 ConcurrentHashMap类,做一个微不足道的小小小小记,分三篇博客: Java:ConcurrentHas ...

  6. Java:HashMap类小记

    Java:HashMap类小记 对 Java 中的 HashMap类,做一个微不足道的小小小小记 概述 HashMap:存储数据采用的哈希表结构,元素的存取顺序不能保证一致.由于要保证键的唯一.不重复 ...

  7. Java:HashTable类小记

    Java:HashTable类小记 对 Java 中的 HashTable类,做一个微不足道的小小小小记 概述 public class Hashtable<K,V> extends Di ...

  8. Java:LinkedHashMap类小记

    Java:LinkedHashMap类小记 对 Java 中的 LinkedHashMap类,做一个微不足道的小小小小记 概述 public class LinkedHashMap<K,V&gt ...

  9. Java:LinkedList类小记

    Java:LinkedList类小记 对 Java 中的 LinkedList类,做一个微不足道的小小小小记 概述 java.util.LinkedList 集合数据存储的结构是循环双向链表结构.方便 ...

随机推荐

  1. jQuery高级编程

    jquery高级编程1.jquery入门2.Javascript基础3.jQuery核心技术 3.1 jQuery脚本的结构 3.2 非侵扰事JavaScript 3.3 jQuery框架的结构 3. ...

  2. DateEdit和TimeEdit用法

    DateEdit 控件默认情况下,显示的只有日期,没有时间.下面介绍2中日期和时间同时显示的方法: 1.Properties.VistaDisplayMode 为true, 2.Properties. ...

  3. IO流的练习 —— 创建用户注册、登陆案例

    把上次用集合做的时候的分析拿出来 需求: 用户登录注册案例 按照如下操作,可以让我们更符合面向对象思想: A:这个案例有哪些类 B:每个类中又有哪些东西 C:类与类之间的关系 分析: A:这个案例有哪 ...

  4. 流媒体学习三-------SIP消息结构详解

    SIP消息由三部分组成,即:开始行(start line).消息头(header).正文(body)Start-line:请求行Request-line  消息为 request消息时使用reques ...

  5. Metro中控件WebView访问外部的网页显示一片空白

    Metro中控件WebView访问外部的网页显示一片空白 解决方案: ​下载安装了Initex.Software.Proxifier.v3.21.Standard.Edition.Incl.Keyma ...

  6. python深入走路

    Python描述符(descriptor)解密 http://www.geekfan.net/7862/

  7. 洛谷 P3399 丝绸之路

    题目背景 张骞于公元前138年曾历尽艰险出使过西域.加强了汉朝与西域各国的友好往来.从那以后,一队队骆驼商队在这漫长的商贸大道上行进,他们越过崇山峻岭,将中国的先进技术带向中亚.西亚和欧洲,将那里的香 ...

  8. Android初步 简单demo

    刚入门不久,没学JAVA,从C++转过来的,C++的QT和安卓简直有异曲同工之妙,为了加深自己对安卓的理解,特写博客以记录,望大神们多多指点. 效果图,刚入门的话,肯定要熟悉基本的控件的使用,这跟我学 ...

  9. 大型分布式C&plus;&plus;框架《二:大包处理过程》

    本来这一篇是打算写包头在分布式平台中的具体变换过程的.其实文章已经写好了.但是想了这个应该是不能随便发表的.毕竟如果知道了一个包的具体每个字节的意义.能伪造包来攻击系统.其次来介绍一个包的具体变换过程 ...

  10. e&period;target 和 e&period;srcElement 的使用问题

    ie 下的event.srcElement从字面上可以看出来有以下关键字:事件.源(它的意思就是:当前事件的源), 我们可以调用他的各种属性就像:document.getElementById(&qu ...