NoSQL 的抽象数据库系统的核心作用在于高效地存储和管理数据，并支持从海量信息中快速检索所需记录。传统的 SQL 关系型数据库在数据规模持续增长的情况下，容易遭遇单机性能瓶颈。目前提升性能的主流做法多依赖垂直扩展增强单机硬件能力，而非水平扩展增加节点以线性扩容。由于其架构限制，关系型数据库在弹性扩展性方面存在障碍，难以充分适应多节点分布式环境。同时为满足 ACID 事务特性，这类系统在支持分布式事务处理时也面临一定的技术挑战。相比之下，NoSQL 数据库更适用于大规模数据存储和高吞吐、低延迟的应用场景。由于 NoSQL 不受固定数据结构和关系的限制，具有更灵活的扩展能力，并且支持节点的动态扩展，从而更好地适应分布式环境。无论是关系型 SQL 数据库还是 NoSQL 数据库，它们都有一个共同的核心组件存储引擎，这是数据库设计与实现的关键核心部分。目前数据库存储引擎可以分为两大类，一类是基于内存的 （In-Memory）实现，例如 Redis 和 Memcached 这类的将数据全部存储在内存中；另外一种则是类似于 MySQL 的 InnoDB 和 LevelDB 这种将数据存储在磁盘中。两者都有各自的优势和劣势，基于内存的存储引擎通常存储的数据量较少，但其访问速度往往比基于磁盘的存储引擎快好几个数量级，而基于磁盘的存储引擎访问速度较慢，但存储数据量要比内存引擎多几个数量级。通常内存的价格要比磁盘的贵很多，这也是在选择存储硬件时要考虑的成本问题。存储引擎的开发者需要权衡读写性能和硬件成本的同时，重点在于如何高效存储数据和检索数据。数据库的存储引擎相当于在操作系统文件系统之上，建立的一套用于数据组织、存储与查询的逻辑管理层，最终实现是依赖于操作系统的文件系统 API 接口的，最终数据是被持久化到磁盘文件中保存，这个就对应着 ACID 中的 Durability 数据持久性。持久性（Durability）是存储引擎最为至关重要的功能实现，目前很多基于内存版本的 NoSQL 数据库例如 Memcached 和 Redis 在这方面做的就比较差，在 NoSQL 服务器运行过程中突然崩溃断电就会导致数据没有被持久化存储的情况，从而导致数据丢失影响到上层的业务程序。[scode type="yellow"]所谓的持久性就是如何将计算机运算的结果持久化存储在一些物理介质中；持久性是指系统能够将状态变更的结果可靠保存，使其在系统重启或故障后仍然能够恢复。[/scode]存储是现代计算机最核心的功能之一，计算机中的程序和文件以数据块的形式保存在各种存储介质中，主要可分为持久化存储和非持久化存储两类。非持久化存储通常指内存（如 RAM），其特点是在断电或关机后，数据会被清除。尽管容量通常小于持久化存储，但其高速读写性能使其广泛应用于程序运行过程中的数据处理和临时缓存。相比之下，持久化存储如硬盘、固态硬盘、DVD、磁带等，能够在断电后保留数据，适用于长期保存程序和文件信息。鉴于数据可能存储在多种物理介质（如磁盘、SSD、光盘等）上，主流的操作系统需要提供一致的抽象接口，以屏蔽底层硬件差异，使用户能够高效、统一地进行文件的读写、创建与删除等操作。当前主流操作系统均实现了完整的文件系统，开发者可以通过如 POSIX 这样的标准 API 接口来访问和管理存储设备，而无需关心具体设备的物理实现方式。尽管操作系统的文件子系统通过标准如 POSIX 提供了对存储设备的访问能力但仍存在一些限制；例如存储性能受限于设备的物理读写速度，同时文件系统通常采用页缓存 Page Cache 或写缓冲机制，这意味着数据写入操作并不会立即持久化到磁盘，一旦系统发生故障或意外断电，可能会导致数据丢失，影响系统的可靠性。基础架构综上所述，针对这些场景的问题 UrnaDB 采用了基于 Log-Structured Megre Tree 日志结构化文件系统的存储引擎实现，存储引擎会以 Append-Only Log 的方式将所有的数据操作写入到数据文件中。同时 UrnaDB 为了高速查询检索数据记录，存储引擎会将数据记录索引信息全部保存在内存中，从而实现高效快速的查询目标数据记录。这样的设计的好处是能以磁盘最大写入性能进行写入数据，并且还能减少读取磁盘索引所需要的时间，通过一次索引定位来读取数据记录，写入和查询流程图：其核心持久化机制基于预写日志 Write-Ahead Logging 简称 WAL ，在对数据执行任何操作前，都会先将操作记录写入 WAL 日志文件。WAL 文件不仅承担持久化的角色，也作为主要的数据存储载体。在数据库进程崩溃后，只需从 WAL 日志中顺序读取各条 Segment 记录，即可高效恢复内存中的索引结构。在 UrnaDB 中对这些 WAL 数据文件有一个统称为叫 Region 文件，这些文件有单个固定大小限制，当一个数据文件写满之后就会被关闭，会重新创建一个新的 Active 活跃的 Region 文件进行数据记录的进行写入。被关闭的 Region 文件会被视为冷数据文件，随着数据库不间断长时间运行 Region 文件会不断递增逐渐占用磁盘空间。此时数据库进程就需要对旧的 Region 文件执行压缩 Compaction 和定期清理，以降低存储压力并提高查崩溃数据恢复时的启动效率，压缩流程原理图：目前工业级的存储系统中，RaikDB 是一个采用类似模型实现的数据库产品，RaikDB 是基于 Amazon Dynamo 论文的设计理念构建而成。其 RaikDB 底层也是采用的顺序写入的日志式存储引擎，并将其命名为 Bitcask 存储模型，以提升写入性能和读写效率。该模型与 UrnaDB 所采用的存储引擎在设计理念上颇为相似。Bitcask 存储引擎在执行数据压缩 Compaction 时会生成 Hint 文件，其作用是在存储引擎重启时，辅助快速重建内存索引，从而避免每次启动都需全量扫描数据文件，显著提升系统的启动效率。然而 Hint 文件仅在 Compaction 过程中生成，所记录的只是当时内存索引的快照，无法反映实时状态。针对这一问题 UrnaDB 在存储引擎中进行了改进，将 Hint 文件机制替换为 Checkpoint 功能，系统会在固定时间间隔内，定期将当前内存索引持久化为 checkpoint 文件写入磁盘。当服务器进程发生异常崩溃，也可通过读取 checkpoint 快照快速恢复内存索引状态。在实际恢复流程中，UrnaDB 会优先加载最近一次的 checkpoint 快照，并从该时间点之后的 Region 文件中继续回放增量数据。通过这种方式，有效提升了系统启动恢复的速度，减少了启动耗时，同时兼顾了数据一致性与运行效率。在该存储引擎设计的基础上，UrnaDB 构建了内置的 HTTP 服务器，并引入了多种抽象化的数据结构层。整体架构如下图所示：系统采用模块化设计，各模块以包结构组织并协同工作，覆盖底层存储、核心逻辑与服务接口，构成一个完整的单机版 NoSQL 数据库，实现了分层解耦与一体化集成。检查点技术由于 UrnaDB 数据库存储引擎采用将所有索引数据存储在内存中的设计，一旦数据库进程意外崩溃，内存中的索引信息将会丢失，未能持久化到磁盘。这样在下一次启动时，系统需要重新扫描所有数据文件，以重建内存中的索引结构，如果数据文件体量较大，将导致启动过程变得缓慢，启动耗时较长。Checkpoint 功能机制会通过定期将内存中的索引状态保存到磁盘，在发生异常重启时即可快速加载 checkpoint 文件，从而大幅缩短数据库的启动时间。开启 checkpoint 功能可以在数据库崩溃后显著加快启动恢复的速度。然而 checkpoint 文件的生成时间间隔设置同样需要谨慎权衡。如果生成间隔过短，将导致 checkpoint 文件过于频繁地写入磁盘，占用大量 I/O 资源，可能影响数据库的整体性能；而如果间隔设置过长，崩溃恢复时仍需扫描大量 Region 数据记录，反而无法发挥 checkpoint 的优势，导致启动时间较长。因此合理配置 checkpoint 的生成频率，需在性能开销与数据恢复效率之间做出平衡，建议根据实际业务的数据写入频率和系统负载，动态调整该参数以获得最佳效果。磁盘垃圾回收器由于 UrnaDB 存储引擎采用顺序日志写入结构，随着系统运行时间的增长，每个 Region 区域对应的磁盘数据文件会不断增大。默认情况下 Region 文件中的每条数据记录未经过压缩，导致磁盘空间占用随数据量增加而持续上升。为了解决这一问题 UrnaDB 存储引擎内置了数据压缩算法，启用该压缩器功能后，可以显著减少磁盘文件的存储体积，从而有效降低存储成本。在配置 Region 区域的垃圾回收功能时，需要综合考虑多种因素。若不启用该功能，随着系统长时间运行，磁盘空间占用将持续增长，甚至可能过高，影响系统稳定性。若启用垃圾回收，则必须合理设定其执行周期：周期过长：会导致空间回收不及时，磁盘占用上升，同时在压缩 Region 时耗时较长。周期过短：会导致垃圾回收过于频繁，增加系统资源开销，进而影响存储引擎的整体性能。在 UrnaDB 中垃圾回收器的执行周期同样依赖于 Time 触发，并且其执行过程会占用一定的系统资源。如果采用并行执行机制，这段时间对外部应用基本无感，系统可持续对外提供服务。这种设计理念与许多现代编程语言的垃圾回收器类似，UrnaDB 的 Region 区域划分为 Active Region 和 Read Region 区，其架构与 Java 虚拟机（JVM）中的垃圾回收机制具有相似性。当垃圾回收开始运行时，它不会对 Active Region 中的活跃数据进行操作，而是仅针对旧的 Read Region 区域执行垃圾分析与清理，从而避免对当前读写路径造成干扰，不会出现类似于编程语言虚拟机中的 Stop-The-World 世界时钟停止问题 （这里指明一点 JVM 即使分代进行垃圾回收，因为存在循环引用问题，还是会出现两个区域的对象相互关联），减少压缩磁盘空间的抖动，保障数据库稳定性。时间就是一个问题在整个 NoSQL 数据库的设计过程中，许多复杂问题的根源其实都与物理世界中的 Time 有关。当前的 UrnaDB 实现为单机版本，因此主要面临的是本地磁盘 I/O 和线程调度带来的延迟问题。然而一旦在未来引入多个存储节点，发展为分布式架构，就必须应对网络延迟、时钟同步、事务一致性等与时间密切相关的挑战。因此无论是当前的 NoSQL 单机实现，还是面向未来的分布式扩展，如何合理建模和管理时间 Time 维度，始终是数据库架构设计中的核心研究问题之一。在单机版本中还面临另一个挑战如何为数据记录提供过期时间（Time-To-Live）支持，尽管 TTL 是常见的需求，但其实现往往较为复杂，目前主流 NoSQL 数据库普遍采用惰性删除机制，即仅在数据被访问时才判断其是否过期并删除，这种方式依赖于外部读取请求的触发，可能导致过期数据长期滞留在存储中。数据文件采用 WAL（Write-Ahead Logging）机制实现持久化，但 WAL 本身仍需通过操作系统文件系统 API 写入磁盘。现代操作系统通常基于 Page Cache 和写缓冲进行 I/O 加速，因此普通的 write 操作并不会立即落盘，而是先进入内核缓存，若在此期间发生掉电，仍可能丢失尚未刷新的数据。UrnaDB 运行在用户态无法从根本上绕过操作系统的 Page Cache 机制，只能通过 fsync/O_DSYNC 等接口请求内核将数据强制写入物理持久介质中。在通过一些代码测试中不同持久化策略下写入性能存在很大差异性，差异对比表格：写入模式性能 (ops/sec)性能下降数据安全性刷盘依赖普通写入~100,000基准依赖 OS 缓存OS 自动定期sync~50,00050%中等应用控制O_DSYNC~1,00099%最高每次写入mmap~100,000基准依赖 OS 缓存OS 自动mmap+msync~1,00099%最高应用控制所以无论是 write() 还是 mmap 内存文件映射，只要不主动调用同步操作sync/msync 都是依赖 OS 的页面缓存刷盘策略。对于 UrnaDB 用户而言，更推荐的优化方式是从操作系统层面调整相关参数，这才是更为根本和可靠的解决方案。通过调整 Page Cache 的刷写策略，可降低数据在内核缓存中滞留的时间，从而减少断电或崩溃场景下的数据丢失风险，以下为关键的操作系统可调优的参数示例：# 减少脏页比例，更频繁地触发后台刷盘 echo 5 > /proc/sys/vm/dirty_background_ratio # 默认10%，改为5% echo 10 > /proc/sys/vm/dirty_ratio # 默认20%，改为10% # 缩短脏页存活时间 echo 500 > /proc/sys/vm/dirty_expire_centisecs # 默认3000(30秒)，改为5秒 echo 100 > /proc/sys/vm/dirty_writeback_centisecs # 默认500(5秒)，改为1秒[scode type="yellow"]通过调整 Linux Page Cache 相关参数，可缩短脏页滞留时间并提升后台刷写频率，从而减小 WAL 数据因掉电而丢失的时间窗口。核心思路是：降低触发阈值、加快刷写节奏，使数据尽可能提前落盘，在断电时能使用备用电源和其他机制来完成数据持久化。[/scode]在 UrnaDB 的运行过程中，如果发生异常宕机，可能会导致部分数据处于未完成写入的状态，从而出现数据记录的不一致性。在某些极端情况下会出现检查点和索引文件同时损毁情况，在这种情况下如果从这些半损毁文件中恢复数据，可能导致记录不一致甚至造成二次损坏。索引文件和检查点文件损毁的原因较为多样，其中一种典型场景出现在 Docker 容器化部署 UrnaDB 时，Docker 在正常关闭容器时会启用默认的超时机制，当 UrnaDB 的内存索引规模较大、持久化耗时较长时，进程可能无法在超时时间内完成数据落盘。此时 Docker 会强制终止容器，导致内存中的索引与检查点数据未能完整写入磁盘，进而引发文件损毁或数据不一致。[scode type="green"]出现元文件损毁的情况下，更安全可靠的恢复流程是使用 UrnaDB 所提供的 fix-dbfs 工具在启动之前对数据目录中文件进行损坏数据整理，经过 fix-dbfs 修复后的数据文件才被视为安全且一致的有效数据文件，再让 UrnaDB 正常加载启动即可恢复宕机之前的数据状态。[/scode]如何合理权衡 Checkpoint 的执行频率与垃圾回收的触发时机，是 UrnaDB 数据库系统优化中的关键问题。若在数据高频读写期间执行垃圾回收（如磁盘空间压缩），可能引入短暂的读写延迟；同时在数据迁移与压缩过程中，存储引擎还可能导致磁盘空间的临时占用上升，从而影响整体性能与资源利用率。为此 UrnaDB 在未来版本中将引入一种主动回收机制：结合运行时监控指标与 Unix 的 Signal 机制，通过 kill 命令向 UrnaDB 进程发送信号，实时唤醒后台垃圾回收线程执行过期数据清理任务。该方案能够更精准地控制存储空间占用，提升系统的可预测性与运行稳定性。
哈希函数 估计是一个程序员都知道这个概念，可以将一串数据变成一串特定的散列值，如果看过我之前的一致性哈希那篇文章应该会很清楚工作原理。这篇文章将讲解如何去设计一个工业级的哈希表，哈希表本身概念和工作原理没有什么难的，主要还是存储方式选择和负载因子带来的扩容和哈希冲突问题。哈希表属于数据结构的范围了，日常开发过程中经常会使用到哈希表例如Java的HashMap、Go内置的map，这些都是哈希表，还有知名的缓存中间件例如Redis也是采用哈希的方式数据分区，也可以看成是一个超大的哈希表，大部分都在使用，而设计一个工业级哈希表要考虑的因素有很多：存储方式、负载因子、缩容和扩容问题等。存储方式哈希表是一种映射数据结构key-value，这种形式的存储，键可以是任何数据只要经过hash function就能得到一串哈希序列值。而值的存储方式有很2种：开放式存储，链表式存储，两种方式都用来存储值数据的，区别就是存储方式和取值方式不同罢了。开放式寻址： 上来我们可以申请一块大的连续内存空间，数组就可以满足，然后把经过哈希计算的值放到对应的数组下标位置上，但是问题就是哈希函数可能不同的键算出来的值有可能相同发送哈希冲突了，这时怎么解决位置被占用的就是一个问题？开放寻址工作原理如上图，如果发生了位置占用就往下一个下标位置找，看看是不是为空的，如果是空的那么就存储，循环这个过程。删除操作是不直接删除数据的，而是直接标记存储位置的下标，假性删除。但是这种也会有扩容带来的问题，删除的数据越多那么被标记的位置越多而且还是一样占用内存，所以不能再删除和插入一起操作，如果直接删除了位置上的内容，下次插入值时被存储到这个位置可能会发生数据错乱的现象。链式存储： 链式存储是最简单的方式了，数据结构存储头节点是指向一个根数组的，然后如果发生了数据冲突那么的，数据会以链表的方式对接下去，这样的好处就是数据槽位固定的，但是数据元素可以在每个槽位上以链表的方式存储下去，动态分配存储，这个最常用的没有什么好说的原理图我也不画了。负载因子负载因子针对的是链式存储的方式，上面我讲过链式存储解决哈希冲突的问题是把数据分槽位，然后在对应的槽位上以链表的方式存储数据。但是这样的话如果数据越来越多，每个链表上的数据也很越来越多导致本来查询很快的时间复杂度变成了O(n)，怎么解决这样的问题，那就是要对数据较多的时候进行扩容操作，扩容操作就是针对分区槽位的扩容，把数据能确保分摊到所有的槽位上，那触发槽位扩容条件是什么？需要扩容条件，那就要确定存储空间在什么条件下才能发生扩容操作，看了上面图，很容易看出来我们哈希函数是针对的槽位数，在哈希确定到槽位编号了之后，然后就是把数据放到链表上存储，和槽位上其他节点对接上。熟悉链表的朋友应该知道链表查找是要从头开始扫描查找数据的，所以时间复杂度为O(n)，所以链表上的数据不能太多，为了解决这个不能多的办法就是对槽的个数发生更新。数据少的时候可能默认几个槽位就可以够用了，但是如果数据多了动态添加和删除数据多了，那么就要扩容了，扩容条件按照上面的推理完全可以推导出来那就是把目前哈希表所有存储的数据对槽位取平摊值，这个值就是每个槽位上的负载因子，公式我已经在图上画出来了，当负载因子越大的时候可能每个槽位上的链表数据就越多，查询性能也会有影响，越小就越快，所以在设计一个哈希表时负载因子很重要，使用的时候，可以在预估需要处理的数量积，先计算出负载因子然后初始化一个哈希表，这样就能满足需求。扩容问题解决了什么时候发生扩容的问题之后，另外一个问题就是怎么迁移数据到新的存储地址上，当数据太多时候，一般的扩容策略都在分配一个原始大小1.25的存储空间或者原始存储大小的两倍空间来存储老的数据和新的数据。但是问题来了，如果老的哈希表里面有很多数据一次性迁移会带来很大问题，例如迁移的过程中哈希表还在并发操作的，并且有可能还有数据在写入，怎么保证数据一次性迁移呢？并且在扩容之后我们的哈希函数也要跟着更新的，原来的槽位数和新的扩容之后的槽位数是不一致的，所以老的哈希函数是不能正常访问到新的数据，这也是一个问题？很多时候一次性迁移数据会发生性能损耗，哈希槽位上的链表数据越多那么迁移的数据就越多，这个就会带来性能问题。我看过一些比较好的迁移策略就是间接性迁移，也可以理解为被动迁移，那是怎么工作的呢？针对上面的两个扩容的问题，哈希函数我们可以保留两个哈希函数，当有新的数据来的时候我们使用新的哈希函数计算存储到新的空间里面，如果有请求来查询我们可以先把老哈希函数计算一遍看看有没有数据，如果老哈希函数在老的地址里面没有找到新的数据，就用的新的哈希函数查找，每次有新的数据插入时就触发一次老的数据迁移，直到老的数据全部被迁移完成，销毁老的存储空间即可，在数据没有迁移完成之前可能内存消耗比较大，但是能使用空间换取时间和性能。所以哈希扩容和迁移要注意的问题就是性能问题，渐进式迁移，每次一小部分发送迁移，不要一次性全部迁移，有新的数据请求如果在老的存储空间内没有命中，就直接存储到新的空间里面，这个设计就非常巧妙的解决问题。注意项开放寻址： 如果是通过数组分配存储空间可以享受CPU缓存机制因为数组空间是连续存储空间，可以把数据序列化存储，不涉及反序列化之后的指针地址不一致问题。开放寻址法的负载因子不能过大，如果过大那么每个数据空间存储的数据发生冲突概率加大影响性能，会发生命中位置被占用而重新寻址情况。链式存储： 链式存储的好处就是每次存储的时候需要找到尾指针，在分配空间存储时需要额外的指针存储空间，存储空间不需要一次性分配连续的，不能发挥CPU缓存机制，其次负载因子可以大一点，解决数据冲突或者哈希冲突可以使用红黑树。例如Java默认负载因子是0.75，当存储数据每个槽位元素个数超过8个机会使用红黑树存储，而小于6的时候默认链表存储，这种多模式存储策略可以根据数据大小进行调整，还换取性能。小结设计一个工业级哈希表，并非难事，要分析哈希表解决了什么样的问题?然后针对每个问题一一击破，这就是系统设计的美学，我看过Go语言的map设计非常巧妙，有兴趣的朋友在看到我这篇博客时可以去读读Go的map设计相关的文章。一些关于散列算法的应用有：MD5、SHA等...数据加密领域、区块链领域、服务负载均衡集群、路由分发、数据分片分布式存储、分布式系统里面的一致性哈希算法，这些全部是散列算法延伸出来的。
二进制的 0 和 1人类我们常用的数据表示方法是十进制，而计算机却是二进制，在计算机的设备里面所有的数据都是使用二进制表示的。显示器显示的数据是人类能理解的数据，这是为了更好的和人类交互这样的设计的，当在键盘上输入一个内容的时候，这些在计算机内部处理完全是二进制的，计算机只认识 0 和 1 ，也是二进制位。计算机最基础的计量单位是 bit ，也就是 8 个比特位等于一个 byte 字节，后面的计量单位在当前计量基础做 10^2 计算，相关的存储单位可以去看看相关资料，这篇 blog 我就不会详细的介绍这些计量单位。用比特位存储表示详细的话，如果把8个比特位填满那么可以表示为 255 ，如果 8 比特位都是0的话那么就是 0 。如果某些时候在追求计算性能和存储空间利用率的时候，可以使用位运算，如果需要表示的信息状态只要两种的话可以使用位图来表示，这样空间利用率会更好，本文就介绍一下关于位运算的基础和位图。说一句话就是：与二一是 1 ，或二零是 0 ，异或相同为 0 ，相异为 1 ，取反就是反。计算两个数的和，因为在计算机中都是以二进制来进行运算，所以下面所给的 int 变量会在机器内部先转换为二进制在进行相加，例如下图动图：在我们人类世界里是逢十进一，在计算机的二进制里面逢二进一，计算过程： 183: 1 0 1 1 0 1 1 1 + 19: 0 0 1 0 0 0 1 1 —————————————————————————— 202: 1 1 0 0 1 0 1 0在计算机运算里面，加减乘除都是通过加法实现的，这部分内容比较深奥，涉及一些知识，读者可以下面这个视频：李永乐二进制进制运算位图实现位图就是利用的比特位作为基础的一种数据结构的应用，可以使用少量的内存占用表示更多数据信息，例如我在 Go 语言里面使用了 int16 作为基础存储空间，这样 int16 是由 2 个 byte 组成的，可以表示 512 状态信息。位图就是使用这一特性来解决的问题状态信息表示的问题，例如下面实现代码：package bitmap type Bits struct { bytes []int16 nbits int } //把需要表示数量除以16得到需要分配的int16个数 func New(nbits int) Bits { return Bits{ nbits: nbits, bytes: make([]int16, nbits/16+1), } } // 通过下标对16取商得到具体那块内存 // 然后对其内存的bit位进行设置 func (m *Bits) Set(index int) { if index > m.nbits { return } byteIndex := index / 16 bitIndex := index % 16 m.bytes[byteIndex] |= (1 << bitIndex) } func (m *Bits) Peek(index int) bool { if index > m.nbits { return false } byteIndex := index / 16 bitIndex := index % 16 return (m.bytes[byteIndex] & (1 << bitIndex)) != 0 }
Go泛型也出来很久了，最近也用泛型去实现一些功能，例如数据结构一些应用还是没有什么问题的。但是如果做一些类型上限制，还是有点问题，和其他语言有一些不一样的地方，想要基于泛型做一些类型上的限制，必须使用组合的模式，或者嵌套。这篇我将记录一下我在Go泛型上遇到一些问题。阅读这篇文章读者需要了解Go泛型怎么使用和泛型能做什么，还有了解map结构原理，并且本文会以LinkedHashMap作为一个泛型结构讲解一些关于Go泛型不完美的地方。读者要知道LinkedHashMap底层是怎么工作的才能读懂这篇文章。原生Map局限性大家都知道Go的内置map结构在遍历的时候是无序的，如果要让其有序输出那么就要对key进行排序，然后收集排序完的key依次索引输出这样子，但是很麻烦的样子，并且还不能保证map存储的的顺序不是以插入值的顺序而存储，并且还不能按照访问操作顺序重排底层存储结构元素的关系，了解的原生map应该知道底层是通过hash function打乱并且存储在不同桶里，遍历只能从不同的桶里随机输出这些元素，这就是无序的原因。LinkedHashMap使用过Java朋友应该知道一个数据结构叫LinkedHashMap，这个数据结构是可以保证数据存储顺序的，并且还能按照配置动态调整存储的元素的顺序关系，下面这是一段Java代码，介绍一下工作原理：LinkedHashMap<String, Integer> lmap = new LinkedHashMap<String, Integer>(); lmap.put("语文", 1); lmap.put("数学", 2); lmap.put("英语", 3); lmap.put("历史", 4); lmap.put("政治", 5); lmap.put("地理", 6); lmap.put("生物", 7); lmap.put("化学", 8); for(Entry<String, Integer> entry : lmap.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); }输出结果可以看到：语文: 1 数学: 2 英语: 3 历史: 4 政治: 5 地理: 6 生物: 7 化学: 8可以看到是以我们插入时候的顺序输出的结果，可以做到有序的。这是怎么做到的呢？如果深入底层源代码分析发现，他内部结构入下图：和HashMap的运行结果不同，LinkedHashMap的迭代输出的结果保持了插入顺序，它底层其实就是一个map加Linked List组成一个结构，map负责索引，而Linked List负责的是数据顺序组织存储方式，可以形成一个完全有序的链表，大部分可能认为就是一个链式存储方式，这是不对的，有兴趣可以源代码，是两种数据结构组合而成，类似于LRU淘汰算法那样，每次操作元素都会发生底层数据交换位置。元素是被内置的map索引着的只是为了方便快速拿取，而为了数据能和插入时一致的顺序又用链表组织成了有序链表，原理可以想象上面这幅图，你洗衣服拿衣服怎么洗的？如果读者看到这里看不懂话，可以去网上看看关于LinkedHashMap底层实现的代码分析文章吧，我这里不讲解了。用Go泛型实现对其工作原理介绍完了，下面我就针对这个这种方式，使用Go去实现类似的，算是重复造轮子吧。但是在泛型key上还是遇到一些问题，顺便写一个文章记录。下面这是我使用Go复刻的LinkedHashMap代码，Node[K Hashed, V any]结构是为了底层数据存储所设计的，而LinkedHashMap为主体结构，注意里面的table map[uint64]*Node[K, V]字段。type Node[K Hashed, V any] struct { Prev, Next *Node[K, V] Key K Value V } // Stored structure type LinkedHashMap[K Hashed, V any] struct { accessOrder bool // the iteration ordering method capacity int // total capacity head, tail *Node[K, V] // linked list table map[uint64]*Node[K, V] // data storeage size int // current size }为了这个map能达到和Java的LinkedHashMap一样的效果，我在key泛型上做了限制，因为要支持双泛型参数声明，有两个泛型参数，如果简单一个话，这个键完全可以设置为string类型，那这样的后果就调用方只能使用string类型做为键了，而value可以泛型，那么就会失去双参数泛型的意义。type Hashed interface { comparable string HashCode() uint64 }为了支持更多类型作为key这里我定义了一个Hashed接口作为泛型约束，可以看到comparable和string还有HashCode() uint64，comparable为了默认一些基础的数据类型例如int和float能作为键，而string大家了解他底层实现的话其实是一个包装的类型，真实的数据是[]byte类型，如果以现在的方式去使用string作为键，那么我还要针对string去做哈希才能得到最终哈希值。在看一下具体的crud代码：func NewLinkedHashMap[K Hashed, V any](capacity int, accessOrder bool) LinkedHashMap[K, V] { return LinkedHashMap[K, V]{ accessOrder: accessOrder, capacity: capacity, table: make(map[uint64]*Node[K, V], capacity), } } func (hashmap *LinkedHashMap[K, V]) Put(key K, value V) bool { // 问题就在这： // 如果是按照我现在定义接口去实现，自定义结构体实现HashCode() uint64就可以满足这个key类型约束？ // 但是如果默认内置的数据类型，就没有实现HashCode() uint64，不能满足，如果需要满足就要实现HashCode() uint64 // 解决方法我在文末列举几种 // 如果按照当前的设计则我就要回归到类型断言，根据不同类型去调用不同计算方法 // 这种是我不推荐的，我还是建议使用类型组合制造一个新的类型，然后去实现HashCode() uint64 // 或者把map[uint64]*Node[K, V]的Key也改成泛型版本 // 如果是字符串 go内置的string没有实现HashCode()uint64 sum64 := Sum64([]byte(key)) // 自定义泛型 我们自己可以实现 HashCode()uint64 sum64 = key.HashCode() node := &Node[K, V]{ Key: key, Value: value, } if hashmap.size == 0 { hashmap.head = node hashmap.tail = node return true } if node, ok := hashmap.table[sum64]; ok { node.Value = value moveNode(node) node.Next = nil addNodeAtTail(hashmap, node) hashmap.size += 1 return true } addNodeAtTail(hashmap, node) hashmap.table[sum64] = node hashmap.size += 1 return true } func (hashmap *LinkedHashMap[K, V]) Remove(key K) { } func (hashmap *LinkedHashMap[K, V]) Get(key K) *V { return nil } func (hashmap *LinkedHashMap[K, V]) Size() int { return hashmap.size } // 从两个节点中间删除节点 func moveNode[K Hashed, V any](node *Node[K, V]) { node.Next.Prev = node.Prev node.Prev.Next = node.Next } // addTail 添加节点到链表尾巴 func addNodeAtTail[K Hashed, V any](hashmap *LinkedHashMap[K, V], node *Node[K, V]) { node.Prev = hashmap.tail hashmap.tail.Next = node hashmap.tail = node }问题来了，看函数签名为(hashmap *LinkedHashMap[K, V]) Put(key K, value V)的函数，问题在这，key我在设计的时候就限制为了Hashed类型，而如果这个key在使用的时候传入的是结构体类型，结构体实现了HashCode() uint64 那么就做成key，如果是默认字符串，go内置的类型没有实现HashCode()uint64，那么我这里就要断言了，看看是不是string 然后函数内置去计算哈希？有木有什么办法不这样搞？解决方法好几种：所以最后还是回归到类型断言，我其实想有木有其他好办法解决？还有一种方法就是我在我自己包里面 自定义一个装个一个string类型代替 默认内置的string类型 去实现HashCode()uint64 接口，这样就可以正确了，不过调用者在泛型字符串的时候必须使用我包里面这个string类型。如果按照上面这种其他类型也要去实现。还有一种让内置的table泛型也是和外面的LinkedHashMap一样，交给go编译器自己去处理，那这样就没有HashCode()uint64方法了。例如下面这样我就自定义造了一个String包装类型满足key要求：type Hashed interface { // comparable // string HashCode() uint64 } type String struct { string } func (s String) HashCode() uint64 { return Sum64([]byte(s.string)) } func MakeString(str string) String { return String{ string: str, } }内外一致泛型下面是通过外内map的key泛型类型一直实现的代码，并且为其实现了迭代器代码，但是迭代器还是有点问题，不能返回节点的key：package sortmap import "github.com/auula/coffee" type Node[K comparable, V any] struct { Prev, Next *Node[K, V] Key K Value V } // Stored structure type LinkedHashMap[K comparable, V any] struct { capacity int // total capacity head, tail *Node[K, V] // linked list table map[K]*Node[K, V] // data storeage size int // current size } func New[K comparable, V any](capacity int) LinkedHashMap[K, V] { return LinkedHashMap[K, V]{ capacity: capacity, table: make(map[K]*Node[K, V], capacity), } } func (hashmap *LinkedHashMap[K, V]) Put(key K, value V) bool { node := &Node[K, V]{ Key: key, Value: value, } if hashmap.size == 0 { hashmap.head = node hashmap.tail = node hashmap.table[key] = node hashmap.size += 1 return true } if node, ok := hashmap.table[key]; ok { node.Value = value return true } addNodeAtTail(hashmap, node) hashmap.table[key] = node hashmap.size += 1 return true } func (hashmap *LinkedHashMap[K, V]) Remove(key K) { if node, ok := hashmap.table[key]; ok { moveNode(hashmap, node) hashmap.size -= 1 delete(hashmap.table, key) } } func (hashmap *LinkedHashMap[K, V]) Get(key K) (*K, *V) { var ( node *Node[K, V] ok bool ) if node, ok = hashmap.table[key]; !ok { return nil, nil } moveNode(hashmap, node) addNodeAtTail(hashmap, node) return &node.Key, &node.Value } func (hashmap *LinkedHashMap[K, V]) Clear() { hashmap.size = 0 hashmap.head = nil hashmap.tail = nil hashmap.table = make(map[K]*Node[K, V], hashmap.capacity) } func (hashmap *LinkedHashMap[K, V]) Size() int { return hashmap.size } // 从两个节点中间删除节点 func moveNode[K comparable, V any](hashmap *LinkedHashMap[K, V], node *Node[K, V]) { if node == hashmap.head { node.Next.Prev = nil hashmap.head = node.Next return } if node == hashmap.tail { node.Prev.Next = nil hashmap.tail = node.Prev return } node.Next.Prev = node.Prev node.Prev.Next = node.Next } // addTail 添加节点到链表尾巴 func addNodeAtTail[K comparable, V any](hashmap *LinkedHashMap[K, V], node *Node[K, V]) { node.Prev = hashmap.tail hashmap.tail.Next = node hashmap.tail = node } func (hashmap *LinkedHashMap[K, V]) Iter() coffee.Iterator[V] { return hashmap } func (hashmap *LinkedHashMap[K, V]) HasNext() bool { return hashmap.size != 0 } func (hashmap *LinkedHashMap[K, V]) Next() V { var node *Node[K, V] if node = hashmap.head; node != nil { hashmap.head = hashmap.head.Next hashmap.size -= 1 return node.Value } return node.Value } func (hashmap *LinkedHashMap[K, V]) Range(fn func(Node[K, V])) { var node *Node[K, V] for hashmap.size != 0 { if node = hashmap.head; node != nil { hashmap.head = hashmap.head.Next hashmap.size -= 1 fn(*node) } } }使用起来很简单：package main import ( "fmt" "github.com/auula/coffee/sortmap" ) func main() { var sm = sortmap.New[string, float64](10) sm.Put("Go", 91.2) sm.Put("Java", 100) sm.Put("Rust", 80.1) // 因为返回的是地址，如果没有返回值则为nil fmt.Println(sm.Get("Go101")) // 如果有值则返回对应类型的指针 k, v := sm.Get("Rust") fmt.Printf("\n key:%s \t value:%f \n", *k, *v) // coffee.ForEach(sm.Iter(), func(i float64) { // fmt.Println(i) // }) sm.Range(func(node sortmap.Node[string, float64]) { fmt.Printf("\n key:%s \t value:%f \n", node.Key, node.Value) }) }Go官方建议Go官方给出使用泛型的意见是使用泛型去减少一些类型一样的重复代码，例如数据结构，这样子的。但是如果把泛型用一些类型约束上还是和一些其他原因有所差距，要使用嵌套或者组合的方式重新构建新的类型去实现，然后使用构建的类型，例如上面我给出的我的这个例子。
逻辑推导二分查找算法： 也称为二分搜索算法，是一个很巧妙的算法，在实际开发中我们会经常使用到这个算法，能在很大的数量有序不重复集合下快速查找到一个元素，每次查找一次如果不符合命中条件的，那么参入搜索的集合就会被折半一次，也就是下次搜索的时候数量会少一半，原理如下图：代码实现首先要在被排序的数组里面定义两个指针，分别是low和high，还有一个middle指针，这个指针是随机的取low和high指针区间的随机数。然后每次搜索就是看需要查找的n是否等于middle指针上的元素，如果等于那么就是命中查找到元素直接返回即可。否则就看middle是否小于n，如果小于那么就把low指向middle + 1处，如果大于就把high指向middle - 1处。package main import "fmt" func main() { var arr []int = []int{10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20} index := binarySearch(arr, len(arr), 16) fmt.Println(index) } func binarySearch(arr []int, len, n int) int { // 初始化两个指针 low, high := 0, len - 1 // 两个指针的关系必须是low小于等于high for low < high { // 取中轴 middle := low + ((high-low)>>1) if arr[middle] == n { return middle } // 如果middle小于n就说明不在middle前面的范围内 // 如果middle大于n就说明不在middle后面的范围内 if arr[middle] < n { low = middle + 1 } else { high = middle - 1 } } return -1 } 需要注意的是low + ((high-low)>>1) = low + (high-low) / 2这行代码，这行代码是为了防止有时候我们需要搜索的数据量太大，经过计算得出来的值会超过int类型的表示范围，所以这来采用优化，位运算也是比传统除法性能要高很多的。下面是递归版本的实现：package me.ibyte.sorting; public class BinarySearch { public static void main(String[] args) { int[] arr = { 10, 11, 12, 13, 14, 15 ,15}; int index = bsearch(arr, 14, 0, arr.length - 1); System.out.println(index); } public static int bsearch(int[] arr, int n, int low, int hight) { if (low > high) { return -1; } int middle = low + (high - low) / 2; if (arr[middle] == n) { return middle; } if (arr[middle] < n) { return bsearch(arr, n, middle + 1, high); } else { return bsearch(arr, n, low, middle - 1); } } } 以上是我的实现代码，掌握了二分查找算法的思想其实用代码写起来就很容易，把思路转换成代码实现就可以了，如果不能理解自己可以先画一下图，例如上面就是我自己画的图，图画完就清晰多了，或者可以看看这个视频讲解二分搜索算法。优点：在一定数据量下查找数据是O(logN)，会很快的就能查找到目标数据。缺点：数据必须全部是静态的并且数据量占用内存不能太多，二分查找依赖于数组，数组存储是连续的，如果数据规模较小可以使用暴力顺序遍历查找，如果数据量较多并且在操作的时候会动态发生修改建议使用二叉搜索树或者哈希表。其实二分查找算法最核心思想是每次进行一轮搜索，数据范围会缩小n/2，这个和插入排序的进阶版本希尔排序的思想差不多。每进行一轮会在原始数组上进行数据缩减，而不是传统方式的O(n)一个一个去查找目标值，而是带着有条件有跨度去搜索，这里条件就是原数组有序并且每一轮都能确定目标数据所在的范围。变体问题二分查找本质也是分而治之的应用，本身如果搜索查找一个元素的话没有什么难度。还有一部分二分查找算法应用就是使用二分查找在有重复的数据段里面做模糊查找。例如[12,13,14,14,14,15,16,17]，这个数组里面有3个14，如果要查找其中一个14出现的位置，那么就是模糊查询了，因为要其他的而外条件才能正常工作，相关的算法问题如下几个：找出某个元素第一次出现的位置：package me.ibyte.sorting; public class FirstAppear { public static void main(String[] args) { // 查找到14第一次出现的位置 int[] arr = { 10, 11, 12, 13, 14, 14, 14, 15, 16 }; int index = firstAppear(arr, 14, 0, arr.length - 1); // 4 System.out.println(index); } public static int firstAppear(int[] arr, int val, int low, int high) { int middle = 0; while (low < high) { middle = low + (high - low) / 2; if (arr[middle] < val) { low = middle + 1; } else if (arr[middle] > val) { high = middle - 1; } else { // 如果在一个位置是就是头部说明就在头部 // 如果是在中间某一部分出现那么就看看前面是否重复如果重复就找打了 if (middle == 0 || arr[middle - 1] != val) { return middle; } else { // 如果上面条件都不满足，说明要找的元素在左半部分，砍掉右边部分 high = middle - 1; } } } return -1; } }找到最后一次出现的位置：package me.ibyte.sorting; public class LastAppear { public static void main(String[] args) { // 查找到14最后一次出现的位置 int[] arr = { 10, 11, 12, 13, 14, 14, 14, 15, 16 }; int index = fastAppear(arr, 14, 0, arr.length - 1); // 6 System.out.println(index); } public static int fastAppear(int[] arr, int val, int low, int high) { int middle = 0; while (low < high) { middle = low + (high - low) / 2; if (arr[middle] < val) { low = middle + 1; } else if (arr[middle] > val) { high = middle - 1; } else { // 本来就是最后一个了那就直接返回，如果不是就看后面的元素是否一样，不一样则返回 if ((middle == arr.length - 1 || arr[middle + 1] != val)) { return middle; } else { // 一样说明前面的范围可以排除掉，继续往后搜索 low = middle + 1; } } } return -1; } } 其实二分模糊搜索主要是考查，使用者是否掌握了基础二分查找的算法思想。模糊查找核心的点就是：看能不能找出符合元素位置的前后关系条件，根据元素前后关系条件做出查找，在每轮查询的过程中，能确定目标元素有可能所在的区间，排除不存在的区间，不断的缩小可能存在的区间范围，下面是我画的一张图，如果阅读我blog朋友也能自己画出这样的图，那说明应该是掌握了二分查找最基本区块划分的思想。下面是一些带有双重查询条件的问题，例如查找第一个大于或者等于14的元素：// 查找第一个大于等于target的元素 public static int greaterOrEqual(int[] arr, int target, int low, int hight) { int middle = 0; while (low < hight) { middle = low + (hight - low) / 2; // 这个满足大于等于 if (arr[middle] >= target) { // 但是要求是第一个或者前面一个元素小于要查找的元素，那么就是这个mid了 if (middle == 0 || arr[middle - 1] < target) { return middle; } else { hight = middle - 1; } } else { low = middle + 1; } } return -1; } 查找最后一个小于或者等于某值的元素：public static int lessThanAndEqual(int[] arr, int target, int low, int hight) { int middle = 0; while (low < hight) { middle = low + (hight - low) / 2; // 如果大于就抛弃右部分 if (arr[middle] > target) { hight = middle - 1; } else { // 然后看看是不是最后一个了，再看后面一个是不是大于前面一个 if (middle == arr.length - 1 || arr[middle + 1] > target) { return middle; } else { low = middle + 1; } } } return -1; }
一些思考很多人可能认为算法和数据结构没有多大用处，恰恰相反，我们使用的一些编程语言核心类库和一些api底层就是对数据结构加算法而组成的。很多人可能最多就是看看源代码，写点分析源代码文章，那都是已经现有的东西照着思路读就行了，而算法完全是不一样的，一个算法题解题思路可以是多种，多种数据结构解决，那这么多解决问题方法，差异在哪啦呢？这就得看自己本身对各种数据结构的特性的了解程度了，算法是应用于数据结构之上的东西，如果没有掌握好数据结构，怎么谈应用去解决实际问题呢？我看过很多人，或者大多数开发者最多就是一个API操作员，搞点框架拼积木一样，能跑就行了，当然框架能解决问题也是，也能减少开发复杂性，重复工作，那都是一些固定死的业务逻辑罢了，真正的问题是针对你业务问题而且填写你业务逻辑问题解决问题，框架做的最多就是把你外围的工作或者基础配置搭建好而已。真正的业务逻辑还是根据个人的需求去完成，框架也是别人包装出来的，但是它包装不了不同问题的解决方法，只能起到一些刚开始的约束作用，最后你会发现随着需求的改变和业务问题，你的代码还是要解决问题，还是自己去写核心逻辑代码，所以不要小看数据结构和算法的重要性。当然很多人选择if else一把梭然后call api完成任务罢了，我觉得一个好工程师最少要掌握设计模式编程范式，数据结构的应用去解决问题，那样代码水平才能提高。我看到很多人在一些语言上写溜的不行，换到Rust上就寸步难行。。实际上根本什么都不懂，面试靠着是八股文，八股文这个东西我觉得只要你不笨有脑子是个人都能背，所以我现在看到那种八股文广告就烦的狠，不是背还是要理解，这样才能技术有提升。而真正一名工程师应该是从上到下知识系统和认知面要很广，操作系统，计算机组成，计算机网络，编译原理，数据结构加算法，这些才是组成今天的计算机的东西，不说废话了本文将介绍堆的实现和堆在实际问题上的应用。堆结构什么是堆？堆是从完全二叉树演进过来的，至于什么是完成二叉树我这里就不介绍了。堆有两种组织形态：根节点的值小于左右孩子节点的值称为小顶堆，根节点的值大于左右孩子节点的值称为大顶堆。堆的用处用很多，例如解决动态数据添加删除问题，从小到大排序，可以在O(1)的时间复杂度里面获取最大值或者最小值，0(logn)的时间内添加一个节点或者删除一个节点。获取一组序列的最大的K个元素，时间复杂度为NlogK，求一些排名前几的这些问题也可以使用。优先队列就是一个例子，如果一个节点频繁添加或者删除可以把他放入大顶堆堆顶上，还有数据是动态的每次要根据新进来的数据做出调整这种也适合使用堆。最典型的应用就是高效的定时器任务扫描了，这个在Go语言里面的定时器底层有用到，具体过程如下：假设我们要设计一个定时器，定时器中维护了很多定时任务，每个任务都设定了一个要触发执行的时间点。定时器每过一个很小的单位时间比如 1 秒，就扫描一遍任务，看是否有任务到达设定的执行时间。如果到达了，就拿出来执行。像这样每次扫描的时候，把所有任务都扫描一遍，肯定很低效，如果任务比较少还好，任务比较多的话，就比较耗时。那有更高效的办法呢？答案是有的：我们可以把每个任务都存储在优先级队列中(以触发时间为优先级的小顶堆)，这样最先执行的任务就在堆顶，每次扫描的时候只需取出堆顶任务，拿对其他任务的定时时间和当前时间比较。堆构造上面说了这么多，那如何构造一个堆呢？例如下图右边就是一个大顶堆：构建很简单就是组成堆的3个元素分别比较交换位置，把最大的放到堆顶上，如果有子节点的话还要继续调整子节点，下面是我Java实现的代码： public static void heapify(int[] tree,int len,int i) { if (i >= len) { return; } int max = i,left = i * 2 + 1,right = i * 2 + 2; if (tree[left] > tree[max]) { max = left; } if (tree[right] > tree[max]) { max = right; } if (max != i) { int temp = arr[i]; arr[i] = arr[max]; arr[max] = arr[i]; heapify(tree,len,max); } } 如果输入的数组顺序是无序的，次数我们还需要对数组进行调整，以满足大顶堆的要求，原理就是对最后一组的3个元素依次往上调整直到到堆顶即可完成堆的构建，下面是我的Java代码：public static void build(int []tree,int len) { for (int i = (len - 1) / 2; i >= O; --i) { heapify(tree,len,i); } }上面build函数就可以对一个无序的数组构建成一个大顶堆结构了，实现了大顶堆就可以实现堆排序，堆排序过程也是相对很简单的，过程就是把堆顶的元素换到叶子节点的位置，把叶子节点调整到堆顶，但是如果是不能满足堆要求还要进行调整，然后重复这个过程整个数组就是有序的了，下面是我的Java代码实现：public static void sort(int[] tree,int len) { build(tree,len); for (int i = len - 1; i >= 0; i--){ int tmep = tree[i]; tree[i] = tree[0]; tree[0] = tree[i]; heapify(tree,i,0); } }然后就可以进行排序了，排序代码如下：public static void main(String[] args) { int[] arr = { 2, 5, 3, 1, 10, 4 }; Sort(arr, arr.length); System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 10] }下面这个版本是使用Go实现的，如果想使用跟多数据结构可以安装这个包，这个模块也是本人我编写的，支持泛型类型，Github地址:https://github.com/auula/coffeepackage heap func Sort[T any](tree []T, fn func(x, y T) bool) { Build(tree, fn, len(tree)) for i := len(tree) - 1; i >= 0; i-- { tree[0], tree[i] = tree[i], tree[0] Heapify(tree, fn, i, 0) } } func Build[T any](tree []T, fn func(x, y T) bool, len int) { parent := (len - 1) / 2 for parent >= 0 { Heapify(tree, fn, len, parent) parent -= 1 } } func Heapify[T any](tree []T, fn func(x, y T) bool, len, i int) { if i >= len { return } var ( max = i left, right = i*2 + 1, i*2 + 2 ) if left < len && fn(tree[left], tree[max]) { max = left } if right < len && fn(tree[right], tree[max]) { max = right } if max != i { tree[max], tree[i] = tree[i], tree[max] Heapify(tree, fn, len, max) } } type Tree[T any] struct { item []T fn func(x, y T) bool } func New[T any](fn func(x, y T) bool, v ...T) Tree[T] { var tree Tree[T] tree.fn = fn tree.item = v Build(tree.item, tree.fn, len(tree.item)) return tree } func (h *Tree[T]) Put(e T) { h.item = append(h.item, e) Build(h.item, h.fn, len(h.item)) } func (h *Tree[T]) Peek() *T { return &h.item[0] } func (h *Tree[T]) Poll() *T { element := &h.item[0] h.item = h.item[1:] Build(h.item, h.fn, len(h.item)) return element } func (h *Tree[T]) Size() int { return len(h.item) }实现定时器模块定时器模块在服务端开发中非常重要，一个高性能的定时器模块能够大幅度提升引擎的运行效率，使用heap实现一个通用的定时器模块，当然也可以使用队列实现或者链表，但是添加删除任务时间复杂度会很高。对于链表有所了解的小伙伴，应该都知道以下两点：虽然，取出链表首节点的时间复杂度是 O(1)；但是，当需要向链表中添加新的定时任务时，保持整个链表有序的时间复杂度是 O(N)。因此，当定时任务比较多，基于链表实现的定时器就会降低整个服务器的性能，所以使用堆更合适，下面是定时器调度源代码实现:package timer import ( "container/heap" // Golang提供的heap库 "fmt" "os" "runtime/debug" "sync" "time" ) const ( MIN_TIMER_INTERVAL = 1 * time.Millisecond // 循环定时器的最小时间间隔 ) var ( nextAddSeq uint = 1 // 用于为每个定时器对象生成一个唯一的递增的序号 ) // 定时器对象 type Timer struct { fireTime time.Time // 触发时间 interval time.Duration // 时间间隔（用于循环定时器） callback CallbackFunc // 回调函数 repeat bool // 是否循环 cancelled bool // 是否已经取消 addseq uint // 序号 } // 取消一个定时器，这个定时器将不会被触发 func (t *Timer) Cancel() { t.cancelled = true } // 判断定时器是否已经取消 func (t *Timer) IsActive() bool { return !t.cancelled } // 使用一个heap管理所有的定时器 type _TimerHeap struct { timers []*Timer } // 让内置heap实现sort func (h *_TimerHeap) Len() int { return len(h.timers) } // 使用触发时间和需要对定时器进行比较 func (h *_TimerHeap) Less(i, j int) bool { //log.Println(h.timers[i].fireTime, h.timers[j].fireTime) t1, t2 := h.timers[i].fireTime, h.timers[j].fireTime if t1.Before(t2) { return true } if t1.After(t2) { return false } // t1 == t2, making sure Timer with same deadline is fired according to their add order return h.timers[i].addseq < h.timers[j].addseq } func (h *_TimerHeap) Swap(i, j int) { var tmp *Timer tmp = h.timers[i] h.timers[i] = h.timers[j] h.timers[j] = tmp } func (h *_TimerHeap) Push(x interface{}) { h.timers = append(h.timers, x.(*Timer)) } func (h *_TimerHeap) Pop() (ret interface{}) { l := len(h.timers) h.timers, ret = h.timers[:l-1], h.timers[l-1] return } // 定时器回调函数的类型定义 type CallbackFunc func() var ( timerHeap _TimerHeap // 定时器heap对象 timerHeapLock sync.Mutex // 一个全局的锁 ) func init() { heap.Init(&timerHeap) // 初始化定时器heap } // 设置一个一次性的回调，这个回调将在d时间后触发，并调用callback函数 func AddCallback(d time.Duration, callback CallbackFunc) *Timer { t := &Timer{ fireTime: time.Now().Add(d), interval: d, callback: callback, repeat: false, } timerHeapLock.Lock() // 使用锁规避竞争条件 t.addseq = nextAddSeq nextAddSeq += 1 heap.Push(&timerHeap, t) timerHeapLock.Unlock() return t } // 设置一个定时触发的回调，这个回调将在d时间后第一次触发，以后每隔d时间重复触发，并调用callback函数 func AddTimer(d time.Duration, callback CallbackFunc) *Timer { if d < MIN_TIMER_INTERVAL { d = MIN_TIMER_INTERVAL } t := &Timer{ fireTime: time.Now().Add(d), interval: d, callback: callback, repeat: true, // 设置为循环定时器 } timerHeapLock.Lock() t.addseq = nextAddSeq // set addseq when locked nextAddSeq += 1 heap.Push(&timerHeap, t) timerHeapLock.Unlock() return t } // 对定时器模块进行一次Tick // 一般上层模块需要在一个主线程的goroutine里按一定的时间间隔不停的调用Tick函数，从而确保timer能够按时触发，并且 // 所有Timer的回调函数也在这个goroutine里运行。 func Tick() { now := time.Now() timerHeapLock.Lock() for { if timerHeap.Len() <= 0 { // 没有任何定时器，立刻返回 break } nextFireTime := timerHeap.timers[0].fireTime if nextFireTime.After(now) { // 没有到时间的定时器，返回 break } t := heap.Pop(&timerHeap).(*Timer) if t.cancelled { // 忽略已经取消的定时器 continue } if !t.repeat { t.cancelled = true } //必须先解锁，然后再调用定时器的回调函数，否则可能导致死锁！！ timerHeapLock.Unlock() runCallback(t.callback) // 运行回调函数并捕获panic timerHeapLock.Lock() if t.repeat { // 如果是循环timer就把Timer重新放回heap中 // add Timer back to heap t.fireTime = t.fireTime.Add(t.interval) if !t.fireTime.After(now) { t.fireTime = now.Add(t.interval) } t.addseq = nextAddSeq nextAddSeq += 1 heap.Push(&timerHeap, t) } } timerHeapLock.Unlock() } // 创建一个goroutine对定时器模块进行定时的Tick func StartTicks(tickInterval time.Duration) { go selfTickRoutine(tickInterval) } func selfTickRoutine(tickInterval time.Duration) { for { time.Sleep(tickInterval) Tick() } } // 运行定时器的回调函数，并捕获panic，将panic转化为错误输出 func runCallback(callback CallbackFunc) { defer func() { err := recover() if err != nil { fmt.Fprintf(os.Stderr, "Callback %v paniced: %v\n", callback, err) debug.PrintStack() } }() callback() }小结好了上面对比了各种结构实现的定时任务调度器优越性，也带着使用堆实现一个版本，也说明了为什么使用堆去做，并且解决问题。
树是一个非线性结构，日常很多东西都和树这个结构类似，例如：企业人员组织架构，操作系统的文件目录，如果这些信息被高度抽象到某种程度那么就是一种数据结构的应用了，这篇文章讲整理一下 树 的知识。树最简单的结构组织方式就是二叉树，二叉树是树里面应用最简单的一种树型结构，其特征就是每个节点有2个子节点或者说一个节点，也可以有一个上级节点，如果当前节点没有子节点但是有父节点那么可以认为是叶子节点。节点之间的关系就是：层次关系，左右关系，层次关系是子节点和父节点之间的关系，左右关系是父节点下的左右节点之间的关系，如下图：关于树的一些名词有： 高度 、 深度 、 层数 ，这些可以用来形容一个树的元信息。节点的高度：节点到叶子节点的最长路径的长度也就是边数。节点的深度：根节点到这个节点的路径长度的边数。节点的层数：节点的深度加上1。树的高度：也就是根节点的高度。上图就是一颗树的结构图，此结构不限于二叉树所有树形结构都适用。树的存储树的存储方式有两种，一种是链式存储，一种是数组存储；链式存储如下图，一共 3 个字段，一个字段存储数据，另外两个字段存储左右子节点：另外一种就是使用数组进行存储，连续空间存储，如下图：上面是使用数组连续空间存储的话不需要额外的空间占用去存储左右孩子节点的 child 的指针，而是通过数组的下标去访问数组上的元素，而下标访问是很特殊的公式如上图我所画的，计算公式很简单: 父节点 = 当前节点下标 / 2，左孩子节点 = 当前下标 2，右孩子节点 = 当前下标 2 + 1；当然有一个前提是数组存储的时候根节点下标为1，而不是0，如果是零的话公式还需要额外计算，大多数1为根节点下标，0有的话空出来，浪费一个位置空间没有什么特殊的。两种存储方式利弊： 第一种使用链式存储的话，在数据节点需要加入树中的时候可以动态分配内存，而数组的方式则要在使用前提取分配一堆连续的内存，然后去存储元素，因为数组的特殊性，如果数中某些子节点只要单一的孩子节点，那么数组对应上的位置为空，要预留这些位置，不能充分使用内存，如果是完全二叉树情况下推荐使用数组，对于非完全二叉树的情况下还是使用传统链式存储方式，这个可能要根据使用的时候场景进行分配。树的应用树最典型的应用就是二叉搜索树了，二叉搜索树特点就是一个节点最多只有两个节点，也可以只有一个节点，而左子节点比父节点本身小，右子节点比父节点大。如上图我所画的就是一个典型的完全二叉搜索树，并且满足左节点小于父节点，右孩子大于父节点的要求，用代码实现的话，用链式存储实现是最为简单的，下面是链式存储实现代码：package tree import "github.com/auula/coffee" type Node[T coffee.Number] struct { Data T LeftChild, RightChild *Node[T] } type BinaryTree[T coffee.Number] struct { Root *Node[T] Size int } func (bt *BinaryTree[T]) Insert(v T) { if bt.Root == nil { bt.Root = &Node[T]{Data: v} return } node := bt.Root for node != nil { if v > node.Data { if node.RightChild == nil { node.RightChild = &Node[T]{Data: v} return } node = node.RightChild } else { if node.LeftChild == nil { node.LeftChild = &Node[T]{Data: v} return } node = node.LeftChild } } } func (bt *BinaryTree[T]) Search(v T) *Node[T] { node := bt.Root for node != nil { if v < node.Data { node = node.LeftChild } else if v > node.Data { node = node.RightChild } else { return node } } return nil } 构造一颗二叉搜索树很简单，先是构造根节点，然后根据需要被插入的节点的值构造左右子节点，搜索方式也是根据节点大小进行的，时间复杂度为O(logN)。func Previous[T coffee.Number](node *Node[T], channel chan *Node[T]) { if node == nil { return } channel <- node Previous(node.LeftChild, channel) Previous(node.RightChild, channel) } func Intermediate[T coffee.Number](node *Node[T], channel chan *Node[T]) { if node == nil { return } Intermediate(node.LeftChild, channel) channel <- node Intermediate(node.RightChild, channel) } func Back[T coffee.Number](node *Node[T], channel chan *Node[T]) { if node != nil { return } Post(node.LeftChild, channel) Post(node.RightChild, channel) channel <- node }前序遍历：先根，再左，后右中序遍历：先左，再根，后右后序遍历：先左，再右，后根以上是树的三种遍历方式的代码实现，前序、中序、后续遍历实现，对应遍历的方式就是对元素组织的方式，如果要把数中的元素排序输出的话可以使用 中序遍历 ，这就是利用二叉搜索树和遍历方式的特性。相比上面3中遍历方式，还有两种遍历方式：深度优先：需要从左子节点开始遍历输出，每个分支先往叶子节点走，然后递归顺序和中序遍历一样。广度优先：按照左右子同层节点开始遍历输出，递归是每个子树进行，先左，后右，再往下层走。删除节点二叉树搜索树另外一个点就是对节点进行删除调整操作，删除操作相比添加和搜索节点相对来说复杂一点，而且树的结构形状有多样的。例如：直接删除叶子节点这是最简单的，直接操作父节点的指针即可完成，而另外一种就是有左右孩子节点，这种情况就是移动右子节点到当前节点位置如下图：func (bt *Tree[T]) Delete(v T) *Node[T] { return delete(bt.root, v) } func delete[T coffee.Number](node *Node[T], v T) *Node[T] { if node == nil { return nil } if v < node.Data { node.LeftChild = delete(node.LeftChild, v) } else if v > node.Data { node.RightChild = delete(node.RightChild, v) } else { // 如果找到了看看有没有左右子节点 if node.LeftChild == nil { return node.RightChild } if node.RightChild == nil { return node.LeftChild } // 不断的在右边找最小节点，然后换上去 minNode := node.RightChild for minNode.LeftChild != nil { minNode = node.LeftChild } node.Data = minNode.Data // 换上去直接再把右子节点最小值删除掉 node.RightChild = delete(node.RightChild, minNode.Data) } return node }删除逻辑： 删除节点逻辑和查找节点逻辑有点类似，区别在于要删除节点，首先要判断要删除的元素在树的左边还是右边，如果在左边，那么就不断的递归往下找。递归逻辑就是 每次要进行区分在左还是在右 ，如果匹配到节点，那么就要有没有左右子节点，然后在右子树找到最小值替换到节点上，然后再去右子树把值删除掉，测试代码如下：package main import ( "fmt" "github.com/auula/coffee/bst" ) func main() { tree := bst.New[int]() tree.Insert(10) tree.Insert(9) tree.Insert(16) tree.Insert(3) tree.Insert(10) tree.Delete(9) channel := make(chan *bst.Node[int]) go func() { bst.Previous(tree.Root, channel) close(channel) }() for v := range channel { fmt.Println(v) } }元素重复上面我整理了二叉搜索树的普通情况，元素都是不存在重复的情况比较好处理，如果遇到重复的元素，要怎么处理呢？第一种处理方式很简单： 和哈希表设计一样遇到元素一样的就使用一个数组存储或者说使用链表存储，类似于解决哈希表的元素冲突方式。第二种处理方式复杂： 需要把插入的元素放到相等元素的右子树，也就是当插入完成之后，右子节点的字数里面有和当前元素相同的元素存在，这样查找元素的时候需要注意要查找整个树节点，范围为第一个重复元素出现位置到叶子节点位置。树的平衡二叉搜索树在数据分布的比较均匀的情况下，树的节点相对来说查找速度就很快 O(logN) ，如果树上元素不能均匀分布，偏向另外一边那就退化成链表 O(N) 了，如下图：为了解决这些问题，那么就要针对这颗树，进行调整了，很多计算机前辈提出来了平衡树概念：红黑树，AVL 树，这些都是为了解决树元素不能平衡分布的而提出来的新型树元素组织方式。但是为了满足节点平衡每次插入数据的时候需要进行数据调整，每次插入节点都需要维持平衡性，但是调整过程很繁琐。B+树B+树也是B树延伸过来的，这里的 B 是指的是 Balanced 意思。B+ 树最常见的用处就是在数据库索引领域，树的节点除了叶子节点存储具体的数据以外，上层的节点全部用做索引的（稠密索引），上层的节点都是区间索引，可以通过二分查找法进行查找数据的。B+ 树的高度和查询次数的 io 成正比，B+ 树解决的问题传统索引可能全部把所有索引存储在内存里面，但是 B+ 树把根索引存放在内存，其他节点可以存储在硬盘里面。对应一个 B+ 树的层次来说，每层节点越多，那么数的高度就越小，对应的 io 操作次数也会小。其实抽象到一定程度，其实解决的问题，和跳表一样，把一个有序链表分割成多个段。跳表教程B+ 树的缺点就是，如果当叶子节点的元素个数小于2的时候需要触发一次合并，合并操作就是把多就叶子节点合并成一个节点，合并过程比较难用实现，当然这是我个人这么认为的，做到了解工作原理就可以。B+树由m叉查找树和叶子结点有序链表组成的。每个节点中子节点的个数不能超过m个并且也不能小于m/2个。根节点的子节点个数可以不超过m/2，这是一个例外。一般情况下根节点被存储在内存中，其他节点存储在硬盘中。为了保证每次操作的时候节点符合以上规则，需要动态调整节点，写入操作的时候数据，会变慢。相对于B树的差别在于节点不存储数据，所有数据存储在叶子节点中，其他节点为数据索引查找节点。小 结树和哈希表都可以起到搜索一个元素的效果，但是二者有什么不同呢？如果从实现角度来讲的话，二叉树实现起来比哈希表简单，设计一款好的哈希表要考虑存储方式，哈希函数，哈希冲突并且元素是无序的，等其他一些因素。而设计一颗二叉树紧要知道怎么去组织节点层次关系就可以了，相当于元素输出方式，二叉树有多种：前序遍历、中序遍历、后序遍历。