环形数组

（Circular Array/Ring Buffer）是一种通过模运算实现循环复用的数组结构，避免普通数组增删时的元素移位开销。

核心特性

  • 底层是普通静态数组，通过头指针（head）和尾指针（tail）标记有效区间
  • 利用模运算（index % 数组长度）实现指针循环移动，无需移动元素
  • 支持 O(1) 时间复杂度的头尾增删操作

应用场景

  • 实现队列/双端队列（避免出队时的数组移位）
  • 实现栈（简化动态数组的扩缩容逻辑）
  • 循环缓冲区（如网络IO、日志缓冲）

相关概念

Link to this note

哈希链表

type: concept tags: [数据结构, 哈希表, 链表, 组合结构] created: 2026-05-03 updated: 2026-05-03哈希链表定义哈希链表（Hash Linked List）是一种组合数据结构，将哈希表与双向链表结合，兼具两者的优点：哈希表特性：O(1) 时间复杂度的增删查改链表特性：维护元素的逻辑顺序（如插入顺序）实现原理核心思想：每个哈希表节点同时维护链表指针哈希表 table 数组 ↓ [桶0] → Node(key1, val1) ⇄ Node(key2, val2) ← 双向链表 [桶1] → Node(key3, val3) [桶2] → null ... 双向链表维护所有节点的插入顺序： head ⇄ Node(key1) ⇄ Node(key2) ⇄ Node(key3) ⇄ tail操作逻辑：插入：按哈希表方式插入，同时追加到双向链表尾部删除：从哈希表中移除，同时从双向链表中摘除遍历：按双向链表顺序遍历，得到插入顺序典型实现Java LinkedHashMapJava 标准库的 LinkedHashMap 是哈希链表的典型实现：LinkedHashMap<String, Integer>

队列

type: concept tags: [数据结构, 操作受限, 线性结构] created: 2026-05-03 updated: 2026-05-03队列（Queue）定义队列是一种操作受限的线性数据结构，遵循**先进先出（FIFO, First In First Out）**原则。核心特性只能在队尾插入元素（入队，enqueue）只能在队头删除元素（出队，dequeue）类比：排队买票，先到先服务基本 API|------|------|-----------| | push(E e) / enqueue(E e) | 向队尾插入元素 | O(1) | | pop() / dequeue() | 从队头删除并返回元素 | O(1) | | peek() / front() | 查看队头元素（不删除） | O(1) | | size() |

index

Harness Engineering Wiki - 内容索引本页面由 Claude 自动维护，每次 ingest 新资料后更新📊 Stats总页面数: 151实体页: 2概念页: 81摘要页: 62对比页: 6最后更新: 2026-05-09📚 摘要页 (Summaries)| 页面链接

log

Harness Engineering - 操作日志本页面记录所有 Claude 的操作记录，仅追加，不修改历史记录[2026-05-02] init | 初始化仓库结构创建 raw/ 目录结构（articles, papers, images）创建 wiki/ 目录结构（entities, concepts, summaries, comparison）创建 wiki/index.md 索引页创建 wiki/log.md 操作日志仓库初始化完成[2026-05-02] ingest | 时间空间复杂度入门保存原始内容到 raw/articles/复杂度分析基础.md创建摘要页 wiki/summaries/2026-05-02 时间空间复杂度入门.md侧重：复杂度分析的实用方法（Big O 简化估算技巧）更新 wiki/index.md：摘要页数量 0→1注意：labuladong 实体和复杂度概念首次出现，暂不创建独立页（需 ≥2 篇来源）[2026-05-02] ingest | 数组基础（labuladong）提取网页内容（defuddle）并创建摘要页 wiki/summaries/2026-05-02 数组基础.md创建实体页

哈希表与链表组合原理

type: summary tags: [哈希表, 链表, LinkedHashMap, 哈希链表, Golang, Java] created: 2026-05-03 updated: 2026-05-03哈希表与链表组合原理[[raw/articles/2026/05/哈希表与链表组合原理]]核心要点1. Golang map 的随机遍历顺序Golang 的 map 每次遍历顺序都不同，这是故意设计的，目的是防止开发者依赖哈希表的遍历顺序。实现原理：不触发扩缩容时，底层 table 数组的存储顺序是固定的遍历时不是从数组头部开始，而是从一个随机位置开始利用环形数组技巧遍历整个 table 数组这样既保证随机性，又不牺牲太多性能示例遍历顺序变化：| 1 2 3 4 5 5 | 1 2 3 4 2 3 4 5 | 1 | 1 2 3 4 52.

数组实现队列和栈

type: summary tags: [数组, 栈, 队列, 动态数组, 环形数组, 时间复杂度] created: 2026-05-03 updated: 2026-05-03数组实现队列和栈[[raw/articles/2026/05/数组实现队列和栈]]一句话总结用数组作为底层数据结构实现栈和队列：栈用动态数组尾部作为栈顶（O(1)），队列用环形数组实现 FIFO 操作（O(1)）。关键要点1. 用数组实现栈方法：把动态数组的尾部作为栈顶时间复杂度：push() - O(1)：arr.add(e)pop() - O(1)：arr.remove(arr.size() - 1)peek() - O(1)：arr.get(arr.size() - 1)为什么不选头部作为栈顶：数组头部增删是 O(n)，不符合栈的效率要求2. 用环形数组实现栈方法：使用 CycleArray 类，以头部作为栈顶时间复杂度：O(1)（环形数组头部增删是 O(1)）API 映射：push() → addFirst()pop() → removeFirst()3. 用环形数组实现队列方法：复用 CycleArray 类实现标准队列时间复杂度：O(1)API 映射：push() → addLast()（入队）pop() →

Interactive Graph