动态数组、哈希表、队列与栈：四种基础数据结构的原理与工程实践

从面试聊起吧。最近帮团队招人面了好几位候选人简历上都写着“熟悉常用数据结构与算法”。我一般会先问一个自认为很简单的问题一个动态数组往尾部追加元素时间复杂度是多少有人答 O(1)有人答 O(n)也有人愣住说“平均是O(1)吧”。他们都没错但当我追问“为什么扩容一次要付出 O(n) 的代价却还能说均摊 O(1)”的时候能讲清楚的人就少了很多。哈希表、队列、栈也类似人人都会用但“为什么这么设计”“什么场景选哪个”“底层到底怎么跑的”这三连问往往才是区分水平的关键。这篇我就把自己这些年用集合类数据结构的经验整理出来围绕动态数组、哈希表、队列、栈这四种最基础的“容器”讲清楚它们的设计逻辑、核心操作、典型应用以及我实际踩过的坑。不堆理论尽量用“人能听懂的话”把底层讲透。适合刚入门想打好基础的同学也适合工作两三年想回头补内功的开发者。1. 四个基础集合为什么必须吃透1.1 集合类数据结构到底在解决什么问题你写代码本质上就是在处理数据一组用户列表、一批订单、一堆日志、一串消息。数据很少是孤立存在的绝大多数情况下是一群一群出现的。这时候你就需要一个“容器”把它们装起来同时支持往里放、往外取、按条件找、按顺序遍历。这类专门管理“一组元素”的数据结构就是集合类数据结构。动态数组、哈希表、队列、栈就是四个最基础的容器。它们解决的问题各不相同动态数组解决“有序存储、按下标随机访问”的问题哈希表解决“快速查找、快速去重”的问题队列解决“先进先出、缓冲削峰”的问题栈解决“后进先出、回溯嵌套”的问题。但很多人的问题恰恰在于只把它们当成“API调用”不知道每种结构背后的抽象模型。数组就是下标访问哈希表就是 key-value队列就是排队栈就是摞盘子——这种理解太浅了。真正干活的时候你需要知道动态数组为什么扩容扩容会影响什么哈希表什么情况下会退化队列满了怎么办栈除了函数调用还能干什么。1.2 从零构建动态数组——扩容背后的工程哲学先说说动态数组。很多语言里叫 ArrayList、List或者干脆就是默认的数组类型动态扩容对使用方透明。但“透明”不等于“没有成本”。动态数组的本质仍然是连续内存上的一段空间只不过比原生数组多了一个“自动扩容”的机制。底层逻辑不复杂初始分配一块固定大小的连续内存比如容量是 8往里塞元素塞到 8 个满了再追加第 9 个时就重新申请一块更大的内存把旧数据全部拷贝过去然后释放旧内存。这块新内存多大常见策略是扩成原来的 1.5 倍或 2 倍具体取决于语言实现和内存分配策略。有人会问为什么是 1.5 倍或者 2 倍而不是“每次多分配一个”或者“直接翻十倍”每次只多分配一个会导致频繁扩容每加一个元素都要复制整个数组追加操作的复杂度退化成 O(n)直接翻十倍又会让内存浪费很严重。1.5 到 2 倍之间是一个折中让扩容次数尽量少同时把空间浪费控制在可接受范围。那“均摊 O(1)”是怎么回事我用等比数列求和来算一下假设初始容量是 1每次翻倍那么容量变化是 1、2、4、8、16……如果最终数组里有 n 个元素扩容的总代价大约是 124...n/2n等比数列求和结果是 2n 左右。也就是说插入 n 个元素的过程中所有扩容拷贝工作加起来也就 O(n)平摊到每次插入头上就是 O(1)。这就是均摊分析的魅力单次操作可能很慢但整体操作序列是高效的。注意动态数组在中间插入或删除元素仍然需要搬移后续元素这是 O(n) 操作。很多人忽略这一点以为动态数组什么操作都快结果在循环里往头部 insert把 O(n²) 的复杂度写出来线上数据一大就出事。2. 哈希表让查找变成 O(1) 的魔法到底藏在哪里2.1 哈希函数与散列冲突的基本原理哈希表是我认为最值得深挖的一个基础结构因为它不是“理所当然”就能 O(1) 的背后有数学和工程的双重支撑。核心思想是把 key 通过一个哈希函数计算出一个整数再把这个整数映射到数组的某个下标这样就能直接通过下标访问不需要逐个比较。比如有 16 个桶一个字符串 key 算出来的哈希值是 105102那么 105102 mod 16 14这个 key 就放在下标 14 的位置。下次查的时候重新算一遍哈希直接去下标 14 找操作次数是常数。但哈希函数不是完美的。两个不同的 key 可能算出同样的下标这就是“哈希冲突”也叫散列碰撞。冲突如果处理不好哈希表会从“平均 O(1)”退化成“最坏 O(n)”。最常见的处理方式有两种开放寻址法和链地址法。开放寻址法即冲突了就往下一个空位放比如线性探测下标 14 被占了就试 15、16、17……直到找到空位。链地址法则是每个桶不再存单个元素而是存一个链表或红黑树冲突的元素挂在同一条链上。2.2 哈希表的工程落地——从开放寻址到链地址法实操中链地址法更常见因为实现简单、删除方便、对负载因子不那么敏感。很多主流语言的哈希表实现就是“数组链表”的变体初始一个数组每个位置是一个桶元素进来后先算下标挂到对应桶里当桶里元素太多时从链表升级成红黑树避免极端情况下链路过长。这里有个关键参数叫“负载因子”等于“已有元素数量 / 桶的总数”。负载因子越高冲突概率越大查找效率下降。工程上一般把负载因子控制在 0.75 左右。为什么是 0.75这是用泊松分布推出来的一个经验值可以让冲突概率维持在一个很低水平同时空间利用率又不至于太低。当负载因子超过阈值哈希表就会触发扩容重新申请更大的桶数组把所有元素重新计算哈希并放置到新桶里。这个操作和动态数组扩容一样是 O(n) 的所以如果数据量突然暴涨扩容瞬间会有一次明显的耗时。哈希函数的选择也很讲究。字符串哈希、整数哈希、复合对象哈希各有各的套路。核心原则是分布要均匀计算要快。如果哈希函数设计得差比如所有 key 都映射到同一个桶那哈希表直接退化成链表查询从 O(1) 变成 O(n)。2.3 真实场景缓存、去重、索引哈希表在工程里几乎无处不在。内存缓存是典型场景传入一个查询条件算出一个 key去哈希表里找找到了直接返回结果没找到再去数据库查查完塞回哈希表。这能挡住大量重复的数据库查询。另一个常见场景是去重日志系统里要过滤重复事件往哈希表里记一下事件 ID新事件来了先查一下存在就丢弃不存在就插入。再一个是索引很多数据库的等值查询索引底层叶子节点是 B 树但内存里的映射层经常用哈希结构做快速定位。我也见过不少同学自己写工具类本来一个哈希表就能搞定的去重非要用两层循环遍历列表数据量一到千级就明显卡顿。选对数据结构比“优化代码逻辑”见效快得多。3. 队列与栈两种“排队哲学”和它们的禁忌3.1 栈后进先出的场景威力栈这个结构规则只有一句话后进先出。所有的操作都发生在栈顶入栈就是往栈顶放出栈就是取栈顶元素。它太简单了简单到很多初学者轻视它。但实际上栈是理解“递归”“嵌套”“回溯”这类问题的钥匙。函数调用本身就是用栈实现的每一次函数调用都会把返回地址、局部变量压入调用栈函数返回时再弹出。递归调用过深导致栈溢出就是因为调用栈被压满了。浏览器的后退按钮也是栈每访问一个新页面就入栈点后退就是出栈。编辑器里的 Undo 也是栈每一次操作记录入栈撤销时从栈顶弹出。括号匹配的经典问题也能用栈优雅解决遇到左括号就入栈遇到右括号就弹出栈顶检查类型是否匹配遍历完以后栈为空说明括号是配对的。这类题眼熟吧但面试考它并不是为了刁难人而是在考察你能否识别出“嵌套结构”与“栈”之间的关系。3.2 队列先进先出的工程价值队列的规则正好反过来先进先出。先到的先处理后来的排队等。这个模型在工程里太重要了。消息队列、任务队列、网络请求缓冲、打印任务排队全是队列的典型应用。为什么需要队列因为“生产者”和“消费者”往往速度不一致。用户疯狂下订单订单处理系统能力有限如果直接把请求怼给处理器处理器会过载甚至崩溃。中间加一个队列生产者把订单放进去消费者按自己的节奏慢慢处理这就是削峰填谷也是消息队列最基础的价值。队列的实现有几个层级。最简单的可以基于动态数组或链表写生产环境里常用“循环队列”让数组的首尾相连避免频繁搬移数据让入队出队都保持在 O(1)。比如一个容量为 8 的循环队列队尾指针到 7 之后如果队头已经出队了队尾可以回到 0 继续写而不是把整个数组往前搬。队列还有一个变体叫优先队列。它不严格按先进先出而是按“优先级”出队。实现优先队列最常用的数据结构是堆但逻辑上依然是一个队列模型进去的元素不保证顺序出来时优先级最高的先出。这在任务调度、Dijkstra 最短路径算法里都有应用。3.3 双端队列与单调栈的变体常被忽略的两个变体双端队列和单调栈。双端队列Deque允许在头尾两端都进行插入和删除灵活性比普通队列高很多。滑动窗口最大值这类问题最经典的解法就是维护一个双端队列队头是当前窗口最大值新元素进来时从队尾弹出比它小的元素窗口滑动时从队头移除过期元素。单调栈则是单调递增或单调递减的栈结构。它的典型应用是“找下一个更大元素”给定一个数组对每个元素求右边第一个比它大的元素。暴力做法是 O(n²)用单调栈只要 O(n)。原理简单说就是维护一个栈让栈内元素保持单调新元素来的时候不断弹出栈顶比它小的元素弹出去的元素就找到了它的“下一个更大元素”。这种结构第一次接触会觉得绕但写熟之后再看很多算法题会觉得非常爽。4. 实操用代码把四种结构跑起来4.1 动态数组的实现与扩容调试为了说明白底层我用类 Python 的语法写一个极简动态数组。先不依赖语言内置的 List 特性用固定数组来模拟class SimpleArray: def __init__(self): self.capacity 4 self.size 0 self.data [None] * self.capacity def push(self, value): if self.size self.capacity: self._resize(self.capacity * 2) self.data[self.size] value self.size 1 def _resize(self, new_capacity): new_data [None] * new_capacity for i in range(self.size): new_data[i] self.data[i] self.data new_data self.capacity new_capacity def pop(self): if self.size 0: raise IndexError(pop from empty array) self.size - 1 return self.data[self.size] def get(self, index): if index 0 or index self.size: raise IndexError(index out of range) return self.data[index]你自己跑一遍就能观察到到第 4 次 push 时容量满了触发扩容到 8到第 8 次 push 时再扩容到 16。如果你在扩容函数里打个日志每次触发扩容都会打印一次这时候你会直观感受到为什么“尾部追加均摊 O(1)”——扩容偶尔会痛一次但大部分时候 push 就是一次赋值加一个指针移动。调试动态数组最常见的坑是缩容。很多人实现了扩容但忘了缩容。如果一个大数组被撑到 1 百万容量然后大部分元素被删掉只剩下 10 个容量还留在 1 百万纯属浪费内存。但缩容也不能太激进否则在临界点来回插入删除会导致频繁扩容缩容性能抖动。工程上的做法是当 size 降到容量的 1/4 时才缩容到一半留出缓冲区间。4.2 哈希表实现中的坑哈希表实现里我遇到过的坑比动态数组多得多。第一个坑是哈希函数的性能。如果你的 key 是一个很长的字符串每一次 get、put 都要重新遍历整个字符串计算哈希这个成本可能超过你的想象。解决办法是“缓存哈希值”字符串对象内部保存一个字段记录已算出的哈希算过一次之后再也不重算。第二个坑是哈希冲突的“最坏情况”。正常情况下哈希分布挺均匀但如果 key 是用户可控的比如 HTTP 参数名攻击者就可能构造出一批哈希值相同的 key导致所有数据挂到同一个桶里哈希表直接退化成链表。这种攻击在业界叫哈希碰撞拒绝服务攻击。防御手段一般是随机化哈希种子、限制单个桶大小、超阈值自动升级成红黑树。这件事说明一个道理数据结构不是“设计出来就完事”还得考虑边界和安全性。第三个坑是扩容时的 rehash。扩容不只是“把数组变大”而是要把所有元素按新桶数重新计算下标。如果扩容过程中有新线程同时读写就可能出现元素丢失或者短暂查不到。生产级哈希表会做渐进式 rehash扩容期间新元素按新规则插入旧元素按批次慢慢搬移读取时先查新表再查旧表。这是一个非常经典的工程优化面试聊到“哈希表并发问题”时很能体现水平。下面是一个简化版的哈希表示例用链地址法处理冲突class SimpleHashMap: def __init__(self, capacity8): self.capacity capacity self.size 0 self.buckets [[] for _ in range(capacity)] def _hash(self, key): return hash(key) % self.capacity def put(self, key, value): idx self._hash(key) bucket self.buckets[idx] for i, (k, v) in enumerate(bucket): if k key: bucket[i] (key, value) return bucket.append((key, value)) self.size 1 if self.size self.capacity * 0.75: self._resize(self.capacity * 2) def get(self, key): idx self._hash(key) bucket self.buckets[idx] for k, v in bucket: if k key: return v raise KeyError(key) def _resize(self, new_capacity): old_buckets self.buckets self.capacity new_capacity self.buckets [[] for _ in range(new_capacity)] self.size 0 for bucket in old_buckets: for k, v in bucket: self.put(k, v)这个代码能工作但不适合上生产环境。为什么因为hash(key)对同一个 key 每次都重算字符串特别长时性能堪忧同时_resize是全部搬移的数据量大时有明显停顿。你理解了这两点再去看语言自带的 HashMap 实现就会明白为什么它们要加缓存、渐进式搬移了。4.3 栈与队列的相互实现栈和队列虽然规则不同但在工程上有个近乎“魔术”的事实栈可以用两个队列实现队列也可以用两个栈实现。这个结论乍一看很反直觉但原理并不复杂。用两个栈实现队列的思路是入队时把元素压入栈 A出队时如果栈 B 为空就把栈 A 的所有元素依次弹出并压入栈 B然后从栈 B 弹出栈顶。这个过程本质上是做了一次“倒序”让最先进栈 A 的元素最后变成栈 B 的栈顶实现先进先出。均摊复杂度是 O(1)因为每个元素最多被倒腾两次。反过来用两个队列实现栈的核心思路是入栈时把元素放进队 A但要保证队尾元素是“最后入栈的”出栈时直接把队尾拿出来。做法是把队 A 中除了最后一个元素之外的全部元素搬到队 B然后队 A 剩下的那个元素就是栈顶出栈后交换队 A 和队 B 的角色。这一类“用 A 结构实现 B 结构”的题目本质上是在考察你对两种结构操作特征的理解。很多人背答案背完就忘。我建议你亲手实现一遍跑几个用例你会真正理解“操作顺序”四个字的分量。5. 常见问题与排查技巧实录5.1 扩容导致的性能抖动怎么办我之前维护过一个数据接口服务平时延迟稳定在 10 毫秒以内但每过一段时间就会出现一次 200 毫秒以上的尖刺。一开始以为是垃圾回收问题后来加了监控才发现尖刺总是出现在一个动态数组扩容的瞬间。原因不复杂这个数组保存了一个业务对象的缓存列表数据量缓慢增长容量到了阈值就要扩容每次扩容要复制整个数组几万美元个对象一次拷贝就是上百毫秒。排查思路是先定位最耗时的函数再分析是不是扩容导致。解决方案有几条路子预估容量初始化时直接给一个足够大的容量避免中途扩容或者换成链式结构用链表代替动态数组牺牲随机访问换掉扩容的批量拷贝再或者做分批搬移学哈希表渐进式 rehash 的思路。这个案例启发了我一个很重要的工程经验任何“均摊 O(1)”的数据结构都必须对“单次最坏延迟”有心理预期。你要评估自己的场景到底在乎平均延迟还是最大延迟。实时系统在乎最大延迟那么动态数组的翻倍扩容就是不可接受的。离线批处理系统在乎吞吐量扩容的偶尔抖动就无所谓。5.2 哈希碰撞引发的“事故”有段时间我负责一个接口会根据一批 ID 批量查询数据内部逻辑是把 ID 作为 key 存进哈希表再把结果按 ID 顺序返回。测试环境一切正常上线后某天突然发现有几个 ID 的查询特别慢。排查发现这批 ID 的哈希值对桶数的取模结果高度集中造成大量元素挤在同一个桶里链表遍历非常长。根本原因是数据分布本来就不均匀加上桶数设计得不够合理。解决办法是两方面的一方面改进哈希函数让这些 ID 尽量分散另一方面把负载因子阈值调低提前扩容降低冲突概率。哈希表最怕的就是“分布不均匀”你要学会看监控里每个桶的长度分布而不是只看平均长度。5.3 栈溢出与队列积压的排查思路栈溢出这个问题多见于递归调用过深或者无限递归。排查时最直接的手段是看调用栈如果发现某两三个函数反复互相调用那就是写了一个没有终止条件的递归如果递归深度确实很大但逻辑正确那就得考虑把递归改成循环或者用显式栈模拟递归。我在实际项目里就把一段深度可能达到几万层的递归改成了栈加循环效果立竿见影。队列积压则是另一类问题。消息队列里堆积了大量消息消费者处理不过来。排查先看生产速率和消费速率再看有没有慢消费者阻塞比如消费逻辑里做了耗时的数据库操作把整个消费线程卡住了。还有一种隐蔽情况消费失败的消息被反复重新投递形成死信循环不断挤占队列。应对思路一般是增加消费者实例数量、优化消费逻辑、设置最大重试次数并转入死信队列。这些问题的共性是什么都要你先对数据结构的行为特征有准确预期。数组慢一下你要知道是扩容哈希慢一下你要想到冲突队列堆积你要分清是生产太快还是消费太慢。5.4 一个通用排查工具复杂度意识说了这么多最想强调的还是复杂度意识。很多线上问题不是 bug而是“数据结构选型不当”导致的问题。一个简单的判断标准如果数据量从一万涨到一百万你的接口耗时是涨一百倍还是只涨一点如果是涨一百倍且算法是 O(n²) 的那不管怎么优化代码细节都救不回来必须换结构。举个简单例子一段文本去重。用动态数组存已经出现过的单词每来一个新单词就遍历数组查找数组长度为 n 时新单词的插入操作是 O(n)总复杂度 O(n²)。一万个单词还好十万个就出问题了。换成哈希表插入和查找都是 O(1)总复杂度变成 O(n)数据量翻十倍耗时基本只翻十倍甚至更低。数据结构选对了很多事情事半功倍。6. 几条关于学习路径的实用建议最后分享几个我自己的体会不针对新手也不针对老手就看你现在想解决什么问题。第一不要死记“XX 数据结构适合 XX 场景”的对照表。动态数组不是只能按下标访问哈希表不是只能做键值缓存队列不是只能做消息队列。你要理解的是每种结构的核心操作是 O(1) 还是 O(n)内存上是连续还是离散顺序上是有序还是无序。这三个维度想清楚选型自然就对了。第二刷题没必要追求数量但把“数组、链表、哈希表、栈、队列”相关的基础题吃透非常有必要。这么做的好处是你会逐渐形成一种直觉看到问题就知道该用哪种结构打底。比如看到“嵌套”想栈看到“时序处理”想队列看到“快速查找”想哈希看到“随机访问”想动态数组。这种直觉不是背出来的是练出来的。第三生产环境里不要自己造轮子除非你真的理解轮子的全部细节。语言自带的 HashMap、队列实现经过百万级场景验证比自己写的可靠得多。但学习阶段一定要自己造一遍因为只有亲手写一次你才会知道哈希函数怎么设计、负载因子怎么选、扩容要处理哪些边界条件。自己造轮子的目的是“理解”而不是“替换”。第四多关注数据结构的“最坏情况”和“边界条件”。动态数组满容量了怎么办哈希表冲突严重了怎么办队列满元素了怎么办栈为空时出栈怎么办这些边界处理往往才是工程里最重要的部分。在线系统出问题基本都出在边界上而不是主流程上。我自己的一个习惯是每接触一个新业务场景先停下来问自己一句这里的数据是“堆积”“排队”“配对”还是“索引”堆积优先想动态数组排队优先想队列配对回溯想栈索引和去重想哈希表。这套朴素分类法帮我少写了很多冤枉代码。希望这些内容对你也有用。