标签：数据结构

共 69 篇相关文章

IT 累计浏览 8,067

Redis和Memcached的区别

这篇讲的是Redis和Memcached这两种内存数据库的核心区别。文章从Redis作者的一个经典比较出发，清晰梳理了三者关键差异：首先，Redis支持String、Hash、List等更丰富的数据结构，可以在服务器端直接进行复杂操作，避免了Memcached需要将数据取回客户端修改的额外开销。其次，在内存效率上，若采用hash结构存储，Redis的组合压缩机制可能比Memcached更具优势。最后，性能表现各有特点：处理小数据时Redis的单核性能更优，而在100k以上的大数据场景中，Memcached的多核处理能力则略占上风。文章随后深入剖析了Redis五种数据类型的实现原理，例如Hash内部如何根据成员数量自动转换存储结构，以及Set如何通过HashMap实现快速去重。这些细节不仅解释了差异背后的技术原因，也揭示了各自的设计考量。总的来说，如果你的应用需要丰富的数据结构和复杂操作，Redis是更强大的选择；而如果是纯粹的、简单的大规模键值缓存，Memcached在内存利用和特定数据量级下的性能或许更合适。文章为技术选型提供了扎实的对比依据。

IT 累计浏览 2,097

深入剖析 redis 数据结构 redisObject

这篇讲的是Redis核心数据结构redisObject的设计。它只有32位，却极其高效地管理了所有类型的数据对象。作者从结构体定义出发，揭示了它的精巧布局：type字段明确是字符串、列表还是哈希等类型；encoding字段则决定了底层是用普通字符串、压缩列表还是跳表来存储——同一个类型的数据可以有多种编码，Redis会根据数据规模自动选择最省内存的方案。比如一个小的集合可能用整数集合，变大了就切换为哈希表。文章还详解了lru字段如何用于内存淘汰，以及refcount引用计数如何管理对象生命周期。最后那个void *ptr指针，才是真正指向数据的地方。作者特别指出，得益于Redis单线程模型，引用计数的操作无需考虑线程安全，这是与Memcached等多线程系统的重要区别。整个设计将数据与元数据分离，各个字段职责清晰，正是Redis高效与灵活的重要基石。

IT 累计浏览 4,268

校招经验——写给找工作的同学们

这篇文章里，一位招聘官分享了自己在北大、武大两场校招中，连续三天面试百余名同学后的直观观察。他指出，不少同学能力不错，却在一些关键环节“可惜”地折戟，问题往往出在准备与认知上。作者将校招流程拆解为笔试、群面和一对一面试，并点出了每个环节的核心考察点。比如，笔试主观题的关键不是解题，而是先“定义问题”，认清出题人设的“局”；群面中，许多人执着于抢“主持”角色，却忽略了面试官在观察团队协作与人岗匹配，扮演好适合自己性格的贡献者同样重要。尤其值得注意的是，他对比了京汉两地同学在知识面（如对团购业务理解深度）上的差异，并强调了环境不能成为借口，主动通过阅读拓宽见识是可行的。这些基于实战的细节建议，都指向一个核心：求职不仅是技巧比拼，更是对个人视野、应变能力和自我认知的一次综合检验。

IT 累计浏览 4,980

面试总结［2014.06］

最近，一位工作7年的程序员分享了他密集面试百度、阿里、小米、美团、雅虎等多家公司的详细总结与思考。文章从一次略带遗憾的求职经历切入，深入剖析了国内技术面试的几个核心考察维度。作者对面试环节的观察颇为犀利。他认为，当前面试对“编码能力”的实际考察不足，而对“算法”考察的侧重点（如是否追求标准答案）值得商榷。在“概念知识”与“项目经验”环节，他指出面试容易陷入“你知不知道”和“销售能力”的比拼，而非真正评估解决问题的能力。相比之下，雅虎面试新技术广度，阿里考察底层深度，小米采用类似谷歌的“基础能力优先”招聘风格，都给他留下了较好印象。文章不仅分享了各家公司的面试风格差异与薪酬职级对比，更抛出了一个核心观点：面试官如何设计问题，才能公平且有效地甄别出候选人的真实能力与潜力？作者对面试体系的反思，或许能为同行带来一些启发。

IT 累计浏览 1,040

文明上网，普及科学，传播价值

针对VPN连接不稳、频繁断开影响技术工作的痛点，作者从自身实践出发，分享了一套基于GRE隧道和策略路由的自建“科学上网”方案。核心思路是在国内服务器与海外服务器之间建立一条稳定的GRE隧道，并通过`iproute`策略路由，实现国内流量直接从国内网关出去、国际流量则经隧道从海外出去，从而在保障访问Google等资源速度的同时，避免了所有流量绕行海外的低效问题。文章详细列出了从建立隧道、配置双向路由规则、通过APNIC数据自动生成中国IP路由表，到设置NAT和调整MTU以确保稳定的完整操作步骤。这套方案相比依赖第三方VPN，显著提升了连接的可靠性和上网速度，为有类似需求的读者提供了一套思路清晰、可落地的实现参考。

IT 累计浏览 2,537

redis 数据结构综述

这篇讲的是 Redis 存储键值对的核心底层数据结构，从源码层面剖析了其设计与巧妙的权衡。文章从全局视角出发，逐一介绍了 dict 哈希表、可变类型的 redisObject、高效插入删除的 zset（跳表+哈希表组合）、经典的 adlist 双链表，以及为优化 CPU 缓存和内存而生的压缩列表 ziplist 和整数集合 intset 等关键结构。不止于理论，作者更将这些结构与具体的 Redis 命令联系起来，清晰地展现了不同场景下的选择逻辑。比如，SET 命令对应最简单的 sds 或数值类型；HSET 和 LPUSH 在特定条件下会使用紧凑的 ziplist 而非链表；SADD 会根据元素是否全为整数，在 intset 和 dict 之间动态切换；而 ZADD 有序集合则综合运用了 skiplist 和 dict，或采用 ziplist，具体取决于配置阈值。这种从底层实现到命令行为的串联分析，揭示了 Redis 在性能与内存之间精妙平衡的设计哲学。作者提到这只是系列开篇，后续将逐一深挖每个结构，值得对 Redis 内部机制感兴趣的技术人持续关注。

IT 累计浏览 11,559

加州求职记

这篇讲的是一位国内互联网工程师放弃稳定工作，决心通过H1B签证赴美求职，最终却在Google、Amazon、Facebook三家巨头的面试中折戟的全过程复盘。作者在百度工作四年多，曾带过技术团队并出版译作，离职时信心十足。然而，他很快发现，湾区科技公司的面试核心是扎实的编码能力，要求写出可直接运行的零Bug代码。他坦承自己算法基础薄弱，并非ACM科班出身，最大的失误在于因自满而没有尽早研究目标公司的面试特点，也未及时用最有效的方法弥补短板。文中详细对比了CareerCup、ZOJ、TopCoder、LeetCode等平台的优劣，指出LeetCode结合了真题与在线评判系统的优点，其难度与实际面试最为接近，是他后期最有效的训练工具。在英语沟通方面，他也分享了通过“自言自语”进行模拟技术讲解的独特练习法。尽管最终未能成功，但这段经历涵盖了首次英语面试、办理签证等多个“第一次”。作者以诚恳的态度记录下从盲目自信到反思自身不足的心路历程，为同样计划“肉身翻墙”的同行者提供了一份极具参考价值的实战教训与准备路线图。

IT 累计浏览 6,692

技术人员如何去面试？

这篇讲的是跳槽季里，技术人员从决策到拿offer的全流程经验。作者从实际问题出发，拆解了跳槽动机分析、目标公司选择（大厂平台 vs. 潜力公司）、以及内推/猎头/海投等渠道的优先级。面试部分尤其详实。作者指出流程旨在规避主观偏见，但仍需做好应对准备：针对性技术复习、保持干净得体的外在、注意面试时的空间距离与座位角度（推荐L角）。沟通上建议语气平稳、逻辑清晰。他具体区分了技术面试中“封闭式”与“开放式”问题的应对策略——前者精准作答，后者可先追问明确方向再分层阐述。对于“离职原因”等敏感问题，则建议客观陈述，避免抱怨。谈薪环节被单独强调，作者提醒要了解行业浮动惯例（通常涨幅在20%-30%），并基于自身预期和市场行情谨慎沟通，避免因狮子大开口或过于被动而受损。全文是作者作为程序员的切身观察与总结，跳出了具体技术语言，为不同阶段的技术人提供了从简历投递到薪酬谈判的实用指南。

IT 累计浏览 6,895

数据结构定义中的中(大陆地区)美差异

这篇讲的是一个挺有意思的技术概念“撞车”现象：作者在和一位清华博士讨论数据结构的选择题时，发现自己按国内教材理解的答案和标准答案大相径庭。一查权威资料才发现，原来“满二叉树”、“完全二叉树”这些基本概念，中国大陆教材的定义和美国及国际通行定义存在系统性差异。文章核心对比了三个概念。最典型的是“满二叉树”：国内严蔚敏版教材定义为“深度为k且有2^k-1个节点的二叉树”，即每一层都完全填满；而美国NIST的定义（对应full binary tree）则是“每个节点要么是叶子，要么有两个孩子”。两者描述的结构截然不同。对于“完全二叉树”，中美定义在“最后一层节点尽可能靠左”这一点上达成了一致。另外，美国定义中的“perfect binary tree”实际上就是国内教材所说的满二叉树，只是国内很少单独提出这个术语。作者借此指出，国内考研、等级考试广泛采用的定义与国际标准存在偏差，建议读者在学习数据结构时，多参考英文原版教材以避免概念混淆。

IT 累计浏览 2,696

关于大区间过滤优化内存设计

这篇讲的是在检索场景下，如何优化“大区间过滤”时的内存结构设计。作者指出，传统做法中以 docId 为下标存储域值的方式存在内存浪费，尤其在域值（如日期类型）重复率很高的场景下。核心方案是引入两个互补的数组：第一个数组以域 Term 的遍历位置（Position）为下标，直接存储对应的域值，这利用了域值在遍历过程中天然有序的特点；第二个数组则以 docId 为下标，存储该文档在第一个数组中的对应位置。这样一来，大量重复的域值（例如“20101202”）在第一个数组中只存储一次，通过第二个数组的间接映射，就能为每个 docId 快速定位到其域值。作者通过示意图和实际业务分析说明，对于时间这类重复率极高的域，该设计能显著压缩内存占用。整个方案的精髓在于通过空间换时间的思想，巧妙地将高重复的域值“去重”存储，并用一次额外的间接查找换取整体内存效率的提升。

IT 累计浏览 6,585

爱喝啤酒的程序员是如何学习数据结构的

这篇文章从程序员形象的演变切入，探讨了一种颇具创意的数据结构学习方式。背景是传统程序员常被贴上木讷、逻辑化的标签，但随着“Brogrammer”文化的兴起，喝酒、听摇滚等生活元素逐渐融入编程世界。作者通过一系列啤酒杯排列的图片，生动展示了如何用日常物品来可视化抽象的数据结构概念。具体来说，文章用啤酒杯模拟了二叉树的层级分支、不平衡树的偏斜状态、重新平衡树的调整过程，以及数组、矩阵、链接表、稀疏矩阵、堆和栈等结构。例如，数组用一排整齐的杯子表示线性存储，矩阵则通过网格状的杯子排列展现二维特性。这种方法不仅幽默风趣，还巧妙地将复杂逻辑转化为直观图像，帮助记忆和理解。核心观点在于，技术学习不必局限于刻板形式，可以结合个人兴趣如啤酒，用视觉化和生活化的方式降低门槛。文章启发读者尝试更灵活的学习路径，将日常元素转化为工具，让枯燥的知识点变得生动可感。

IT 累计浏览 3,638

N叉树和人性光辉

这篇讲的是产品设计与技术协作中的思维困境。作者从一个关于裁员的梦聊起，犀利地指出了互联网行业职位过度细分带来的问题：当每个人都只埋头于自己的一亩三分地，用专业术语互相“踢皮球”时，产品的整体逻辑就碎了一地。他观察到，真正靠谱的项目，反而需要对前后环节了如指掌的通才来润滑。无论是做交互的、写代码的，还是做运营的，如果只盯着自己眼前那张图、那行代码或那个活动，而没有把整个产品“在脑海里串成一个完整的使用流程”，配合起来就会漏洞百出。文章的核心观点落在“总-分-总”的必然趋势上，并提出了一个具体的思维框架：用“N叉树”的结构来构建产品逻辑。作者强调，好的设计应该拥有清晰的单线逻辑、功能无交叉的叶子节点，以及一致的视觉与交互，这样才能让用户快速学习并形成记忆。这实际上是对产品整体架构能力的呼唤，批判了那种流程细分却缺乏全局视角的“混日子”体制。对于技术人来说，这提醒我们不能只做执行的“螺丝钉”，而要培养贯通需求、设计与实现的系统化思维。

IT 累计浏览 10,518

基于Redis构建系统的经验和教训

这篇文章从实际应用出发，讨论了Redis的优势与局限，并对比了其他海量数据存储方案。作者指出，Redis的有序集合（zset）等丰富数据结构使其在表达业务逻辑时极为高效，特别适合对性能要求高、数据规模可控的场景，比如消息传递系统的收发件箱。然而，Redis“所有数据必须存放在内存中”的核心设计，直接导致了容量瓶颈和高昂的硬件成本。作者通过计算说明，对于一个百万级用户系统，数据量轻松超过单机内存极限。由此还引发了一系列问题：持久化时fork进程占用双倍内存，Aof日志写盘可能阻塞系统，以及不成熟的主从复制可能因网络抖动产生全量同步，严重消耗带宽。单机架构也迫使开发者在业务逻辑之外，必须额外设计复杂的数据分片方案。面对海量数据，文章对比了Cassandra、HBase和MongoDB等方案。作者认为纯键值存储（如Cassandra）对结构化数据的表达能力太弱；而像HBase这类系统，其数据模型提供了更有序的组织方式。文章最终提出的观点是：理想的存储方案应当提供基础的有序数据结构，允许开发者通过“实体”加“有序子集”的方式来自然映射业务逻辑，从而在海量数据规模下，实现高效的数据访问与传输。因此，Redis应定位在小而美的高性能缓存或结构化存储层，而非追求海量数据的存储目标。

IT 累计浏览 4,345

有关面试

这篇讲的是作者作为技术面试官，在近期一系列高强度的招聘面试后，沉淀下来的第一手观察与思考。他没有空谈理论，而是直接从面试现场的细节入手，探讨了几个关键问题：面试的本质究竟是“技术考核”还是“潜力探测”？作为面试官，如何避免陷入仅凭“手速”和“标准答案”来评判候选人的误区？在有限的时间里，是该深挖一个知识点来考察思维深度，还是广泛覆盖以评估知识广度？文章将面试形容为一场双向的信息对称博弈。作者特别指出了一个常见盲区：我们往往过度关注候选人“答对了什么”，却忽略了观察他“如何面对不知道的问题”以及“提问时展现了怎样的思考路径”。这些细节，往往比背诵八股文更能揭示一个人的技术素养和成长潜力。对于正在准备技术面试的候选人，或是同样承担面试职责的技术人员，这篇文章提供了一个跳出常规题库的视角，去重新审视面试中那些容易被量化的标准所掩盖的、更重要的人的维度。

IT 累计浏览 3,564

我看面试时出（纯）算法题

作者读到左耳朵耗子关于反对纯算法面试题的新文章后，结合自身经验写下了回应。他认同面试不应只考察与实际工作脱节的纯算法题这一大方向，但也希望为这个讨论补上一些更细腻的视角。文章首先温和地指出，原文对学术研究者的描述略有偏颇，但这不是重点。真正的核心在于，如何更准确地通过面试问题，来评估一个候选人在实际工程中解决问题的能力。作者认为，纯粹的算法题容易忽略工程实践中的权衡、沟通与协作，而一个更有效的面试环节，或许应当模拟真实场景，考察候选人分析需求、拆解问题、并在约束条件下做出合理技术选择的能力。这篇短文像是一个冷静的“补丁”，将一场热门的技术讨论引向了更具体的实践层面，提醒我们在设计面试时，别忘了技术能力最终是为解决真实业务问题服务的。

IT 累计浏览 3,314

树与存储

这篇讲的是数据结构中最基础也最重要的“二叉树”概念。作者开篇就抓住了核心：二叉树的精髓在于“二分”，即每个节点最多拥有两个子节点的规则，由此衍生出满二叉树、完全二叉树等多种形态，是理解更复杂树结构的基础。文章接着深入到计算机如何实际存储这棵树。关键对比在于两种经典方案：顺序存储和链式存储。顺序存储利用数组，逻辑上相邻的节点在物理内存中也连续，通过特定索引关系（如左孩子为2i+1，右孩子为2i+2）快速定位，适合完全二叉树这类结构紧凑的场景。而链式存储则更灵活，通过指针将分散在内存中的节点连接起来，能高效处理非完全二叉树或动态变化的树结构，是实际编程中最常用的方式。这种存储方式的选择直接决定了后续遍历、查找等操作的效率和实现复杂度。文章通过对两种方式的剖析，清晰地揭示了抽象数据结构与具体计算机存储之间的映射关系，为读者后续学习二叉搜索树、堆等高级结构打下了扎实的基础。

IT 累计浏览 2,579

Apache基础数据结构(tables)代码浅析

这篇讲的是Apache HTTP Server（httpd）中一个基础且关键的数据结构——`tables`。在众多轻量级Web服务器涌现的今天，这篇分析直接深入到这位“老兵”最核心的C语言源码之中。作者从`tables`如何存储和管理键值对（如HTTP头、环境变量）入手，剖析了其内部实现。文章不仅展示了它用数组和哈希表结合的灵活内存布局，还特别点出了其内存预分配、按需增长的“惰性”策略，以及在查找、插入、迭代操作上如何权衡性能与内存占用。这些看似朴素的设计，在并发处理海量请求时，恰恰是高效且稳定的基石。对于想理解高性能C项目如何设计基础组件、或对Apache内部机制感兴趣的读者，这篇文章提供了一个很好的微观窗口，其思路对优化其他C语言项目的数据容器也有借鉴意义。

IT 累计浏览 4,175

开源世界中的算法与数据结构 2 -- Linux Skbuff实现

这篇讲的是Linux内核网络栈中至关重要的数据结构 `skbuff`（套接字缓冲区）。作者从2003年接触Linux协议栈的亲身经历谈起，那时参考资料匮乏，很多理解都是自己摸索的。他提到了一本关键参考书——2008年出版的《TCP/IP Architecture, Design and Implementation in Linux》，书中第五章对 `skbuff` 的代码实现有非常详细的解析。不过，作者并非简单翻译这一章，而是希望基于这些关键代码片段，分享自己对其背后设计思想的理解。摘要着重于源码分析类文章的核心：它探讨了 `skbuff` 这个管理网络数据包在内核中流转的核心结构是如何被设计和实现的。文章的价值在于，它不仅仅罗列代码，而是结合作者长期的实践经验和经典的参考书籍，去剖析 `skbuff` 这样一个关键数据结构的设计取舍与巧思。对于想深入理解Linux网络子系统工作原理的开发者而言，这是一个从资深工程师视角切入的深度解读。

IT 累计浏览 3,601

开源世界中的算法与数据结构 1 -- Linux FIB实现

这篇讲的是作者对Linux 2.4版本中FIB（转发信息库）数据结构的回顾与剖析

IT 累计浏览 6,009

聚焦爬虫：定向抓取系统的实现方法

这篇讲的是聚焦爬虫与传统网络爬虫在工作流程上的核心区别，以及实现定向抓取系统的具体方法。文章首先梳理了传统爬虫的基本工作模式：从种子URL出发，抓取页面并不断发现新链接放入队列，直到满足停止条件。但这种“广撒网”式的抓取效率低下，且会下载大量无关内容。聚焦爬虫的实现，正是为了解决这个问题——它需要根据一个明确的主题来优化抓取过程。其核心在于加入了一套智能的“决策系统”。在抓取每个页面后，聚焦爬虫会运行网页分析算法，评估页面中的链接与主题的相关性，从而过滤掉无关链接，只将有价值的链接放入待抓取队列。同时，它采用特定的搜索策略，从队列中优先选择最可能包含目标内容的URL进行下一步抓取。文章还提到，所有抓取的内容都会被存储、分析并建立索引，而对聚焦爬虫而言，这些分析结果会形成反馈，反过来指导下一轮的抓取，形成一个闭环。简单来说，如果传统爬虫是无差别地覆盖互联网，那么聚焦爬虫就是一位有目的的“侦察兵”，它让爬虫系统能够高效、精准地服务于特定领域的垂直搜索或数据挖掘任务。