首页 文章 精选 留言 我的

精选列表

搜索[提高]，共10000篇文章
优秀的个人博客,低调大师

提高API采用率的关键：快速创建有效的API监控任务

为什么需要API监控？ 在当今数字化时代，企业应用程序及网站越来越依赖于外部 API 和第三方应用程序提供商。例如一家电商公司，他们的网站可能同时会接入多个外部API，包括支付、物流、广告等服务。如果在用户购买商品时，恰巧出现了支付API故障，就会导致用户无法完成付款动作，从而影响公司的整体营收。API的可靠性直接关系到公司的业务运转。当应用程序中的API出现问题时，会影响到整个网站或应用程序的性能，甚至会导致网站或应用程序直接崩溃。因此，API监控变得至关重要。 监控宝API监控 监控宝提供的API监控能够利用全球近百个监测点，实时监控API的运行状况，包括可用性、正确性、响应时间等性能数据。通过实时告警和历史统计分析，帮您快速发现并解决问题，节约企业的运维成本，减少业务损失。监控宝的API监控能够： 实时监控get、post、put、delete、head、options六种API请求方式，覆盖绝大部分的接口调用格式。 支持JSON、XML、Text、Response Header、状态码验证及Postman，JMeter脚本导入。 通过断言功能监测正确性，支持监控多步请求，从而实现对整个业务流程的监控。 API监控包括可用性、正确性、响应时间、可用率、故障率、正确率、平均可用率、平均正确率、平均响应时间、错误总时长、错误总次数、故障总时长、故障总次数13个监控指标。判断和计算规则如下： 创建监控任务 配置入口：API监控>任务管理 单击创建项目创建API监控任务，需要配置监控任务的基本信息、事务设置、监控设置和告警设置。 设置基本信息 在创建API监控任务页面设置监控任务的基本信息，包括定义任务名称、选择项目是否加入分类。如下图所示。 任务名称 输入任务名称，以便于查找和区分监控对象。您需要为监控任务设置一个有代表性的名称，例如您需要监控在淘宝中提交订单的业务流程，则可设置监控任务名称为“淘宝-提交订单”。 项目是否加入分类 为方便管理自己创建的监控任务，您可为当前监控任务选择一个项目分类。您还可以单击创建分类，新建一个项目分类作为当前监控任务的分类。 设置初始变量 您可利用变量来存储值，动态地提取HTTP响应数据，并在多个请求之间动态地传递数据和状态。比如，添加请求1时，可通过设置变量$a来动态提取Response Header中的Date值。然后在添加请求2时，使用变量a作为断言的目标值。使用变量时需要提前初始化变量，即为变量赋默认值。 在创建API监控任务的事务设置页面，单击设置初始化变量，添加并管理初始变量，如下图所示。 设置自定义变量 在自定义变量页面区域，单击添加变量添加一个变量，设置变量名称和变量值。自定义变量仅应用于本监控任务。注意：变量名称必须以$符号开头，并且是纯字母组成。除自定义变量外，您可以查看系统变量及自定义系统变量，系统变量可用于所有监控任务的API请求。 设置系统变量 在系统变量页面区域，单击自定义页签，单击添加变量添加系统变量，定义变量名称和变量描述信息。注意：在自定义系统变量时，变量名称必须以$public_开头。在系统变量页面区域，单击公共函数页签，查看可用的系统变量，详细说明见下表。 设置事务 在创建API监控任务的事务设置中添加并管理需要监控的API请求。 您能够直接导入脚本来添加API请求，也可手动添加和设置API请求。添加API请求后，可直接复制已添加的请求来创建新的请求。 通过导入脚本添加API请求 为快速创建多条API请求，单击导入脚本，在打开的对话框中直接输入脚本内容并导入。导入成功后，监控宝根据导入的脚本自动创建对应的API请求。在打开的导入脚本对话框，单击查看实例了解脚本样式，脚本支持Postman和JMeter格式。您可以直接使用Postman中生成的脚本。 手动添加API请求 单击添加请求，打开请求编辑页面，如下图所示。 根据实际需要设置各项内容，详细说明见下表。 复制API请求 为避免重复设置，添加API请求后，您可单击【复制按钮】复制当前API请求作为一条新的API请求，根据需要修改相应内容即可。 移动API请求 当添加多个API请求，如果需要调换请求的先后顺序，鼠标拖动目标请求移动到目标位置。 添加请求间隔 单击添加请求间隔，输入发送API请求的时间间隔，例如设置“10s”,则发送一次API请求后，等待10s发送第二次API请求。 测试API监控请求 添加API请求后，为保证正常监控，需检查是否能请求成功。单击验证测试来测试请求并查看测试结果，如下图所示。 请求成功即可用，所有请求都成功时，监控任务（即整个业务流程）的状态为正常且可用，单击展开>返回结果，查看请求的返回结果。添加断言时才能测试请求的正确性，所有请求都正确时监控任务的正确性为“是”，单击展开>变量与断言，查看断言详情。 设置监控 在创建API监控任务的监控设置中，设置监测点和监控频率，如下图所示。 监测点选择相应的监测点对目标API进行监测。您可以选择多个监测点也可以创建/选择一个监测点分组。所选择的监测点或监测点分组的成员均用来监测目标网API。 选择监测点：根据需求选择多个监测点。 选择监测点分组：选择或创建监测点分组。若分组内监测点成员有所变化，任务创建后仍会同步。 注意：选择监测点分组后，监测点分组中的所有监测点都发生故障时才会向您发送告警消息。 监控频率：监控宝执行监控的时间间隔，例如选择2分钟，则监控宝每隔2分钟就执行一次监控。 设置告警 在创建API监控任务的告警设置中，设置常规告警重试次数，连续连续告警提醒，告警线，企业IM通知及告警方式，如下图所示。 告警设置项说明如下表所示： 小结 在过去的封闭系统中，如果出现故障，只会对该系统内的应用程序产生影响，而对于现在大部分企业来说，一个故障就会影响到整个生态系统。监控宝可以利用全球近百个监测点，实时监控API的运行状况，保障企业运维效率及用户体验。点击此处，马上申请监控宝免费试用名额
2023-04-04
优秀的个人博客,低调大师

Java 引入预览版虚拟线程功能，大幅提高应用吞吐量

OpenJDK 的 JEP 425 ：虚拟线程（预览版）功能提案显示： Java 平台将引入虚拟线程特性。虚拟线程是轻量级线程，可显著地减少编写、维护和观察高吞吐量并发应用程序的工作量。 Java 开发人员一直依赖线程作为并发服务器应用程序的构建块，每个方法中的语句都在一个线程内执行，每个线程提供一个堆栈来存储局部变量和协调方法调用，以及报错时的上下文捕获。线程是 Java 的并发单元，也是 Java 工具的核心基础：调试器逐步执行线程方法中的语句，分析器则可视化多个线程的行为。 目前，JDK 将其平台线程实现为操作系统 (OS) 线程的包装器，JDK 中每个实例都是一个平台线程，平台线程在底层操作系统线程上运行 Java 代码 ，并在代码的整个生命周期内捕获 OS 线程。平台线程数受限于 OS 线程数，而OS 线程的成本很高，不能占用太多。因此，目前 JDK 的这种线程实现方法限制了其应用程序的吞吐量，使吞吐量远低于硬件支持的水平。 关于虚拟线程 虚拟线程java.lang.Thread是在底层操作系统线程（OS 线程）上运行 Java 代码，但在代码的整个生命周期内不捕获 OS 线程的实例。这意味着许多虚拟线程可以在同一个 OS 线程上运行 Java 代码，从而有效地共享它。 虚拟线程是由 JDK 而不是操作系统提供的线程的轻量级实现，也是用户模式线程的一种形式。用户模式线程在 Java 的早期版本中被称为“绿色线程”，当时操作系统线程的概念还不够成熟和普及， Java 的所有绿色线程都共享一个 OS 线程（M:1 调度），随着线程概念的发展，绿色线程最终被现在的平台线程超越，实现为 OS 线程的包装器（1:1 调度），而最新引入的虚拟线程采用 M:N 调度，其中大量 (M) 虚拟线程被调度为在较少数量 (N) 的 OS 线程上运行。 更高的吞吐量 开发者可以选择使用虚拟线程还是平台线程，但虚拟线程在高吞吐量的服务器应用程序中表现更好。比如下面这段休眠一秒钟的代码就创建了大量的虚拟线程，程序首先获得一个ExecutorService，它为每个提交的任务创建一个新的虚拟线程，然后提交 10000 个任务并等待所有任务完成：： try (var executor = Executors.newVirtualThreadPerTaskExecutor()) { IntStream.range(0, 10_000).forEach(i -> { executor.submit(() -> { Thread.sleep(Duration.ofSeconds(1)); return i; }); }); } // executor.close() is called implicitly, and waits 现代硬件可以很容易地支持 10000 个虚拟线程同时运行这样的代码。如果该程序使用为每个任务都创建一个新平台线程的 ExecutorService，例如 Executors.newCachedThreadPool() ，那么它将尝试创建 10000 个平台线程，也就意味着 10000 个 OS 线程，那么这个程序在大多数操作系统上都会崩溃。又或者这个程序使用从池中获取平台线程的 ExecutorService，如 Executors.newFixedThreadPool(200)，也好不到哪去。 ExecutorService 将创建 200 个平台线程供这 10000 个任务共享，任务将按顺序运行而不是同时运行，程序需要很长时间才能跑完。 对于上述程序来说，具有 200 个平台线程的池只能实现每秒 200 个任务的吞吐量，而虚拟线程可以实现大约每秒 10000 个任务的吞吐量（在充分预热之后）。此外，如果将示例程序中的 10000 更改为 1,000,000 ，则程序将提交 1,000,000 个任务，创建 1,000,000 个并发运行的虚拟线程，并且（在充分预热后）达到大约 1,000,000 个任务/秒的吞吐量。 总而言之，虚拟线程不是更快的线程 —— 它们运行代码的速度并不比平台线程快。它们的存在是为了提供规模（更高的吞吐量），而不是速度（更低的延迟）。 如何启用虚拟线程？ 目前虚拟线程在其他多线程语言中被广泛使用（例如 Go 中的 goroutine 和 Erlang 中的进程，在 C++ 中也是一个稳定特性），但在 Java 中还是一个预览 API，默认禁用。如要在 JDK XX 上尝试该功能，则必须通过以下方法启用预览 API： 使用 javac --release XX --enable-preview Main.java 编译程序，并使用 java --enable-preview Main 运行 使用源代码启动器时，使用 java --release XX --enable-preview Main.java 运行程序 使用 jshell 时，用 jshell --enable-preview 启动 有关虚拟线程的更多信息可在 OpenJDK 的JDK Issue-8277131中查看，目前该提案于 2021/11/15 创立，目前还处于 JEP 流程的第一阶段，距离稳定版本还需要一段时间。
2022-04-08
优秀的个人博客,低调大师

KDE Plasma 5.22 发布，全面提高稳定性和可用性

KDE Plasma 5.22 现已发布。官方表示，该版本比以往更加可靠和稳定，通过在清理后台和重构代码，Plasma 桌面带来了更快的响应速度和性能。同时，将Plasma 全部转移到 Wayland（未来的显示协议）的工作仍在全面进行，以提供更好的体验和更强的稳定性。 自适应透明度 该版本具有自适应透明度，这意味着面板和面板部件通常是半透明的，但如果有任何最大化的窗口，就会变得完全不透明，以避免在用户需要集中注意力时出现任何视觉干扰。用户也可以设置面板总是半透明或总是不透明的。 搜索菜单项 全局菜单小程序现在可以让用户在 Wayland 上搜索菜单项。此外，当把鼠标悬停在面板上的任务管理器中的一个应用程序的图标时，会出现一个工具提示，以展示该应用程序打开的所有窗口的预览。并且该版本将使用 Plasma System Monitor 作为默认的系统监控应用程序。 系统设置 Plasma 5.22 的系统设置可以在一个快速页面上打开，让用户直接进入最常用的设置或者最常访问的设置。它包括一个改变墙纸设置，以对整体外观进行更多调整。此外，用户现在可以在设置中禁用软件的离线更新功能。 系统面板 该版本的系统面板（通常位于桌面的右下角）中的小工具在外观上更加一致，也更加实用。包括引入重新设计的数字时钟，以及点击时钟时弹出的日历外观，还有更加完善的音频音量小部件和剪贴板。 KRunner KRunner 是 Plasma 的迷你命令行启动器，现在可以显示多行文字，而不是单行。这意味着用户现在可以很方便地阅读长的字典定义。另外，KRunner 不再返回混乱的重复搜索结果，所以当用户搜索 "Firefox" 时，KRunner 现在只显示一个结果，而不是显示桌面应用程序、命令行应用程序、面板快捷方式等几个结果。 通知 在 Plasma 5.22 的 Wayland 会话中，通知小部件变得更加完善，如果用户正在分享或录制屏幕用于在线演示、课堂或视频，通知小部件会自动进入 "请勿打扰" 模式，暂停干扰性的弹出通知，直到用户完成。它还可以在从互联网下载被阻止时通知用户，更重要的是，当下载完成后，通知小工具可以知道并显示哪个应用程序将打开该文件。 KWin 和图形 KWin 是后台的窗口管理软件，从 Plasma 5.22 开始，KWin 支持 Wayland 上的可变刷新率/自由同步屏幕。这意味着，如果用户可以有多个屏幕，而且每个屏幕都设置不同的刷新率。此外，KWin 现在可以设置一个屏幕的过扫描值，这可以确保没有任何图像会在屏幕的边界之外被切断，也可以用来消除边缘的黑边。 其他 KWin Wayland 的改进包括 Present Windows 效果：当用户把光标移到屏幕的左上角时显示所有打开的窗口。它与 X11 上的效果完全一致。用户现在可以在垂直或水平方向上最大化窗口。支持插入外部显卡，KWin 会自动接收并配置它，而不需要重新启动 Plasma。 更多详细内容，请查看官方公告。
2021-06-09
优秀的个人博客,低调大师

Google 提高 Android RAM 要求，低于 2GB 将强制使用 Android GO

外媒XDAdevelopers表示，其近日发现了一份泄露的 Google 文档，名为“Android 11 Go 版设备配置指南” （日期为 2020 年 4 月 24 日）。该文档内容显示， 对于新推出的配备 2GB RAM 或以下的低阶 Android 手机，Google计划强制预载 Android Go 版本系统。 一些具体内容如下： 从 Android 11 开始，具有 512MB RAM（包括升级）的设备将不符合预加载 GMS 的资格。 所有在 Android 11 上启动的新产品（如果它们具有 2GB 或更少的 RAM），必须为 ActivityManager.isLowRamDevice() API 返回 true，并作为 Android Go 设备启动。 从 2020 年第四季度开始，所有随 Android 10 一起启动的新产品（如果它们具有 2GB 或更少的 RAM），必须为 ActivityManager.isLowRamDevice()API 返回 true，并作为 Android Go 设备启动。 之前推出的标准 GMS 配置的 2GB RAM 设备，不应该通过 MRs 或 letter升级转换为 Android Go 配置。它们将保持标准的 Android版本。 也就是说，从 2020 年第四季度开始，任何运行 2GB 或更少 RAM 的新 Android 10 设备都必须使用 Android Go Edition。此外，任何使用 Android 11启动且具有 2GB 或更少 RAM 的设备也必须使用 Android Go。 不过已经上市的设备并不会受到影响。换句话说，对于已经在使用只有 1GB 容量的 Android 智能手机的用户来说，将不会有任何改变，其设备将像以前一样继续工作并接收更新。 谷歌的这些决定或许会让人们对低端 Android 设备的看法产生相当大的变化，将 Android Go 安装在 1GB 和 2G B设备上也意味着整体性能将会更好。
2020-07-25
优秀的个人博客,低调大师

【Java入门提高篇】Day34 Java容器类详解（十五）WeakHashMap详解

在Java容器详解系列文章的最后，介绍一个相对特殊的成员：WeakHashMap，从名字可以看出它是一个Map。它的使用上跟HashMap并没有什么区别，所以很多地方这里就不做过多介绍了，可以翻看一下前面HashMap中的内容。本篇主要介绍它与HashMap的不同之处。 WeakHashMap特殊之处在于WeakHashMap里的entry可能会被垃圾回收器自动删除，也就是说即使你没有调用remove()或者clear()方法，它的entry也可能会慢慢变少。所以多次调用比如isEmpty，containsKey，size等方法时可能会返回不同的结果。 接下来希望能带着这么几个问题来进行阅读： 1、WeakHashMap中的Entry为什么会自动被回收。 2、WeakHashMap与HashMap的区别是什么。 3、WeakHashMap的引用场景有哪些。 WeakHashMap探秘 从说明可以看出，WeakHashMap的特殊之处便在于它的Entry与众不同，里面的Entry会被垃圾回收器自动回收，那么问题来了，为什么会被自动回收呢？HashMap里的Entry并不会被自动回收，除非把它从Map中移除掉。 其实这个秘密就在于弱引用，WeakHashMap中的key是间接保存在弱引用中的，所以当key没有被继续使用时，就可能会在GC的时候被回收掉。 只有key对象是使用弱引用保存的，value对象实际上仍旧是通过普通的强引用来保持的，所以应该确保value不会直接或者间接的保持其对应key的强引用，因为这样会阻止key被回收。 如果对于引用类型不熟悉的话，可以先阅读这篇文章。 下面来从源码角度看看具体是如何实现这个特性的。 继承结构 WeakHashMap并不是继承自HashMap，而是继承自AbstractMap，跟HashMap的继承结构差不多。 存储结构 WeakHashMap中的数据结构是数组+链表的形式，这一点跟HashMap也是一致的，但不同的是，在JDK8中，当发生较多key冲突的时候，HashMap中会由链表转为红黑树，而WeakHashMap则一直使用链表进行存储。 成员变量 // 默认初始容量，必须是2的幂 private static final int DEFAULT_INITIAL_CAPACITY = 16; // 最大容量 private static final int MAXIMUM_CAPACITY = 1 << 30; // 默认装载因子 private static final float DEFAULT_LOAD_FACTOR = 0.75f; // Entry数组，长度必须为2的幂 Entry<K,V>[] table; // 元素个数 private int size; // 阈值 private int threshold; // 装载因子 private final float loadFactor; // 引用队列 private final ReferenceQueue<Object> queue = new ReferenceQueue<>(); // 修改次数 int modCount; 跟HashMap的成员变量几乎一致，这里多了一个ReferenceQueue，用来存放那些已经被回收了的弱引用对象。如果想知道ReferenceQueue是如何工作的，可以参考这篇文章。 构造函数 WeakHashMap中也有四个构造函数： public WeakHashMap(int initialCapacity, float loadFactor) { ... } public WeakHashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public WeakHashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } public WeakHashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); putAll(m); } 可以看到后三个，都是调用的第一个构造函数，下面再来看一下第一个构造函数的内容： // 校验initialCapacity if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Initial Capacity: "+ initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // 校验loadFactor if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal Load factor: "+ loadFactor); int capacity = 1; // 将容量设置为大于initialCapacity的最小2的幂 while (capacity < initialCapacity) capacity <<= 1; table = newTable(capacity); this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); 再看看newTable函数。 private Entry<K,V>[] newTable(int n) { return (Entry<K,V>[]) new Entry<?,?>[n]; } 这里其实只是简单的创建一个Entry数组。 Entry剖析 接下来看看WeakHashMap中的核心角色——Entry。上面已经看到了，WeakHashMap中的table是一个Entry数组： Entry<K,V>[] table; 来看看Entry长什么样： private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> { ... } Entry继承自WeakReference，继承关系图如下： 再来看看Entry中的内容： // 成员变量 V value; final int hash; Entry<K,V> next; // 构造函数 Entry(Object key, V value, ReferenceQueue<Object> queue, int hash, Entry<K,V> next) { super(key, queue); this.value = value; this.hash = hash; this.next = next; } 细心的你可能会发现，哎？key哪里去了，成员变量里没有key。别着急，看看构造函数就可以发现，它调用了父类的构造函数。 super(key, queue); 这里调用的WeakReference的构造函数，将key传入Reference中，保存在referent成员变量中。对Reference和WeakReference不熟悉的话可以参考这篇文章和这篇文章。 再看看其它几个方法： @SuppressWarnings("unchecked") public K getKey() { // 这里调用了Reference的get方法，从中取出referent对象 // WeakHashMap中，key如果为null会使用NULL_KEY来替代 return (K) WeakHashMap.unmaskNull(get()); } public V getValue() { return value; } public V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<?,?> e = (Map.Entry<?,?>)o; K k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { V v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } public int hashCode() { K k = getKey(); V v = getValue(); // 这里只是简单的把key和value的hashcode做一个异或处理 return Objects.hashCode(k) ^ Objects.hashCode(v); } public String toString() { return getKey() + "=" + getValue(); } 这里稍微说一下getKey方法，调用了WeakHashMap.unmaskNull，之所以要调用这个方法，其实是因为WeakHashMap中对key为null时的特殊处理，会将其指向一个特殊的内部变量： private static final Object NULL_KEY = new Object(); 与其对应的两个方法便是： private static Object maskNull(Object key) { return (key == null) ? NULL_KEY : key; } static Object unmaskNull(Object key) { return (key == NULL_KEY) ? null : key; } 所以，其他WeakHashMap中的Entry最大的不同就是继承自WeakReference，并把key保存在了WeakReference中。可以说WeakHashMap的特性绝大部分都是WeakReference的功劳。 常用方法 主要的方法有这些： void clear() Object clone() boolean containsKey(Object key) boolean containsValue(Object value) Set<Entry<K, V>> entrySet() V get(Object key) boolean isEmpty() Set<K> keySet() V put(K key, V value) void putAll(Map<? extends K, ? extends V> map) V remove(Object key) int size() Collection<V> values() 这里选其中的三个最常用的方法进行解析： put方法 public V put(K key, V value) { // 处理null值 Object k = maskNull(key); // 计算hash int h = hash(k); // 获取table Entry<K,V>[] tab = getTable(); // 计算下标 int i = indexFor(h, tab.length); // 查找Entry for (Entry<K,V> e = tab[i]; e != null; e = e.next) { if (h == e.hash && eq(k, e.get())) { V oldValue = e.value; if (value != oldValue) e.value = value; return oldValue; } } modCount++; Entry<K,V> e = tab[i]; tab[i] = new Entry<>(k, value, queue, h, e); // 如果元素个数超过阈值，则进行扩容 if (++size >= threshold) resize(tab.length * 2); return null; } 这里涉及到的方法比较多，不慌不慌，一个一个来。 先来看看hash方法： final int hash(Object k) { int h = k.hashCode(); // 这里做了二次散列，来扩大低位的影响 h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } hash方法对key的hashcode进行了二次散列，主要是为了扩大低位的影响。因为Entry数组的大小是2的幂，在进行查找的时候，进行掩码处理，如果不进行二次散列，那么低位对index就完全没有影响了，如果不清楚也没有关系，之后在get方法里会有说明。 至于为什么要选20,12,7,4。emmm，大概是效果奇佳吧（一本正经的胡说八道，有兴趣的话可以自行研究）。 再看看indexFor函数，这里就是将数组长度减1后与hashcode做一个位与操作，因为length必定是2的幂，所以减1后就变成了掩码，再进行与操作就能直接得到hashcode mod length的结果了，但是这样操作效率会更高。 private static int indexFor(int h, int length) { return h & (length-1); } 再来看看getTable方法： private Entry<K,V>[] getTable() { // 清除被回收的Entry对象 expungeStaleEntries(); return table; } private void expungeStaleEntries() { for (Object x; (x = queue.poll()) != null; ) { // 循环获取引用队列中的对象 synchronized (queue) { @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>) x; // 查找对应的位置 int i = indexFor(e.hash, table.length); // 找到之前的Entry Entry<K,V> prev = table[i]; Entry<K,V> p = prev; // 在链表中寻找 while (p != null) { Entry<K,V> next = p.next; if (p == e) { if (prev == e) table[i] = next; else prev.next = next; // 将对应的value置为null，帮助GC回收 e.value = null; size--; break; } prev = p; p = next; } } } } 所以每次调用getTable的时候，都会将table中key已经被回收掉的Entry移除掉。 resize方法： void resize(int newCapacity) { // 获取当前table Entry<K,V>[] oldTable = getTable(); int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } // 新建一个table Entry<K,V>[] newTable = newTable(newCapacity); // 将旧table中的内容复制到新table中 transfer(oldTable, newTable); table = newTable; if (size >= threshold / 2) { threshold = (int)(newCapacity * loadFactor); } else { expungeStaleEntries(); transfer(newTable, oldTable); table = oldTable; } } // 新建Entry数组 private Entry<K,V>[] newTable(int n) { return (Entry<K,V>[]) new Entry<?,?>[n]; } private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) { for (int j = 0; j < src.length; ++j) { Entry<K,V> e = src[j]; src[j] = null; while (e != null) { Entry<K,V> next = e.next; Object key = e.get(); if (key == null) { e.next = null; e.value = null; size--; } else { int i = indexFor(e.hash, dest.length); e.next = dest[i]; dest[i] = e; } e = next; } } } get方法 public V get(Object key) { // 对null值特殊处理 Object k = maskNull(key); // 取key的hash值 int h = hash(k); // 取当前table Entry<K,V>[] tab = getTable(); // 获取下标 int index = indexFor(h, tab.length); Entry<K,V> e = tab[index]; // 链表中查找元素 while (e != null) { if (e.hash == h && eq(k, e.get())) return e.value; e = e.next; } return null; } 在查找元素的时候调用了一个eq方法： private static boolean eq(Object x, Object y) { return x == y || x.equals(y); } remove方法 public V remove(Object key) { // 对null值特殊处理 Object k = maskNull(key); // 取key的hash int h = hash(k); // 取当前table Entry<K,V>[] tab = getTable(); // 计算下标 int i = indexFor(h, tab.length); Entry<K,V> prev = tab[i]; Entry<K,V> e = prev; while (e != null) { Entry<K,V> next = e.next; // 查找对应Entry if (h == e.hash && eq(k, e.get())) { modCount++; size--; if (prev == e) tab[i] = next; else prev.next = next; // 如果找到，返回对应Entry的value return e.value; } prev = e; e = next; } return null; } 使用栗子 public class WeakHashMapTest { public static void main(String[] args){ testWeakHashMap(); } private static void testWeakHashMap() { // 创建3个String对象用来做key String w1 = new String("key1"); String w2 = new String("key2"); String w3 = new String("key3"); // 新建WeakHashMap Map weakHashMap = new WeakHashMap(); // 添加键值对 weakHashMap.put(w1, "v1"); weakHashMap.put(w2, "v2"); weakHashMap.put(w3, "v3"); // 打印出weakHashMap System.out.printf("weakHashMap:%s\n", weakHashMap); // containsKey(Object key) :是否包含键key System.out.printf("contains key key1 : %s\n",weakHashMap.containsKey("key1")); System.out.printf("contains key key4 : %s\n",weakHashMap.containsKey("key4")); // containsValue(Object value) :是否包含值value System.out.printf("contains value v1 : %s\n",weakHashMap.containsValue("v1")); System.out.printf("contains value 0 : %s\n",weakHashMap.containsValue(0)); // remove(Object key) ： 删除键key对应的键值对 weakHashMap.remove("three"); System.out.printf("weakHashMap: %s\n", weakHashMap); // ---- 测试 WeakHashMap 的自动回收特性 ---- // 将w1设置null。 // 这意味着“弱键”w1再没有被其它对象引用，调用gc时会回收WeakHashMap中与“w1”对应的键值对 w1 = null; // 内存回收。这里，会回收WeakHashMap中与“w1”对应的键值对 System.gc(); // 遍历WeakHashMap Iterator iter = weakHashMap.entrySet().iterator(); while (iter.hasNext()) { Map.Entry en = (Map.Entry)iter.next(); System.out.printf("next : %s - %s\n",en.getKey(),en.getValue()); } // 打印WeakHashMap的实际大小 System.out.printf("after gc WeakHashMap size:%s\n", weakHashMap.size()); } } 输出如下： weakHashMap:{key1=w1, key2=w2, key3=w3} contains key key1 : true contains key key4 : false contains value w1 : true contains value 0 : false weakHashMap: {key1=w1, key2=w2, key3=w3} next : key2 - w2 next : key3 - w3 after gc WeakHashMap size:2 可以看到，w1对应的Entry被回收掉了，这就是WeakHashMap的最重要特性，当然，实际使用的时候一般不会这样使用， 应用场景 由于WeakHashMap可以自动清除Entry，所以比较适合用于存储非必需对象，用作缓存非常合适。 public final class ConcurrentCache<K,V> { private final int size; private final Map<K,V> eden; private final Map<K,V> longterm; public ConcurrentCache(int size) { this.size = size; this.eden = new ConcurrentHashMap<>(size); this.longterm = new WeakHashMap<>(size); } public V get(K k) { V v = this.eden.get(k); if (v == null) { synchronized (longterm) { v = this.longterm.get(k); } if (v != null) { this.eden.put(k, v); } } return v; } public void put(K k, V v) { if (this.eden.size() >= size) { synchronized (longterm) { this.longterm.putAll(this.eden); } this.eden.clear(); } this.eden.put(k, v); } } 在put方法里，在插入一个键值对时，先检查eden缓存的容量是不是超过了阈值，如果没有超就直接放入eden缓存，如果超了就将eden中所有的键值对都放入longterm（这里longterm类似于老年代，eden类似于年轻代），再将eden清空并插入相应键值对。 在get方法中，也是优先从eden中找对应的value，如果没有则进入longterm缓存中查找，找到后就加入eden缓存并返回。 这样设计的好处是，能将相对常用的对象都能在eden缓存中找到，不常用的则存入longterm缓存，并且由于WeakHashMap能自动清除Entry，所以不用担心longterm中键值对过多而导致OOM。 WeakHashMap还有这样一个不错的应用场景，配合事务进行使用，存储事务过程中的各类信息。可以使用如下结构： WeakHashMap<String,Map<K,V>> transactionCache; 这里key为String类型，可以用来标志区分不同的事务，起到一个事务id的作用。value是一个map，可以是一个简单的HashMap或者LinkedHashMap，用来存放在事务中需要使用到的信息。 在事务开始时创建一个事务id，并用它来作为key，事务结束后，将这个强引用消除掉，这样既能保证在事务中可以获取到所需要的信息，又能自动释放掉map中的所有信息。 小结 WeakHashMap是一个会自动清除Entry的Map WeakHashMap的操作与HashMap完全一致 WeakHashMap内部数据结构是数组+链表 WeakHashMap常被用作缓存
2018-10-10
优秀的个人博客,低调大师

【Java入门提高篇】Day33 Java容器类详解（十五）PriorityQueue详解

今天要介绍的是基础容器类（为了与并发容器类区分开来而命名的名字）中的另一个成员——PriorityQueue，它的大名叫做优先级队列，想必即使没有用过也该有所耳闻吧，什么？没。。没听过？emmm。。。那就更该认真看看了。 通过本篇你将了解到： 1、PriorityQueue是什么？ 2、PriorityQueue的内部结构是什么？ 3、二叉堆、大顶堆、小顶堆分别是什么？有什么特性？ 4、小顶堆是如何实现的，如何用数组表示？ 5、小顶堆的删除、插入操作是如何进行的？ 6、PriorityQueue的源码解析。 7、PriorityQueue的应用场景。 一、PriorityQueue简介 PriorityQueue也是Queue的一个继承者，相比于一般的列表，它的特点便如它的名字一样，出队的时候可以按照优先级进行出队，所以不像LinkedList那样只能按照插入的顺序出队，PriorityQueue是可以根据给定的优先级顺序进行出队的。这里说的给定优先级顺序既可以是内部比较器，也可以是外部比较器。PriorityQueue内部是根据小顶堆的结构进行存储的，所谓小顶堆的意思，便是最小的元素总是在最上面，每次出队总是将堆顶元素移除，这样便能让出队变得有序，至于什么是小顶堆，后面会有详细介绍。 比如说，比较常见的场景就是任务队列，队列动态插入，后面的任务优先级高的需要被先执行，那么使用优先级队列就可以比较好的实现这样的需求。下面我们模拟一下这个场景： public class PriorityQueueTest { public static void main(String[] args){ // 传入外部比较器， //PriorityQueue<Task> taskQueue = new PriorityQueue<>(Comparator.comparingInt(Task::getPriority)); //PriorityQueue<Task> taskQueue = new PriorityQueue<>((t1, t2) -> t1.getPriority() - t2.getPriority()); PriorityQueue<Task> taskQueue = new PriorityQueue<>(new Comparator<Task>() { @Override public int compare(Task t1, Task t2) { return t1.getPriority() - t2.getPriority(); } }); // 添加六个任务 taskQueue.add(new Task(1, "learn java")); taskQueue.add(new Task(3, "learn c++")); taskQueue.add(new Task(4, "learn c#")); taskQueue.add(new Task(2, "learn python")); taskQueue.add(new Task(2, "learn php")); taskQueue.add(new Task(5, "learn js")); // 出队 while (!taskQueue.isEmpty()){ System.out.println(taskQueue.poll()); } } } class Task{ /** * 任务优先级 */ private int priority; /** * 任务名称 */ private String taskName; public Task() { } public Task(int priority, String taskName) { this.priority = priority; this.taskName = taskName; } public int getPriority() { return priority; } public void setPriority(int priority) { this.priority = priority; } public String getTaskName() { return taskName; } public void setTaskName(String taskName) { this.taskName = taskName; } @Override public String toString() { return "Task{" + "priority=" + priority + ", taskName='" + taskName + '\'' + '}'; } } 输出如下： Task{priority=1, taskName='learn java'} Task{priority=2, taskName='learn python'} Task{priority=2, taskName='learn php'} Task{priority=3, taskName='learn c++'} Task{priority=4, taskName='learn c#'} Task{priority=5, taskName='learn js'} 可以看到，输出的时候是按照我们设定的优先级顺序进行输出的，由于默认的是小顶堆，所以这里Priority值小的会被先输出。 二、PriorityQueue的内部结构 上面已经提到了，PriorityQueue的内部结构其实是按照小顶堆的结构进行存储的，那么什么是小顶堆呢？说到小顶堆，还是先从堆开始介绍吧。 堆和栈一样是一种很基础的数据结构，在维基百科中的介绍如下： 堆（英语：Heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。 用图来表示的话就像这样： 说完了堆，再来聊聊它的进化版——二叉堆，同样引用维基百科中的介绍： 二叉堆（英语：binary heap）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。 当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。 其中，最大堆也叫做大顶堆或者大根堆，最小堆也叫做小顶堆或者小根堆。上面的图一其实就是一个大顶堆，而图二则是小顶堆。PriorityQueue是通过数组表示的小顶堆实现的，既然如此，PriorityQueue的排序特性自然与小顶堆的特性一致，下面便介绍小顶堆如何使用数组进行表示以及插入删除时的调整。 下面是一个由10，16，20，22，18，25，26，30，24，23构成的小顶堆： 将其从第一个元素开始依次从上到下，从左到右给每个元素添加一个序号，从0开始，这样就得到了相应元素在数组中的位置，而且这个序号是很有规则的，第k个元素的左孩子的序号为2k+1，右孩子的序号为2k+2，这样就很容易根据序号直接算出对应孩子的位置，时间复杂度为o(1)。这也就是为什么可以用数组来存储堆结构的原因了。 再来看看小顶堆是如何插入元素的，假设我们插入一个元素15： 插入元素的调整其实很简单，就是先插入到最后，然后再依次与其父节点进行比较，如果小于其父节点，则互换，直到不需要调整或者父节点为null为止。 那再来看看移除元素： 嗯，过程其实也很简单，先用最后的元素当替补，然后再从上往下进行调整。 三、PriorityQueue源码解析 小顶堆已经介绍完了，那PriorityQueue就没什么内容可讲了，嗯，那散了吧好了好了，不开玩笑了，接下来让我们一起来看看源码中是如何实现的。 先来继承结构： PriorityQueue继承自AbstractQueue，像这样的Abstract开头的抽象类，想必应该不陌生了，就是继承自指定接口然后进行了一些默认实现。 来看看PriorityQueue的内部成员： // 默认初始化容量 private static final int DEFAULT_INITIAL_CAPACITY = 11; /** * 优先级队列是使用平衡二叉堆表示的: 节点queue[n]的两个孩子分别为 * queue[2*n+1] 和 queue[2*(n+1)]. 队列的优先级是由比较器或者 * 元素的自然排序决定的， 对于堆中的任意元素n，其后代d满足：n<=d * 如果堆是非空的，则堆中最小值为queue[0]。 */ transient Object[] queue; /** * 队列中元素个数 */ private int size = 0; /** * 比较器 */ private final Comparator<? super E> comparator; /** * 修改次数 */ transient int modCount = 0; 可以看到内部使用的是一个Object数组进行元素的存储，并对该数组进行了详细的注释，所以不管是根据子节点找父节点，还是根据父节点找子节点都肥肠的方便。 再来看看它的构造函数，有点多，一共有六个构造函数： /** * 使用默认的容量（11）来构造一个空的优先级队列，使用元素的自然顺序进行排序（此时元素必须实现comparable接口） */ public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY, null); } /** * 使用指定容量来构造一个空的优先级队列，使用元素的自然顺序进行排序（此时元素必须实现comparable接口） * 但如果指定的容量小于1则会抛出异常 */ public PriorityQueue(int initialCapacity) { this(initialCapacity, null); } /** * 使用默认的容量（11）构造一个优先级队列，使用指定的比较器进行排序 */ public PriorityQueue(Comparator<? super E> comparator) { this(DEFAULT_INITIAL_CAPACITY, comparator); } /** * 使用指定容量创建一个优先级队列，并使用指定比较器进行排序。 * 但如果指定的容量小于1则会抛出异常 */ public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) { if (initialCapacity < 1) throw new IllegalArgumentException(); this.queue = new Object[initialCapacity]; this.comparator = comparator; } /** * 使用指定集合的所有元素构造一个优先级队列， * 如果该集合为SortedSet或者PriorityQueue类型，则会使用相同的顺序进行排序， * 否则，将使用元素的自然排序（此时元素必须实现comparable接口），否则会抛出异常 * 并且集合中不能有null元素，否则会抛出异常 */ @SuppressWarnings("unchecked") public PriorityQueue(Collection<? extends E> c) { if (c instanceof SortedSet<?>) { SortedSet<? extends E> ss = (SortedSet<? extends E>) c; this.comparator = (Comparator<? super E>) ss.comparator(); initElementsFromCollection(ss); } else if (c instanceof PriorityQueue<?>) { PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c; this.comparator = (Comparator<? super E>) pq.comparator(); initFromPriorityQueue(pq); } else { this.comparator = null; initFromCollection(c); } } /** * 使用指定的优先级队列中所有元素来构造一个新的优先级队列. 将使用原有顺序进行排序。 */ @SuppressWarnings("unchecked") public PriorityQueue(PriorityQueue<? extends E> c) { this.comparator = (Comparator<? super E>) c.comparator(); initFromPriorityQueue(c); } /** * 根据指定的有序集合创建一个优先级队列，将使用原有顺序进行排序 */ @SuppressWarnings("unchecked") public PriorityQueue(SortedSet<? extends E> c) { this.comparator = (Comparator<? super E>) c.comparator(); initElementsFromCollection(c); } 从集合中构造优先级队列的时候，调用了几个初始化函数： private void initFromPriorityQueue(PriorityQueue<? extends E> c) { if (c.getClass() == PriorityQueue.class) { this.queue = c.toArray(); this.size = c.size(); } else { initFromCollection(c); } } private void initElementsFromCollection(Collection<? extends E> c) { Object[] a = c.toArray(); // If c.toArray incorrectly doesn't return Object[], copy it. if (a.getClass() != Object[].class) a = Arrays.copyOf(a, a.length, Object[].class); int len = a.length; if (len == 1 || this.comparator != null) for (int i = 0; i < len; i++) if (a[i] == null) throw new NullPointerException(); this.queue = a; this.size = a.length; } private void initFromCollection(Collection<? extends E> c) { initElementsFromCollection(c); heapify(); } initFromPriorityQueue即从另外一个优先级队列构造一个新的优先级队列，此时内部的数组元素不需要进行调整，只需要将原数组元素都复制过来即可。但是从其他非PriorityQueue的集合中构造优先级队列时，需要先将元素复制过来后再进行调整，此时调用的是heapify方法： private void heapify() { // 从最后一个非叶子节点开始从下往上调整 for (int i = (size >>> 1) - 1; i >= 0; i--) siftDown(i, (E) queue[i]); } // 划重点了，这个函数即对应上面的元素删除时从上往下调整的步骤 private void siftDown(int k, E x) { if (comparator != null) // 如果比较器不为null，则使用比较器进行比较 siftDownUsingComparator(k, x); else // 否则使用元素的compareTo方法进行比较 siftDownComparable(k, x); } private void siftDownUsingComparator(int k, E x) { // 使用half记录队列size的一半，如果比half小的话，说明不是叶子节点 // 因为最后一个节点的序号为size - 1，其父节点的序号为(size - 2) / 2或者(size - 3 ) / 2 // 所以half所在位置刚好是第一个叶子节点 int half = size >>> 1; while (k < half) { // 如果不是叶子节点，找出其孩子中较小的那个并用其替换 int child = (k << 1) + 1; Object c = queue[child]; int right = child + 1; if (right < size && comparator.compare((E) c, (E) queue[right]) > 0) c = queue[child = right]; if (comparator.compare(x, (E) c) <= 0) break; // 用c替换 queue[k] = c; k = child; } // queue[k] = x; } // 同上，只是比较的时候使用的是元素的compareTo方法 private void siftDownComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>)x; int half = size >>> 1; // 如果是非叶子节点则继续循环 while (k < half) { int child = (k << 1) + 1; Object c = queue[child]; int right = child + 1; if (right < size && ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0) c = queue[child = right]; if (key.compareTo((E) c) <= 0) break; queue[k] = c; k = child; } queue[k] = key; } 这里可能一眼看过去有点难以理解，嗯，那就多看两眼吧。 siftDown方法是这里面比较重要的方法之一，有两个参数，一个是序号k，另一个是元素x，这个方法的作用，便是把x从k开始往下调整，使得在节点k在其子树的每相邻层中，父节点都小于其子节点。所以heapify的作用就比较明显了，从最后一个非叶子节点开始，从下往上依次调整其子树，使得最终得到的树里，根节点是最小的。这里要先理解一下为什么heapify中i的初始值要设置为(size >>> 1) - 1。因为这是最后一个非叶子节点的位置，不信的话可以随便画几个图验证一下，至于在siftDownUsingComparator方法中，int half = size >>> 1;这里half则是第一个叶子节点的位置，小于这个序号的节点都是非叶子节点，这里也可以画图验证，当然，注释中我已经做了解释。 说了这么多，也许还是不太明白，以集合{14,7,12,6,9,4,17,23,10,15,3}为例画个图吧： 嗯，这样最小的元素就被顶上去了，有没有觉得有点像冒泡排序，嗯，确实有点像。 siftDown说完了，再来看一眼siftUp吧，这里操作是十分类似的。 private void siftUp(int k, E x) { if (comparator != null) siftUpUsingComparator(k, x); else siftUpComparable(k, x); } @SuppressWarnings("unchecked") private void siftUpComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>) x; while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if (key.compareTo((E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = key; } @SuppressWarnings("unchecked") private void siftUpUsingComparator(int k, E x) { while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if (comparator.compare(x, (E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = x; } 嗯，相信如果理解了siftDown的话，这里应该就不难理解了吧，如果还有疑问，欢迎留言。 再来看看几个常用的方法： public boolean add(E e) { return offer(e); } public boolean offer(E e) { if (e == null) throw new NullPointerException(); modCount++; int i = size; if (i >= queue.length) grow(i + 1); size = i + 1; if (i == 0) queue[0] = e; else siftUp(i, e); return true; } // 扩容函数 private void grow(int minCapacity) { int oldCapacity = queue.length; // 如果当前容量比较小（小于64）的话进行双倍扩容，否则扩容50% int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1)); // 如果发现扩容后溢出了，则进行调整 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); queue = Arrays.copyOf(queue, newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } public boolean contains(Object o) { return indexOf(o) != -1; } private int indexOf(Object o) { if (o != null) { // 查找时需要进行全局遍历，比搜索二叉树的查找效率要低 for (int i = 0; i < size; i++) if (o.equals(queue[i])) return i; } return -1; } public E poll() { if (size == 0) return null; int s = --size; modCount++; E result = (E) queue[0]; E x = (E) queue[s]; queue[s] = null; if (s != 0) siftDown(0, x); return result; } 这里对照一下最开始说的小顶堆的插入和移除就能比较好的理解了。 最后源码中还有一个remove方法，需要稍微说明一下： // 这里不是移除堆顶元素，而是移除指定元素 public boolean remove(Object o) { // 先找到该元素的位置 int i = indexOf(o); if (i == -1) return false; else { removeAt(i); return true; } } // 移除指定序号的元素 private E removeAt(int i) { // assert i >= 0 && i < size; modCount++; // s为最后一个元素的序号 int s = --size; if (s == i) queue[i] = null; else { // moved记录最后一个元素的值 E moved = (E) queue[s]; queue[s] = null; // 用最后一个元素代替要移除的元素，并向下进行调整 siftDown(i, moved); // 如果向下调整后发现moved还在该位置，则再向上进行调整 if (queue[i] == moved) { siftUp(i, moved); if (queue[i] != moved) return moved; } } return null; } 当移除的不是堆顶元素的时候，同样先用最后一个元素代替，然后先从被移除的位置开始向下调整，如果发现没有改动，则再向上调整。 四、PriorityQueue的应用场景 最后，来聊聊PriorityQueue的应用场景，由于内部是用数组实现的小顶堆，所以堆适用的场景它都适用，比如典型的从n个元素中取出最小（最大）的前k个，这样的场景适用PriorityQueue就能以比较小的空间代价和还算ok的时间代价进行实现，另外，优先级队列适用场景的特点便是需要动态插入元素，并且元素有优先级，需要根据一定的规则进行优先级排序。 下面以从10000个整数中取出最大的10个整数为例进行介绍。 public class Test { public static void main(String[] args){ ArrayList<Integer> integers = new ArrayList<>(10000); Random random = new Random(); for (int i = 0; i < 10000; i++) { Integer integer = random.nextInt(); if (!integers.contains(integer)) integers.add(integer); } Integer[] largest = getLargest10(integers); for (Integer i : largest){ System.out.print(i + " "); } System.out.println(); // 验证一下是否是最大的前10个 integers.sort(Comparator.comparingInt(Integer::intValue)); ArrayList<Integer> largest2 = new ArrayList<>(10); for (int i = integers.size() - 1; i >= integers.size() - 10; i--){ largest2.add(integers.get(i)); } // 在largest数组中查找 System.out.println(Arrays.asList(largest).containsAll(largest2)); } public static Integer[] getLargest10(ArrayList<Integer> integers){ PriorityQueue<Integer> queue = new PriorityQueue<>(10); for (Integer integer : integers){ queue.add(integer); if (queue.size() > 10){ queue.poll(); } } return queue.toArray(new Integer[10]); } } 输出如下，由于是取的随机数，所以每个人的输出都会不一样。 2143974860 2143998490 2144350843 2145111627 2144739333 2145674658 2144667271 2145543903 2147209906 2145466260 true 最后，我们来回答一下开头的问题： 1、PriorityQueue是什么？PriorityQueue是优先级队列，取出元素时会根据元素的优先级进行排序。 2、PriorityQueue的内部结构是什么？PriorityQueue内部是一个用数组实现的小顶堆。 3、二叉堆、大顶堆、小顶堆分别是什么？有什么特性？二叉堆是完全二叉树或者近完全二叉树，大顶堆即所有父节点大于子节点，小顶堆即所有父节点小于子节点。 4、小顶堆是如何实现的，如何用数组表示？小顶堆是用二叉树实现的，用数组表示时，父节点n的左孩子为2n+1，右孩子的序号为2n+2。 5、小顶堆的删除、插入操作是如何进行的？小顶堆删除堆顶元素后用最后一个元素替补，然后从上往下调整，插入一个元素时，先放到最后的位置，然后再从下往上调整。 6、PriorityQueue的源码解析。如上。 7、PriorityQueue的应用场景。适用于需要动态插入元素，且元素有优先级顺序的场景。 到此，本篇圆满结束。如果觉得还不错的话，记得动动小手点个赞，也欢迎关注博主，你们的支持是我写出更好博客的动力。 有兴趣对Java进行更深入学习和交流的小伙伴，欢迎加入QQ群交流：529253292
2018-09-09
优秀的个人博客,低调大师

【Java入门提高篇】Day32 Java容器类详解（十四）ArrayDeque详解

今天来介绍一个不太常见也不太常用的类——ArrayDeque，这是一个很不错的容器类，如果对它还不了解的话，那么就好好看看这篇文章吧。 看完本篇，你将会了解到： 1、ArrayDeque是什么？ 2、ArrayDeque如何使用？ 3、ArrayDeque的内部结构是怎样的？ 4、ArrayDeque的各个方法是如何实现的？ 5、ArrayDeque是如何扩容的？ 6、ArrayDeque的容量有什么限制？ 7、ArrayDeque和LinkedList相比有什么优势？ 8、ArrayDeque的应用场景是什么？ 一、ArrayDeque简介 ArrayDeque是JDK容器中的一个双端队列实现，内部使用数组进行元素存储，不允许存储null值，可以高效的进行元素查找和尾部插入取出，是用作队列、双端队列、栈的绝佳选择，性能比LinkedList还要好。听到这里，不熟悉ArrayDeque的你是不是有点尴尬？JDK中竟然还有这么好的一个容器类？ 别慌，现在了解还来得及，趁响指还没有弹下去，快上车吧，没时间解释了。 来看一个ArrayDeque的使用小栗子： public class DequeTest { public static void main(String[] args){ // 初始化容量为4 ArrayDeque<String> arrayDeque = new ArrayDeque<>(4); //添加元素 arrayDeque.add("A"); arrayDeque.add("B"); arrayDeque.add("C"); arrayDeque.add("D"); arrayDeque.add("E"); arrayDeque.add("F"); arrayDeque.add("G"); arrayDeque.add("H"); arrayDeque.add("I"); System.out.println(arrayDeque); // 获取元素 String a = arrayDeque.getFirst(); String a1 = arrayDeque.pop(); String b = arrayDeque.element(); String b1 = arrayDeque.removeFirst(); String c = arrayDeque.peek(); String c1 = arrayDeque.poll(); String d = arrayDeque.pollFirst(); String i = arrayDeque.pollLast(); String e = arrayDeque.peekFirst(); String h = arrayDeque.peekLast(); String h1 = arrayDeque.removeLast(); System.out.printf("a = %s, a1 = %s, b = %s, b1 = %s, c = %s, c1 = %s, d = %s, i = %s, e = %s, h = %s, h1 = %s", a,a1,b,b1,c,c1,d,i,e,h,h1); System.out.println(); // 添加元素 arrayDeque.push(e); arrayDeque.add(h); arrayDeque.offer(d); arrayDeque.offerFirst(i); arrayDeque.offerLast(c); arrayDeque.offerLast(h); arrayDeque.offerLast(c); arrayDeque.offerLast(h); arrayDeque.offerLast(i); arrayDeque.offerLast(c); System.out.println(arrayDeque); // 移除第一次出现的C arrayDeque.removeFirstOccurrence(c); System.out.println(arrayDeque); // 移除最后一次出现的C arrayDeque.removeLastOccurrence(c); System.out.println(arrayDeque); } } 输出如下： [A, B, C, D, E, F, G, H, I] a = A, a1 = A, b = B, b1 = B, c = C, c1 = C, d = D, i = I, e = E, h = H, h1 = H [I, E, E, F, G, H, D, C, H, C, H, I, C] [I, E, E, F, G, H, D, H, C, H, I, C] [I, E, E, F, G, H, D, H, C, H, I] 可以看到，从ArrayDeque中取出元素的姿势可谓是五花八门，不过别慌，稍后会对这些方法进行一一讲解，现在只需要知道，get、peek、element方法都是获取元素，但是不会将它移除，而pop、poll、remove都会将元素移除并返回，add和push、offer都是插入元素，它们的不同点在于插入元素的位置以及插入失败后的结果。 二、ArrayDeque的内部结构 ArrayDeque的整体继承结构如下： ArrayDeque是继承自Deque接口，Deque继承自Queue接口，Queue是队列，而Deque是双端队列，也就是可以从前或者从后插入或者取出元素，也就是比队列存取更加方便一点，单向队列只能从一头插入，从另一头取出。 再来看看ArrayDeque的内部结构，其实从名字就可以看出来，ArrayDeque自然是基于Array的双端队列，内部结构自然是数组： //存储元素的数组 transient Object[] elements; // 非private访问限制，以便内部类访问 /** * 头部节点序号 */ transient int head; /** * 尾部节点序号，（指向最后一点节点的后一个位置） */ transient int tail; /** * 双端队列的最小容量，必须是2的幂 */ private static final int MIN_INITIAL_CAPACITY = 8; 这里可以看到，元素都存储在Object数组中，head记录首节点的序号，tail记录尾节点后一个位置的序号，队列的容量最小为8，而且必须为2的幂。看到这里，有没有想到HashMap的元素个数限制也必须为2的幂，嗯，这里同HashMap一样，自有妙用，后面会有分析。 三、ArrayDeque的常用方法 从队列首部插入/取出 从队列尾部插入/取出 失败抛出异常 失败返回特殊值 失败抛出异常 失败返回特殊值 插入 addFirst(e) push() offerFirst(e) addLast(e) offerLast(e) 移除 removeFirst() pop() pollFirst() removeLast() pollLast() 获取 getFirst() peekFirst() getLast() peekLast() 嗯，几乎绝大多数常用方法都在这里了，基本上可以分成两类，一类是以add，remove，get开头的方法，这类方法失败后会抛出异常，一类是以offer，poll，peek开头的方法，这类方法失败之后会返回特殊值，如null。大部分方法基本上都是可以根据命名来推断其作用，如addFirst，当然就是从队列头部插入，removeLast，便是从队列尾部移除，get和peek只获取元素而不移除，getFirst方法调用时，如果队列为空，会抛出NoSuchElementException异常，而peekFirst在队列为空时调用则返回null。 一下摆出这么多方法有些难以接受？别慌别慌，接下来让我们从源码的角度一起来看看这些方法，用图说话，来解释我们最开始那个栗子中到底发生了哪些事情。 四、ArrayDeque源码分析 先来看看构造函数： /** * 构造一个初始容量为16的空队列 */ public ArrayDeque() { elements = new Object[16]; } /** * 构造一个能容纳指定大小的空队列 */ public ArrayDeque(int numElements) { allocateElements(numElements); } /** * 构造一个包含指定集合所有元素的队列 */ public ArrayDeque(Collection<? extends E> c) { allocateElements(c.size()); addAll(c); } 所以之前栗子中， ArrayDeque<String> arrayDeque = new ArrayDeque<>(4); 调用的是第二个构造函数，里面有这么一个函数allocateElements，让我们来看看它的实现： 1 private void allocateElements(int numElements) { 2 elements = new Object[calculateSize(numElements)]; 3 } 4 5 private static int calculateSize(int numElements) { 6 int initialCapacity = MIN_INITIAL_CAPACITY; 7 if (numElements >= initialCapacity) { 8 initialCapacity = numElements; 9 initialCapacity |= (initialCapacity >>> 1); 10 initialCapacity |= (initialCapacity >>> 2); 11 initialCapacity |= (initialCapacity >>> 4); 12 initialCapacity |= (initialCapacity >>> 8); 13 initialCapacity |= (initialCapacity >>> 16); 14 initialCapacity++; 15 16 if (initialCapacity < 0) 17 initialCapacity >>>= 1; 18 } 19 return initialCapacity; 20 } allocateElements方法主要用于给内部的数组分配合适大小的空间，calculateSize方法用于计算比numElements大的最小2的幂次方，如果指定的容量大小小于MIN_INITIAL_CAPACITY（值为8），那么将容量设置为8，否则通过多次无符号右移进行最小2次幂计算。先将initialCapacity赋值为numElements，接下来，进行5次无符号右移，下面将以一个小栗子介绍这样运算的妙处。 在Java中，int类型是占4字节，也就是32位。简单起见，这里以一个8位二进制数来演示前三次操作。假设这个二进制数对应的十进制为89，整个过程如下： 可以看到最后，除了第一位，其他位全部变成了1，然后这个结果再加一，即得到大于89的最小的2次幂，怎么样，很巧妙吧，也许你会想，为什么右移的数值要分别是1，2，4，8，16呢？嗯，好问题。其实仔细观察就会发现，先右移在进行或操作，其实我们只需要关注第一个不为0的位即可，下面以64为例再演示一次： 所以，事实上，在这系列操作中，其他位只是配角，我们只需要关注第一个不为0的位即可，假设其为第n位，先右移一位然后进行或操作，得到的结果，第n位和第n-1位肯定为1，这样就有两个位为1了，然后进行右移两位，再进行或操作，那么第n位到第n-3位一定都为1，然后右移4位，依次类推。int为32位，因此，最后只需要移动16位即可。1+2+4+8+16 = 31，所以经过这一波操作，原数字对应的二进制，操作得到的结果将是从其第一个不为0的位开始，往后的位均为1。然后： initialCapacity++; 再自增一下，目标完成。观察到还有下面这一小节代码： if (initialCapacity < 0) initialCapacity >>>= 1; 其实它是为了防止进行这一波操作之后，得到了负数，即原来第31位为1，得到的结果第32位将为1，第32位为符号位，1代表负数，这样的话就必须回退一步，将得到的数右移一位（即2 ^ 30）。 嗯，那么这一部分就先告一段落了。 来看看之前的那些函数。 public boolean add(E e) { addLast(e); return true; } /** * 在队列头部插入元素，如果元素为null，则抛出异常 */ public void addFirst(E e) { if (e == null) throw new NullPointerException(); elements[head = (head - 1) & (elements.length - 1)] = e; if (head == tail) doubleCapacity(); } /** * 在队列尾部插入元素，如果元素为null，则抛出异常 */ public void addLast(E e) { if (e == null) throw new NullPointerException(); elements[tail] = e; if ( (tail = (tail + 1) & (elements.length - 1)) == head) doubleCapacity(); } add的几个函数比较简单，在头部或者尾部插入元素，如果直接调用add方法，则是在尾部插入，这时直接在对应位置塞入该元素即可。 elements[tail] = e; 然后把tail记录其后一个位置，如果tail记录的位置已经是数组的最后一个位置了怎么办？嗯，这里又有一个巧妙的操作，跟HashMap中的取模是一样的： tail = (tail + 1) & (elements.length - 1) 因为elements.length是2的幂次方，所以减一后就变成了掩码，tail如果记录的是最后一个位置，即elements.length - 1，tail + 1 则等于elements.length，与elements.length - 1 做与操作后，就变成了0，嗯，没错，这样就变成了一个循环数组，如果tail与head相等，则表示没有剩余空间可以存放更多元素了，则调用doubleCapacity进行扩容： private void doubleCapacity() { assert head == tail; int p = head; int n = elements.length; int r = n - p; // number of elements to the right of p int newCapacity = n << 1; if (newCapacity < 0) throw new IllegalStateException("Sorry, deque too big"); Object[] a = new Object[newCapacity]; System.arraycopy(elements, p, a, 0, r); System.arraycopy(elements, 0, a, r, p); elements = a; head = 0; tail = n; } 扩容其实也是很简单粗暴的，先记录一下原来head的位置，然后把容量变为原来的两倍，然后把head之后的元素复制到新数组的开头，把剩余的元素复制到新数组之后。以之前的栗子为例，新建的ArrayDeque实例容量为8，然后我们调用add插入元素，插入H之后，tail指向第一个位置，与head重合，就会触发扩容。 arrayDeque.add("A"); arrayDeque.add("B"); arrayDeque.add("C"); arrayDeque.add("D"); arrayDeque.add("E"); arrayDeque.add("F"); arrayDeque.add("G"); arrayDeque.add("H"); arrayDeque.add("I"); 看图应该就比较清楚了，然后来看看获取元素的几个方法： // 获取元素 String a = arrayDeque.getFirst(); String a1 = arrayDeque.pop(); String b = arrayDeque.element(); String b1 = arrayDeque.removeFirst(); String c = arrayDeque.peek(); String c1 = arrayDeque.poll(); String d = arrayDeque.pollFirst(); String i = arrayDeque.pollLast(); String e = arrayDeque.peekFirst(); String h = arrayDeque.peekLast(); String h1 = arrayDeque.removeLast(); System.out.printf("a = %s, a1 = %s, b = %s, b1 = %s, c = %s, c1 = %s, d = %s, i = %s, e = %s, h = %s, h1 = %s", a,a1,b,b1,c,c1,d,i,e,h,h1); System.out.println(); getFirst方法直接取head位置的元素，如果为null则抛出异常。 public E getFirst() { @SuppressWarnings("unchecked") E result = (E) elements[head]; if (result == null) throw new NoSuchElementException(); return result; } getLast也是类似，取出tail所在位置的前一个位置，这里也做了掩码操作。 public E getLast() { @SuppressWarnings("unchecked") E result = (E) elements[(tail - 1) & (elements.length - 1)]; if (result == null) throw new NoSuchElementException(); return result; } element方法直接调用的是getFirst方法： public E element() { return getFirst(); } remove方法有三个： public E remove() { return removeFirst(); } public E removeFirst() { E x = pollFirst(); if (x == null) throw new NoSuchElementException(); return x; } public E removeLast() { E x = pollLast(); if (x == null) throw new NoSuchElementException(); return x; } remove方法其实是调用的对应的poll方法，poll方法也有三个： public E poll() { return pollFirst(); } public E pollFirst() { int h = head; @SuppressWarnings("unchecked") E result = (E) elements[h]; // 如果结果为null则返回null if (result == null) return null; elements[h] = null; // Must null out slot head = (h + 1) & (elements.length - 1); return result; } public E pollLast() { int t = (tail - 1) & (elements.length - 1); @SuppressWarnings("unchecked") E result = (E) elements[t]; if (result == null) return null; elements[t] = null; tail = t; return result; } 其实也很简单，都是先取出对应的元素，如果为null则返回null，否则取出对应的元素并对head或tail进行调整。 pop方法调用的是removeFirst方法，removeFIrst方法调用的是pollFirst方法，所以方法看起来这么多，实际上最后真正调用的就那么几个。 public E pop() { return removeFirst(); } peek方法是取出元素但是不移除，也有三个方法： public E peek() { return peekFirst(); } @SuppressWarnings("unchecked") public E peekFirst() { // elements[head] is null if deque empty return (E) elements[head]; } @SuppressWarnings("unchecked") public E peekLast() { return (E) elements[(tail - 1) & (elements.length - 1)]; } 这里没有做任何校验，所以如果如果取到的元素是null，返回的也是null。 再来看看插入元素的其它几个方法： public boolean offer(E e) { return offerLast(e); } public boolean offerLast(E e) { addLast(e); return true; } public boolean offerFirst(E e) { addFirst(e); return true; } public void push(E e) { addFirst(e); } offer方法直接调用的是add方法。 emmm，都是相互调用，为啥要设置那么多方法呢？其实主要是为了模拟不同的数据结构，如栈操作：pop，push，peek，队列操作：add，offer，remove，poll，peek，element，双端队列操作：addFirst，addLast，getFirst，getLast，peekFirst，peekLast，removeFirst，removeLast，pollFirst，pollLast。不过确实稍微多了一点。 之前的栗子里还有用到两个方法，removeFirstOccurrence和removeLastOccurrence，前者是移除首次出现的位置，后者是移除最后一次出现的位置。 public boolean removeFirstOccurrence(Object o) { if (o == null) return false; int mask = elements.length - 1; int i = head; Object x; while ( (x = elements[i]) != null) { if (o.equals(x)) { delete(i); return true; } i = (i + 1) & mask; } return false; } public boolean removeLastOccurrence(Object o) { if (o == null) return false; int mask = elements.length - 1; int i = (tail - 1) & mask; Object x; while ( (x = elements[i]) != null) { if (o.equals(x)) { delete(i); return true; } i = (i - 1) & mask; } return false; } 其实都是通过循环遍历的方式进行查找一个是从head开始往后查找，一个是从tail开始往前查找。 最后，我们再来看看它的迭代器类。 public Iterator<E> iterator() { return new DeqIterator(); } private class DeqIterator implements Iterator<E> { private int cursor = head; private int fence = tail; private int lastRet = -1; public boolean hasNext() { return cursor != fence; } public E next() { if (cursor == fence) throw new NoSuchElementException(); @SuppressWarnings("unchecked") E result = (E) elements[cursor]; if (tail != fence || result == null) throw new ConcurrentModificationException(); lastRet = cursor; cursor = (cursor + 1) & (elements.length - 1); return result; } public void remove() { if (lastRet < 0) throw new IllegalStateException(); if (delete(lastRet)) { cursor = (cursor - 1) & (elements.length - 1); fence = tail; } lastRet = -1; } public void forEachRemaining(Consumer<? super E> action) { Objects.requireNonNull(action); Object[] a = elements; int m = a.length - 1, f = fence, i = cursor; cursor = f; while (i != f) { @SuppressWarnings("unchecked") E e = (E)a[i]; i = (i + 1) & m; if (e == null) throw new ConcurrentModificationException(); action.accept(e); } } } 在迭代器类中，cursor记录的是head的位置，fence记录的是tail的位置，lastRet记录的是调用next返回的元素的序号，如果调用了remove方法，lastRet会置为-1，这里没有像其它容器那样使用modCount来实现fast-fail机制，而是通过在next方法中进行修改判断。 // 如果移除了尾部元素，会导致 tail != fence // 如果移除了头部元素，会导致 result == null if (tail != fence || result == null) throw new ConcurrentModificationException(); 当然，这种检测比较弱，如果先移除一个尾部元素，然后再添加一个尾部元素，那么tail依旧和fence相等，这种情况就检测不出来了。 在调用remove方法的时候，调用了一个delete方法，这是ArrayDeque类中的一个私有方法。 private boolean delete(int i) { // 先做不变性检测，判断是否当前结构满足删除需求 checkInvariants(); final Object[] elements = this.elements; // mask即掩码 final int mask = elements.length - 1; final int h = head; final int t = tail; // front代表i到头部的距离 final int front = (i - h) & mask; // back代表i到尾部的距离 final int back = (t - i) & mask; // 再次校验，如果i到头部的距离大于等于尾部到头部的距离，表示当前队列已经被修改了，通过最开始检测后，i是不应该满足该条件的 if (front >= ((t - h) & mask)) throw new ConcurrentModificationException(); // 为移动尽量少的元素做优化，如果离头部比较近，则将该位置到头部的元素进行移动，如果离尾部比较近，则将该位置到尾部的元素进行移动 if (front < back) { if (h <= i) { System.arraycopy(elements, h, elements, h + 1, front); } else { // Wrap around System.arraycopy(elements, 0, elements, 1, i); elements[0] = elements[mask]; System.arraycopy(elements, h, elements, h + 1, mask - h); } elements[h] = null; head = (h + 1) & mask; return false; } else { if (i < t) { // Copy the null tail as well System.arraycopy(elements, i + 1, elements, i, back); tail = t - 1; } else { // Wrap around System.arraycopy(elements, i + 1, elements, i, mask - i); elements[mask] = elements[0]; System.arraycopy(elements, 1, elements, 0, t); tail = (t - 1) & mask; } return true; } } 所以这个delete还是花了一点心思的，不仅做了两次校验，还对元素移动进行了优化。嗯，到此为止，源码部分就差不多了。 那么现在再回到最开始提的问题。 1、ArrayDeque是什么？ArrayDeque是一个用循环数组实现的双端队列。 2、ArrayDeque如何使用？通过add，offer，poll等方法进行操作。 3、ArrayDeque的内部结构是怎样的？内部结构是一个循环数组。 4、ArrayDeque的各个方法是如何实现的？嗯，见上文。 5、ArrayDeque是如何扩容的？扩容成原来的两倍，然后将原来的内容复制到新数组中。 6、ArrayDeque的容量有什么限制？容量必须为2的幂次方，最小为8，默认为16. 7、ArrayDeque和LinkedList相比有什么优势？ArrayDeque通常来说比LinkedList更高效，因为可以在常量时间通过序号对元素进行定位，并且省去了对元素进行包装的空间和时间成本。 8、ArrayDeque的应用场景是什么？在很多场景下可以用来代替LinkedList，可以用做队列或者栈。 到此，本篇圆满结束。如果觉得还不错的话，记得动动小手点个赞，也欢迎关注博主，你们的支持是我写出更好博客的动力。 有兴趣对Java进行更深入学习和交流的小伙伴，欢迎加入QQ群交流：529253292
2018-09-07
优秀的个人博客,低调大师

【Java入门提高篇】Day31 Java容器类详解（十三）TreeSet详解

上一篇很水的介绍完了TreeMap，这一篇来看看更水的TreeSet。 本文将从以下几个角度进行展开： 1、TreeSet简介和使用栗子 2、TreeSet源码分析 本篇大约需食用10分钟，各位看官请随意享用。 一、TreeSet简介 TreeSet是Set家族中的又一名懒将，跟其他两位一样，与对应的Map关系密不可分 我们先来回顾一下其他两个Set类，HashSet借助于HashMap拥有快速元素插入和查找的特性，LinkedHashSet借助于LinkedHashMap拥有快速插入查找以及使元素保持插入顺序的特性，TreeSet则是借助于TreeMap拥有使内部元素保持有序的特性，当然，所有的Set集合类都有元素去重的特性。当然，要区别一下的是，TreeSet中的有序是指可以按照内部比较器或者外部比较器的顺序对插入的元素进行排序，也就是每次插入后都会调整顺序以保持内部元素整体有序，而LinkedHashSet只能保持元素的插入顺序。 Talkischeap，showme your code.嗯，还是来看代码吧： public class TreeSetTest { public static void main(String[] args){ TreeSet<String> treeSet = new TreeSet<>(); treeSet.add("Frank"); treeSet.add("Alice"); treeSet.add("Bob"); treeSet.add("Allen"); treeSet.add("Ada"); treeSet.add("Adora"); System.out.println(treeSet); LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>(); linkedHashSet.add("Frank"); linkedHashSet.add("Alice"); linkedHashSet.add("Bob"); linkedHashSet.add("Allen"); linkedHashSet.add("Ada"); linkedHashSet.add("Adora"); System.out.println(linkedHashSet); } } 输出如下： [Ada, Adora, Alice, Allen, Bob, Frank] [Frank, Alice, Bob, Allen, Ada, Adora] 可以看到TreeSet给插入的元素自动排序了。那么可不可以放入我们自定义的类元素呢？当然是可以的，不然要它何用 public class TreeSetTest { public static void main(String[] args){ List<Goods> goods = new ArrayList<>(); goods.add(new Goods("Iphone4S",500.00)); goods.add(new Goods("Iphone5",800.00)); goods.add(new Goods("Iphone6S",2500.00)); goods.add(new Goods("Iphone7S",4500.00)); goods.add(new Goods("Iphone8",6500.00)); goods.add(new Goods("IphoneX",8500.00)); System.out.println(goods); TreeSet<Goods> treeSet = new TreeSet<>(); treeSet.addAll(goods); System.out.println(treeSet); LinkedHashSet<Goods> linkedHashSet = new LinkedHashSet<>(); linkedHashSet.addAll(goods); System.out.println(linkedHashSet); } public static class Goods{ private String name; private Double price; public Goods(String name, Double price) { this.name = name; this.price = price; } public String getName() { return name; } public void setName(String name) { this.name = name; } public Double getPrice() { return price; } public void setPrice(Double price) { this.price = price; } @Override public String toString() { return "Goods{" + "name='" + name + '\'' + ", price=" + price + '}'; } } } 输出如下： Exception in thread "main" java.lang.ClassCastException: com.frank.chapter22.TreeSetTest$Goods cannot be cast to java.lang.Comparable [Goods{name='Iphone4S', price=500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='IphoneX', price=8500.0}] at java.util.TreeMap.compare(TreeMap.java:1294) at java.util.TreeMap.put(TreeMap.java:538) at java.util.TreeSet.add(TreeSet.java:255) at java.util.AbstractCollection.addAll(AbstractCollection.java:344) at java.util.TreeSet.addAll(TreeSet.java:312) at com.frank.chapter22.TreeSetTest.main(TreeSetTest.java:25) 欢迎来到大型翻车现场。。。 别慌别慌，问题不大。TreeSet与TreeMap一样，是需要元素实现Comparable接口或者传入一个外部比较器的。为什么String可以不用？看看String的实现吧，人家可是实现了Comparable接口的。 所以有两种方式解决，一种是让Goods类实现Comparable接口，另一种是传入一个外部比较器，我们先来看第一种： public class TreeSetTest { public static void main(String[] args){ List<Goods> goods = new ArrayList<>(); goods.add(new Goods("Iphone7S",4500.00)); goods.add(new Goods("Iphone4S",500.00)); goods.add(new Goods("Iphone5",800.00)); goods.add(new Goods("IphoneX",8500.00)); goods.add(new Goods("Iphone6S",2500.00)); goods.add(new Goods("Iphone8",6500.00)); goods.add(new Goods("Iphone8",6500.00)); System.out.println(goods); TreeSet<Goods> treeSet = new TreeSet<>(); treeSet.addAll(goods); System.out.println(treeSet); LinkedHashSet<Goods> linkedHashSet = new LinkedHashSet<>(); linkedHashSet.addAll(goods); System.out.println(linkedHashSet); } public static class Goods implements Comparable{ private String name; private Double price; public Goods(String name, Double price) { this.name = name; this.price = price; } public String getName() { return name; } public void setName(String name) { this.name = name; } public Double getPrice() { return price; } public void setPrice(Double price) { this.price = price; } @Override public String toString() { return "Goods{" + "name='" + name + '\'' + ", price=" + price + '}'; } @Override public int compareTo(Object o) { if (!(o instanceof Goods)){ return -1; } Goods goods = (Goods) o; return this.price.compareTo(goods.getPrice()); } } } 为了看出效果，把几个商品的顺序调整了一下，输出如下： [Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone4S', price=500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='IphoneX', price=8500.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='Iphone8', price=6500.0}] [Goods{name='Iphone4S', price=500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='IphoneX', price=8500.0}] [Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone4S', price=500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='IphoneX', price=8500.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='Iphone8', price=6500.0}] 这里我们按价格进行了升序排列，接下来使用外部比较器的方式进行价格的倒序排列： public class TreeSetTest { public static void main(String[] args){ List<Goods> goods = new ArrayList<>(); goods.add(new Goods("Iphone7S",4500.00)); goods.add(new Goods("Iphone4S",500.00)); goods.add(new Goods("Iphone5",800.00)); goods.add(new Goods("IphoneX",8500.00)); goods.add(new Goods("Iphone6S",2500.00)); goods.add(new Goods("Iphone8",6500.00)); goods.add(new Goods("Iphone8",6500.00)); System.out.println(goods); // 1、使用Lamada表达式 //TreeSet<Goods> treeSet = new TreeSet<>((g1,g2) -> g2.getPrice().compareTo(g1.getPrice())); // 2、使用匿名内部类 TreeSet<Goods> treeSet = new TreeSet<>(new Comparator<Goods>() { @Override public int compare(Goods o1, Goods o2) { return o2.getPrice().compareTo(o1.getPrice()); } }); treeSet.addAll(goods); System.out.println(treeSet); LinkedHashSet<Goods> linkedHashSet = new LinkedHashSet<>(); linkedHashSet.addAll(goods); System.out.println(linkedHashSet); } public static class Goods{ private String name; private Double price; public Goods(String name, Double price) { this.name = name; this.price = price; } public String getName() { return name; } public void setName(String name) { this.name = name; } public Double getPrice() { return price; } public void setPrice(Double price) { this.price = price; } @Override public String toString() { return "Goods{" + "name='" + name + '\'' + ", price=" + price + '}'; } } } 在传入外部比较器的时候，也有很多种姿势，这里还是选了匿名内部类的方式进行传入，因为这里只需要使用一次，Lamada表达式还没有做介绍，这里就先不讲了，欣赏一下就好，先领略一下它的强大。 [Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone4S', price=500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='IphoneX', price=8500.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='Iphone8', price=6500.0}] [Goods{name='IphoneX', price=8500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='Iphone4S', price=500.0}] [Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone4S', price=500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='IphoneX', price=8500.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='Iphone8', price=6500.0}] 这样，就完成了倒序排列了，很简单吧。 二、TreeSet源码分析 先来看看TreeSet的继承关系图： 跟TreeMap的继承机构差不多，NavigableSet接口中存在大量的导航方法，可以帮助更快定位想要查找的元素，AbstractSet提供Set的部分默认实现，这样只需要实现其它方法即可。 可以看到，TreeSet中的方法并不是很多，除了导航方法之外，就是几个最常用的方法了，如add，addAll，remove，contains。接下来让我们一起看看这几个方法是如何实现的： 先来看看内部成员和构造函数： /** * 内部默默无闻工作的Map */ private transient NavigableMap<E,Object> m; // map中共用的一个value private static final Object PRESENT = new Object(); //默认构造方法，根据其元素的自然顺序进行排序 public TreeSet() { this(new TreeMap<E,Object>()); } //构造一个包含指定 collection 元素的新 TreeSet，它按照其元素的自然顺序进行排序。 public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<>(comparator)); } //构造一个新的空 TreeSet，它根据指定比较器进行排序。 public TreeSet(Collection<? extends E> c) { this(); addAll(c); } //构造一个与指定有序 set 具有相同映射关系和相同排序的新 TreeSet。 public TreeSet(SortedSet<E> s) { this(s.comparator()); addAll(s); } TreeSet(NavigableMap<E,Object> m) { this.m = m; } add方法，嗯，够简明扼要。 public boolean add(E e) { return m.put(e, PRESENT)==null; } addAll： public boolean addAll(Collection<? extends E> c) { // 先检测集合是否继承了SortedSet接口，内部map是否为TreeMap // 并且检测使用的比较器是否与内部Map的比较器一致 // 如果一致的话则使用TreeMap的addAllForTreeSet方法进行批量插入 // addAllForTreeSet方法可以在常量时间对有序元素进行插入 if (m.size()==0 && c.size() > 0 && c instanceof SortedSet && m instanceof TreeMap) { SortedSet<? extends E> set = (SortedSet<? extends E>) c; TreeMap<E,Object> map = (TreeMap<E, Object>) m; Comparator<?> cc = set.comparator(); Comparator<? super E> mc = map.comparator(); if (cc==mc || (cc != null && cc.equals(mc))) { map.addAllForTreeSet(set, PRESENT); return true; } } // 如果不满足条件，则使用父类的addAll方法进行添加 return super.addAll(c); } 嗯，这里会先激进优化，不行再用笨办法一个个添加，因为如果是将大量元素插入TreeMap中相对而言还是比较耗时耗力的，每次插入一个元素都可能导致整体结构的调整，而如果插入的元素刚好是有序的，那么就可以对这个过程进行一次很不错的优化。 public boolean remove(Object o) { return m.remove(o)==PRESENT; } public boolean contains(Object o) { return m.containsKey(o); } remove和contains方法也很简单。而且还带一点粗暴 到此，本篇就结束了，其实也没太多内容，因为TreeSet本身也没有太多东西。当然，了解它的内部结构目的是为了更好的使用它。在遇到问题时，每个知识点就是你手中的一张牌，能不能打好这手牌，先要看你这牌好不好，牌不好的话，再聪明也难翻盘。 . 真正重要的东西，用眼睛是看不见的。
2018-09-02
优秀的个人博客,低调大师

【Java入门提高篇】Day30 Java容器类详解（十二）TreeMap详解

今天来看看Map家族的另一名大将——TreeMap。前面已经介绍过Map家族的两名大将，分别是HashMap，LinkedHashMap。HashMap可以高效查找和存储元素，LinkedHashMap可以在高效查找的基础上对元素进行有序遍历，那么TreeMap又有什么特点呢？别急别急，看完这篇你就知道了。 本篇主要从以下几个方面对TreeMap进行介绍： 1、TreeMap的特性以及使用栗子 2、TreeMap继承结构简介 3、TreeMap源码分析 本篇预计食用10分钟，请各位食客合理分配时间。 一、TreeMap的特性以及使用栗子 1. 键值不允许重复2. 默认会对键进行排序，所以键必须实现Comparable接口或者使用外部比较器3. 查找、移除、添加操作的时间复杂度为log(n)4.底层使用的数据结构是红黑树 没错，又是让你欲仙欲死的红黑树，不过不要慌，跟之前介绍HashMap时的红黑树是一毛一样的，所以这一篇里，不打算再做介绍啦，如果对红黑树的内容有些遗忘了，可以动动小手，往前面翻一翻。 先来看一个TreeMap的使用小栗子。 public class TreeMapTest { public static void main(String[] args){ TreeMap<String, Integer> grades = new TreeMap<>(); grades.put("Frank", 100); grades.put("Alice", 95); grades.put("Mary", 90); grades.put("Bob", 85); grades.put("Jack", 90); System.out.println(grades); System.out.println(grades.subMap("Bob", "Jack")); System.out.println(grades.subMap("Bob", true, "Jack", true)); System.out.println(grades.ceilingEntry("Bob")); System.out.println(grades.ceilingKey("Bob")); System.out.println(grades.higherEntry("Bob")); System.out.println(grades.higherKey("Bob")); System.out.println(grades.headMap("Bob")); System.out.println(grades.headMap("Bob", true)); System.out.println(grades.tailMap("Bob")); System.out.println(grades.tailMap("Bob", true)); System.out.println(grades.containsKey("Bob")); System.out.println(grades.containsValue(90)); System.out.println(grades.descendingMap()); System.out.println(grades.descendingKeySet()); } } 输出如下： {Alice=95, Bob=85, Frank=100, Jack=90, Mary=90} {Bob=85, Frank=100} {Bob=85, Frank=100, Jack=90} Bob=85 Bob Frank=100 Frank {Alice=95} {Alice=95, Bob=85} {Bob=85, Frank=100, Jack=90, Mary=90} {Bob=85, Frank=100, Jack=90, Mary=90} true true {Mary=90, Jack=90, Frank=100, Bob=85, Alice=95} [Mary, Jack, Frank, Bob, Alice] 可以看到，放入TreeMap中的元素默认按键值升序排列，这里的键值类型为String，使用String的CompareTo方法进行比较和排序。subMap返回当前Map的子Map，headMap和tailMap也是如此， 二、TreeMap继承结构简介 TreeMap继承自AbstractMap，实现了NavigableMap接口，继承关系图如下： 对于AbstractMap相信大家已经不陌生了，HashMap也是继承自AbstractMap，里面有对Map接口的一些默认实现。这里我们可以看到两个新的接口——SortedMap和NavigableMap。SortedMap接口继承自Map接口，从名字就能看出。SortedMap相比Map接口，憎加了排序的功能，内部的方法也不多，简单了解一下就好了 NavigableMap接口继承自SortedMap接口，主要提供一下导航方法： 说了这么多没啥营养的，接下来还是讲讲真正的干货吧。 三、TreeMap源码分析 JDK 1.8中的TreeMap源码有两千多行，还是比较多的。所以本文并不打算逐句分析所有的源码，而是挑选几个常用的内部类和方法进行分析。这些方法实现的功能分别是查找、遍历、插入、删除等，其他的方法小伙伴们有兴趣可以自己分析。TreeMap实现的核心部分是关于红黑树的实现，其绝大部分的方法基本都是对底层红黑树增、删、查操作的一个封装。就像前面所说，只要弄懂了红黑树原理，TreeMap 就没什么秘密了。关于红黑树的原理，可以参考前面关于HashMap红黑树的文章，本篇文章不会对此展开讨论。 TreeMap的主要数据结构是红黑树，而这红黑树结构的承载者便是内部类Entry，先来看看这个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; /** * 构造函数*/ Entry(K key, V value, Entry<K,V> parent) { this.key = key; this.value = value; this.parent = parent; } public K getKey() { return key; } public V getValue() { return value; } 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; } } 其实内部的结构也很简单，主要有key，value和三个分别指向左孩子，右孩子，父节点的引用，以及用来标识颜色的color成员变量。再来看看TreeMap中的几个重要的成员变量： /** * 外部比较器 */ private final Comparator<? super K> comparator; private transient Entry<K,V> root; /** * 键值对数量 */ private transient int size = 0; private transient int modCount = 0; private static final boolean RED = false; private static final boolean BLACK = true; /** * 键值对集合 */ private transient EntrySet entrySet; /** * 键的集合 */ private transient KeySet<K> navigableKeySet; /** * 倒序Map */ private transient NavigableMap<K,V> descendingMap; comparator用于对map中的键进行排序，root指向红黑树的根节点，size表示键值对的数量，modCount相信已经不陌生了，表示内部结构被修改的次数，RED和BLACK是两个内部常量，即红黑两种颜色，false表示红，true表示黑。entrySet是键值对的集合，navigableKeySet是键的集合，最后一个descendingMap是当前map的一个倒序map。 在TreeMap中有很多内部类，可以先看图了解一下： 前前后后一共18个内部类，不过不要慌，其实里面跟迭代器相关的类就占了一半多（10个），跟子Map相关的类占4个，剩下4个就是跟内部集合相关的了。接下来还是一起来看看那些最常用的方法吧： // 插入元素 public V put(K key, V value) { TreeMap.Entry<K,V> t = root; if (t == null) { // 检查类型以及key是否为null // 如果外部比较器为null，且key也为null则会抛出空指针异常 // 如果TreeMap未设置外部比较器，且传入的对象未实现Comparable接口 // 则会抛出ClassCastException异常 compare(key, key); // type (and possibly null) check // 如果根节点不存在，则用传入的键值对信息生成一个根节点 root = new TreeMap.Entry<>(key, value, null); size = 1; modCount++; return null; } int cmp; TreeMap.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 // 找到相等的key则替换其value return t.setValue(value); // 一直循环，直到待比较的节点为null } while (t != null); } else { // 如果外部比较器为null // 如果key为null则抛出空指针 if (key == null) throw new NullPointerException(); // 如果key未实现comparable接口则会抛出异常 @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; do { // 跟上面逻辑类似，只是用key的compareTo方法进行比较，而不是用外部比较器的compare方法 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); } // 生成键值对 TreeMap.Entry<K,V> e = new TreeMap.Entry<>(key, value, parent); // 连接到当前map的左孩子位置或者右孩子位置 if (cmp < 0) parent.left = e; else parent.right = e; // 插入后的调整 fixAfterInsertion(e); size++; modCount++; return null; } 其实这里的逻辑跟HashMap中TreeNode的插入逻辑十分类似，也是先找到要插入的位置，然后再进行结构调整。这里的结构调整即红黑树的结构调整，在前面HashMap中已经详细介绍过了，这里就不重复介绍了，调整过程是完全一样的。 /** * 插入后的调整 */ private void fixAfterInsertion(TreeMap.Entry<K,V> x) { // 将插入的节点初始化为红色节点 x.color = RED; // 如果x不为null且x不是根节点，且x的父节点是红色，此时祖父节点一定为黑色 while (x != null && x != root && x.parent.color == RED) { // 如果x的父节点为祖父节点的左孩子 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { // y指向x的叔叔节点 TreeMap.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指向祖父节点，继续往上调整 x = parentOf(parentOf(x)); } else { // 如果叔叔节点是黑色节点 // 如果x是父节点的右孩子 if (x == rightOf(parentOf(x))) { // 将x指向其父节点 x = parentOf(x); // 左旋 rotateLeft(x); } // 将x的父节点置为黑色 setColor(parentOf(x), BLACK); // 将x的祖父节点置为红色 setColor(parentOf(parentOf(x)), RED); // 将祖父节点右旋 rotateRight(parentOf(parentOf(x))); } } else { // 这里类似操作 TreeMap.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; } 说完了插入，再来看看删除操作。 // 删除节点 public V remove(Object key) { // 先找到该key对应的键值对 TreeMap.Entry<K,V> p = getEntry(key); if (p == null) // 如果未找到则返回null return null; V oldValue = p.value; // 找到后删除该键值对 deleteEntry(p); return oldValue; } final TreeMap.Entry<K,V> getEntry(Object key) { // 为了性能，卸载了比较器的版本 if (comparator != null) return getEntryUsingComparator(key); if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; TreeMap.Entry<K,V> p = root; // 使用compareTo方法进行查找 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; } // 使用比较器的getEntry版本。 从getEntry分离以获得性能。 // （对于大多数方法而言，这不值得做，这些方法较少依赖于比较器性能，但在这里是值得的。） final TreeMap.Entry<K,V> getEntryUsingComparator(Object key) { @SuppressWarnings("unchecked") K k = (K) key; Comparator<? super K> cpr = comparator; // 使用比较器进行二分查找 if (cpr != null) { TreeMap.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; } /** * 删除节点，并调整红黑树以保持它的平衡 */ private void deleteEntry(TreeMap.Entry<K,V> p) { modCount++; size--; // 如果p的左右孩子均不为空，则找到p的后继节点，并且将p指向该后继节点 if (p.left != null && p.right != null) { TreeMap.Entry<K,V> s = successor(p); p.key = s.key; p.value = s.value; p = s; } // p has 2 children // 修复替补节点 // 用替补节点替换待删除的节点后，需要对其原来所在位置结构进行修复 TreeMap.Entry<K,V> replacement = (p.left != null ? p.left : p.right); if (replacement != null) { replacement.parent = p.parent; if (p.parent == null) root = replacement; else if (p == p.parent.left) p.parent.left = replacement; else p.parent.right = replacement; p.left = p.right = p.parent = null; // 如果p的颜色是黑色，则进行删除后的修复 if (p.color == BLACK) fixAfterDeletion(replacement); } else if (p.parent == null) { root = null; } else { if (p.color == BLACK) fixAfterDeletion(p); if (p.parent != null) { if (p == p.parent.left) p.parent.left = null; else if (p == p.parent.right) p.parent.right = null; p.parent = null; } } } /** * 返回指定节点的后继节点 */ static <K,V> TreeMap.Entry<K,V> successor(TreeMap.Entry<K,V> t) { if (t == null) return null; else if (t.right != null) { TreeMap.Entry<K,V> p = t.right; // 如果右子树不为空，则找到右子树的最左节点作为后继节点 while (p.left != null) p = p.left; return p; } else { TreeMap.Entry<K,V> p = t.parent; TreeMap.Entry<K,V> ch = t; // 如果右子树为空且当前节点为其父节点的左孩子，则直接返回 // 如果为其父节点的右孩子，则一直往上找，直到找到根节点或者当前节点为其父节点的左孩子时，用其做为后继节点 while (p != null && ch == p.right) { ch = p; p = p.parent; } return p; } } /** * 进行删除后的结构修复 * @param x */ private void fixAfterDeletion(TreeMap.Entry<K,V> x) { while (x != root && colorOf(x) == BLACK) { // 如果x是父节点的左孩子 if (x == leftOf(parentOf(x))) { // sib指向x的兄弟节点 TreeMap.Entry<K,V> sib = rightOf(parentOf(x)); // 如果sib是红色，则进行变色处理 if (colorOf(sib) == RED) { // 兄弟节点改为黑色 setColor(sib, BLACK); // 父节点改为红色 setColor(parentOf(x), RED); // 父节点左旋 rotateLeft(parentOf(x)); // sib指向x的父节点的右孩子 sib = rightOf(parentOf(x)); } // 如果sib的左孩子和右孩子都是黑色，则进行变色处理 if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { // 将sib置为红色 setColor(sib, RED); // x指向其父节点 x = parentOf(x); } else { // 如果sib的右孩子是黑色而左孩子是红色，则变色右旋 if (colorOf(rightOf(sib)) == BLACK) { setColor(leftOf(sib), BLACK); setColor(sib, RED); rotateRight(sib); sib = rightOf(parentOf(x)); } // 变色左旋 setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(rightOf(sib), BLACK); rotateLeft(parentOf(x)); x = root; } } else { // symmetric // 跟上面操作类似 TreeMap.Entry<K,V> sib = leftOf(parentOf(x)); if (colorOf(sib) == RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateRight(parentOf(x)); sib = leftOf(parentOf(x)); } if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { setColor(sib, RED); x = parentOf(x); } else { if (colorOf(leftOf(sib)) == BLACK) { setColor(rightOf(sib), BLACK); setColor(sib, RED); rotateLeft(sib); sib = leftOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(leftOf(sib), BLACK); rotateRight(parentOf(x)); x = root; } } } setColor(x, BLACK); } 嗯，对比一下HashMap的删除操作，核心步骤是完全一样的，所以可以对照前面的HashMap红黑树详解进行食用。 到此，这一篇就很水的讲完啦= = 最近这段时间烦心事比较多，对发展方向也考虑了很多，想做的事情很多，反而让我止步不前，不过很多事情是急不来的，还是好好写写博客，多做总结分享吧。 机会只留给有准备的人。 真正重要的东西，用眼睛是看不见的。
2018-08-28

资源下载

更多资源
优质分享App

优质分享App

近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

时间: 2025-12-03 大小: 4.36MB 下载: 23次
腾讯云软件源

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

时间: 2026-01-27 大小: 1MB 下载: 5次
Spring

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

时间: 2025-12-17 大小: 5MB 下载: 1次
Rocky Linux

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。

时间: 2026-01-03 大小: 1.42GB 下载: 2次
热门标签
SpringCloud Rocky Gemini3 Docker Service Mesh Nacos3 OpenAi Redis HarmonyOS6 DeepSeek Jdk25 Kubernetes SpringBoot4

欢迎您来访！

登录后，您将获得更多功能！
热门文章
联系我们

有任何问题或合作意向欢迎联系我们

Email: 99873273@qq.com

QQ: 99873273

用户登录
用户注册