最新

什么是 ChaosTree？ ChaosTree 是一个零依赖的 Java 有序集合/映射库，围绕多种树实现构建。 它提供了以下实现： - AVL 树 - 红黑树 - B 树 - B+ 树 我没有创建自定义 API，因为它实现了 NavigableSet、NavigableMap、SequencedSet 和 SequencedMap。我的自定义 API 包括： - `buildFromSorted(Iterator<T> it, float factor)` - `importFlatMatrix(Object[][] blast, float factor)` - `Object[][] exportFlatMatrix()` 我开始开发 ChaosTree 是因为我想探索我对数据结构理解的极限。最初，它是一个包含 7 种集合类型树的第一个版本，带有自定义 API。随着我对此的深入，我转向了映射。在从集合转向映射的过程中，我经历了巨大的变化和知识的提升，将我的树支持从 JDK 11+ 提升到 JDK 21+，并密切关注了无依赖性、内存布局、分配、JVM 行为和实际性能。 我进行的一些实验包括： - 不同的节点布局和元数据占用空间 - 用于树实现的 CRTP/F-有界多态 - 带父指针的节点与不带父指针的节点 - 基于数组的 N 叉树节点 - B 树/B+ 树的阶数选择 - JMH 基准测试和 JFR 性能分析 - 与 `java.util.TreeMap`/`TreeSet` 进行差分/随机测试 经过这些艰难的测试，它还通过了以下测试： - Guava Testlib 兼容性测试 - jqwik 属性驱动测试 - 与参考集合的随机差分测试 - 树节点的白盒结构验证 - B 树/B+ 树结构不变量的直接验证 - 异常和迭代器契约测试 - 序列化和克隆测试 - N 叉树使用自定义 jqwik API 验证测试 尾部延迟行为未在此处显示，因为它被截断为简单的文本，导致数据读取错误：https://chaos-vy.github.io/ChaosTree/utils/JMH-Report.html 我还对官方 JDK TreeMap 运行了基准测试，并更新了我的 N 叉树。 GitHub： https://github.com/Chaos-vy/ChaosTree https://chaos-vy.github.io/ChaosTree/ 我特别希望获得关于 API 设计、实现选择和基准测试方法的反馈。我目前正在尝试截断无用和复杂的代码分支以进行性能调优。