Luyseon Blog

红黑树R-B Tree，全称Red-Black Tree，又称红黑树，一种特殊的二叉平衡树。它通过引入颜色标记和一系列约束规则，保证了树的插入、删除等操作后的平衡性，从而使得查找、插入、删除的时间复杂度均保持在O(log n)范围内。 1.前提知识在了解红黑树之前，我们先得了解BST二叉查找树和AVL平衡二叉树的一些基本概念。 1.1.BST二叉查找树什么是二叉查找树 二叉查找树(BST) 又叫二叉搜索树，它满足以下性质： 若任意节点的左子树不为空，则左子树上所有的节点的值均小于它的根节点的值。 若任意节点的右子树不为空，则右子树上所有的节点的值均大于它的根节点的值。 任意节点的左、右子树也分别为二查找树。 二叉查找树的查找流程 在二叉查找树b中查找x的过程为： 1.若b是空树，则查找失败，否则： 2.若x等于b的根节点的数据域之值，则查找成功；否则： 3.若x小于b的根节点的数据域之值，则查找左子树；否则： 4.查找右子树。 示例代码 123456789101112131415Status SearchBST(BiTree T, KeyType key, BiTree...

HashMap源码解析 HashMap是Java集合框架中非常重要的一个类，它基于哈希表实现，提供了快速的键值对存储和查找功能。HashMap实现了Map接口，允许放入key为null的元素，也允许插入value为null的元素。（本篇文章主要以Java 8 为例） 1.HashMap的基本结构HashMap内部使用数组 + 链表/红黑树的结构存储数据。 数组：Node<K,V>[] table是一个数组，每个位置称为一个桶(bucket)，用于存储键值对。 链表：当多个键值对的哈希值映射到同一个桶时(即同一个下标)，这些键值对会以链表的形式存储。 红黑树：如果链表长度超过一定阈值(默认为8)，且数组长度大于等于64，则链表会转换为红黑树。（Java 8 开始） 2.核心属性一下是HashMap中的一些重要的成员变量： 1234567891011121314151617181920212223242526272829303132//默认初始容量（必须是2的幂），默认16static final int DEFAULT_INITIAL_CAPACITY...

ArrayList源码解析1.概述ArrayList是 Java 集合框架中基于动态数组实现的顺序容器，允许放入null元素，底层通过数组实现，非线性安全。 特性： 元素有序且可重复。 支持随机访问。 动态扩容机制。 每个ArrayList都有一个容量，表示底层数组的实际大小，容器内存储元素的个数不能多余当前容量。当向容器内添加元素时，如果容量不足，容器会自动进行扩容，每次扩容大约为原来的1.5倍。 继承体系 ArrayList实现了List<E>,RandomAccess, Cloneable, java.io.Serializable这些接口。 List<E>：提供了基础的添加、删除、遍历等操作，并且可以通过下标进行访问。 RandomAccess：提供了随机访问的能力。 Cloneable：表示它具有拷贝能力。 Serializable：表示可以被序列化，也就是可以将对象转换为字节流进行持久化存储或网路传输。 2.源码解析2.1.属性123456789101112131415161718192021222324/** *...

JVM体系结构JVM（Java Virtual Machine，Java虚拟机 ）是一种抽象的计算机，它能够运行Java编译后生成的字节码文件（.class后缀的文件）。JVM充当了一个翻译官的角色，将开发者编写的Java代码转换为底层操作系统能够理解的指令。最为核心的特性是“一次编写，到处运行”，即通过JVM，Java程序可以在任何支持JVM的平台上运行，而无需修改代码。 如图所示，可以知道JVM主要由四个部分组成： 类加载子系统（ClassLoader） 运行时数据区 （Runtime Data Area） 执行引擎 （Execution Engine） 本地库接口 （Native Method Library） 1.类加载子系统1.1.类的生命周期类加载过程包括了加载、验证、准备、解析、初始化五个阶段。其中，验证、准备 和 解析...

延迟队列在我们的日常生活中很常见，比如超时取消订单功能，优惠卷过期，消息延时推送等功能。RabbitMQ是一个广泛的消息队列中间件，它支持延迟队列的功能，我们可以通过设置消息的TTL (过期时间) ...

线程创建的几种方式1.继承Thread类最为简单直接的方式，直接通过继承Thread类，并重写run()方法。 步骤： 创建一个类继承Thread。 重写 run() 方法，将线程要执行的的代码写在run方法中。 创建线程对象，通过start()方法启动线程。 示例： 12345678910111213public class MyThread extends Thread{ @Override public void run() { System.out.println("Thread is running"); }}public class Main { public static void main(String[] args) { MyThread myThread = new MyThread(); myThread.start(); ...

1. 什么是布隆过滤器以下定义来至百度百科： 布隆过滤器（英语：Bloom Filter）是1970年由伯顿·霍华德·布隆（Burton Howard Bloom）提出的。它实际上是由一个很长的二进制向量和一系列随机映射函数组成的。布隆过滤器可以用于检索一个元素是否在一个集合中。 它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。 由此我们可知布隆过滤器主要由两个部分组成：位数组和多个映射函数（哈希函数）。 位数组：初始化为一组固定长度的二进制位（默认全为 0）。 哈希函数：使用多个独立的哈希函数（如 k 个），对输入元素进行哈希处理，生成 k 个哈希值。 Bloom Filter 使用一个较大的bit数组进行保存所有的数据，数组中的每个元素都只占用1 bit，并且每个元素只能是 0 或者 1，这也是布隆过滤器节省内存的核心所在。我们设想1000w个元素，它只需要 1000000Bit / 8 = 125000 Byte = 125000 / 1024 KB ≈ 122 KB...

Redis 是一个开源的的内存数据结构存储系统，常用作数据库、缓存和消息代理。它支持多种数据结构，如字符串、哈希、列表、集合等，具备高性能和灵活性。 常见使用场景1. 缓存将热点数据存放在内存中，作为缓存对象以加速数据的读取，减轻数据库的负担。这种方法可以显著提高应用的响应速度，尤其是在频繁访问的数据场景中。 常见缓存策略： LRU（Least Recently Used）：淘汰最少使用的缓存数据。 TTL（Time To Live）：设置缓存数据的有效时间，过期后自动删除。 2. 会话缓存可以使用 Redis 来统一存储多台应用服务器的会话信息。通过将会话信息存储在 Redis 中，当应用服务器不再存储用户的会话信息时，系统变得无状态。这意味着用户可以请求任意一台应用服务器，这样更容易实现高可用性和可伸缩性。 Redis会话缓存 的优势： 持久化：Redis 提供数据持久化机制（把内存中的数据写到磁盘中去），可以在服务器重启后恢复会话数据。 高并发：Redis...