数组

哈希链表vs数组加强哈希表

type: comparison tags: [数据结构, 哈希表, 链表, 数组, 组合结构] created: 2026-05-03 updated: 2026-05-03哈希链表 vs 数组加强哈希表对比两种基于哈希表的组合数据结构设计概述| 维度 | 哈希链表 (Hash Linked List) | 数组加强哈希表 (Hash Table + Array) | |------|---------------------------|-----------------------------------| | 别名 | LinkedHashMap | Hash Map with Array / Randomized HashMap | | 核心目标 | 维护键的插入顺序 |

数组vs链表

type: comparison tags: [数据结构, 对比, 数组, 链表] created: 2026-05-02 updated: 2026-05-02数组 vs 链表 对比两种基础线性数据结构的多维度对比分析核心差异| 维度 | 数组 (Array) | 链表 (Linked List) | |------|-------------|-------------------| | 内存布局 | 连续内存空间 | 离散内存块，通过指针连接 | | 随机访问 | $O(1)$ - 支持 | $O(N)$ - 不支持 | | 头部插入/删除 | $O(N)$ -

二分查找

type: concept tags: [算法技巧, 查找算法, 双指针, 分治算法] created: 2026-05-09 updated: 2026-05-09二分查找（Binary Search）二分查找在有序搜索空间中不断排除一半候选区间，将查找复杂度降到 O(log n)。定义二分查找是一种在有序数组或有序搜索空间中查找目标值的算法。它每次取中点 mid，根据 nums[mid] 与目标值的大小关系，缩小左半区间或右半区间。核心特性| 特性 | 说明 | |------|------| | 前提条件 | 搜索空间有序，或答案空间具有单调性 | | 指针模式 | 左右指针维护搜索区间 | | 时间复杂度 | O(log n) | | 空间复杂度 | O(1)（迭代实现） | | 常见难点 | 区间开闭、边界收缩、重复元素处理 |基本框架int binarySearch(int[]

位图

type: concept tags: [数据结构, 位图, BitMap, 哈希表] created: 2026-05-04 updated: 2026-05-04位图（BitMap）定义位图（BitMap）是一种用二进制位（bit）来表示状态的数据结构，每个 bit 对应一个元素的存在状态（1 表示存在，0 表示不存在）。核心优势空间效率极高：相比布尔数组（1 byte/元素），位图仅用 1 bit/元素，节省 7/8 的空间适合超大规模数据：如判断 10 亿个整数中是否存在某个数，仅需 ~120MB 空间局限性仅支持整数类型的数据无法处理字符串等其他类型布隆过滤器是其扩展，支持更多数据类型 → [[布隆过滤器]]相关概念[[哈希表]]：位图可作为哈希表的简化替代（仅判断存在性）[[布隆过滤器]]：基于位图的扩展[[数组]]：底层用位数组（bit array）实现

动态数组

type: concept tags: [数据结构, 数组, 动态数组, 扩缩容, Java] created: 2026-05-02 updated: 2026-05-02动态数组（Dynamic Array）一种能够自动调整容量的数组数据结构，底层仍是静态数组，但通过封装扩缩容逻辑，提供了更灵活的使用接口。定义动态数组是在静态数组基础上封装的数据结构，能够在运行时自动调整存储容量。当元素数量超过当前容量时自动扩容，当元素数量过少时可能缩容以节约内存。常见实现：Java: ArrayListC++: std::vectorPython: list（本质是可变数组）JavaScript: Array（引擎自动管理）核心原理1. 底层结构动态数组 = 静态数组 + 元信息 + 扩缩容逻辑MyArrayList<E> ├── data: E[] // 底层静态数组 ├── size: int

哈希表

type: concept tags:哈希表数据结构HashMap键值对哈希函数 created: 2026-05-03 updated: 2026-05-03哈希表（Hash Table）定义哈希表（Hash Table，也称散列表）是一种基于哈希函数实现的数据结构，能够在平均 O(1) 时间内完成插入、删除和查找操作。核心思想：通过哈希函数将键（key）映射到数组的某个索引位置，直接访问该位置获取数据。基本原理键值对 (key, value) │ ▼ 哈希函数 hash(key) → 数组索引 index │ ▼ 数组 table[index] = value伪码表示put(key, value): index = hash(key)

环形数组

type: concept tags: [数据结构, 数组, 队列, 栈] created: 2026-05-03 updated: 2026-05-03环形数组（Circular Array/Ring Buffer）是一种通过模运算实现循环复用的数组结构，避免普通数组增删时的元素移位开销。核心特性底层是普通静态数组，通过头指针（head）和尾指针（tail）标记有效区间利用模运算（index % 数组长度）实现指针循环移动，无需移动元素支持 O(1) 时间复杂度的头尾增删操作应用场景实现队列/双端队列（避免出队时的数组移位）实现栈（简化动态数组的扩缩容逻辑）循环缓冲区（如网络IO、日志缓冲）相关概念[[数组]][[队列]][[栈]][[动态数组]]

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: [数据结构, 双端队列, 队列, 链表, 数组, Java] created: 2026-05-03 updated: 2026-05-03双端队列实现[[raw/articles/2026/05/双端队列实现]]核心要点双端队列（Deque）基本原理双端队列（double-ended queue）是一种允许在队头和队尾两端都进行插入和删除操作的线性数据结构。对比标准队列：标准队列（Queue）：FIFO，只能队尾插入、队头删除双端队列（Deque）：队头和队尾都可以插入/删除，不再满足 FIFO类比：标准队列 → 排队买票（先来先买）双端队列 → 过街天桥（两端都可以进出）API 接口class MyDeque<E> { void addFirst(E e); // O(1) 队头插入 void addLast(E e);

哈希表基础

type: summary tags: [哈希表, HashMap, 数据结构, Java, 哈希函数, 负载因子, 哈希冲突, 拉链法, 线性探查法] created: 2026-05-03 updated: 2026-05-03哈希表基础[[raw/articles/2026/05/哈希表基础]]核心要点1. 哈希表 vs MapMap 是接口，仅声明操作方法（get/put/remove），未指定实现方式HashMap 是 Map 的一种实现，底层使用哈希表，增删查改复杂度 O(1)其他实现如 TreeMap（红黑树，O(logN)）、LinkedHashMap（保持插入顺序）不能假设所有键值对操作都是 O(1)，需看具体实现的数据结构2. 哈希表基本原理哈希表 = 加强版数组核心机制：通过哈希函数将 key 映射到数组索引，实现 O(1) 访问伪码逻辑：put(key, value): table[hash(key)] = value get(key): return table[hash(key)] remove(key): table[hash(key)] = null3. 哈希函数设计作用：将任意类型

数组双指针技巧总结

type: summary tags: [双指针, 数组, 算法技巧, LeetCode] created: 2026-05-05 updated: 2026-05-05数组双指针技巧总结[[raw/articles/2026/05/数组双指针技巧总结]]一句话总结系统讲解数组中的双指针技巧，分为快慢指针（原地修改、滑动窗口）和左右指针（二分查找、n数之和、反转、回文）两大类，配合 LeetCode 经典题目实践。核心要点1. 双指针两大分类数组中的双指针技巧主要分为两类：| 类型 | 指针移动方式 | 典型应用 | |------|-------------|----------| | 快慢指针 | 同向而行，一快一慢 | 原地修改、滑动窗口 | | 左右指针 | 相向而行或相背而行 | 二分查找、n数之和、反转、回文 |2. 快慢指针：原地修改核心思想：慢指针 slow 走在后面，快指针 fast 走在前面探路，找到符合条件的元素就赋值给 slow 并前进。经典问题：| LeetCode | 问题 |

数组实现队列和栈

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() →

用数组加强哈希表

type: summary tags: [数据结构, 哈希表, 数组, 随机算法, 数据结构设计] created: 2026-05-03 updated: 2026-05-03用数组加强哈希表[[raw/articles/2026/05/用数组加强哈希表]]核心问题在标准哈希表 API 基础上，添加 randomKey() API，要求 O(1) 时间复杂度随机返回一个键（均匀随机）。interface Map<K, V> { V get(K key); void put(K key, V value); void remove(K key);

算法总结

type: summary tags: [算法, 数据结构, 穷举, 框架思维, 回溯算法, 动态规划, BFS, DFS] created: 2026-05-05 updated: 2026-05-05算法总结[[raw/articles/2026/05/算法总结]]一句话总结数据结构的本质是数组和链表的变换；算法的本质是穷举，关键是"无遗漏、无冗余"。核心思想一、数据结构的本质所有数据结构皆为数组（顺序存储）和链表（链式存储）的变换。1.1 存储方式只有两种| 数据结构 | 底层实现 | 特点 | |---------|---------|------| | 队列、栈 | 数组或链表 | 数组实现需处理扩容缩容；链表实现无需扩容但多内存开销 | | 图 | 邻接表（链表）或邻接矩阵（二维数组） | 邻接矩阵判断连通性快但耗费空间；邻接表节省空间 | | 哈希表 | 大数组 + 散列函数 | 拉链法需链表特性；线性探查法需数组特性 | | 树

队列和栈基础

type: summary tags: [队列, 栈, 数据结构, 操作受限] created: 2026-05-03 updated: 2026-05-03队列和栈基础[[raw/articles/2026/05/队列和栈基础]]核心要点队列和栈都是操作受限的数据结构，基于数组（顺序存储）和链表（链式存储）实现。队列（Queue）特性：先进先出（FIFO — First In First Out）操作限制：只能在队尾插入元素，在队头删除元素类比：排队买票，先来的先离开栈（Stack）特性：先进后出（LIFO — Last In First Out）操作限制：只能在栈顶插入和删除元素类比：一摞盘子，最后放的在最上面，最先被拿走基本 API队列 API| 方法 | 描述 | 时间复杂度 | |------|------|-----------| | push(E e) | 向队尾插入元素 | O(1) | | pop() | 从队头删除并返回元素 | O(1) | | peek()