标签：data structures

共 16 篇相关文章

IT 累计浏览 4,443

软件开发的硬约束

这篇讲的是作者从超市结账小票的两种打印方式出发，对软件开发中“软约束”与“硬约束”的深刻反思。作者观察到，收银小票倾向于为同一件商品打印多行记录（每行数量为1），而非合并成单行（数量为N），即使后者更省纸。起初他怀疑是设备性能所限，但通过一次收货管理系统的开发与实地部署，他发现了真正的原因：合并记录会影响仓库作业流程的效率与操作习惯——后续员工需要在纸质清单上手动划销，单件单行才最直观。这个发现让他意识到，长期从事纯软件开发时，功能、架构与责任划分往往具有灵活性（“软约束”），可以按需调整。但现实世界存在大量“硬约束”，比如设备操作习惯、生产线工艺流程、物理环境限制等。他进一步以工厂生产多语言说明书为例：生产线难以像软件模块一样灵活拆分组合，导致不得不为所有市场印刷包含所有语言的通用说明书，以避免为每种语言维护独立生产线的高昂成本。作者总结道，随着软件深入物理世界，决定其价值的往往不是复杂的技术架构，而是能否与现实约束融洽相处。开发者需要跳出纯粹的代码思维，直面问题的核心限制。文章最后以快递站利用条码替代键盘操作的巧妙案例收尾，说明了解决方案可以完全跳出技术框架，以极低成本满足场景的真实需求。

IT 累计浏览 3,422

python数组使用说明

这篇文章系统梳理了Python中三种常用的序列类型：list、Tuple和Dictionary，并详细讲解了它们各自的定义方法、核心技巧与常用API。文章首先厘清了三者的基本特性：list是动态链表，初始化后可以灵活增减元素；Tuple是固定长度的元组，一旦定义便不可更改；Dictionary则是基于键值对的哈希表，提供快速的数据检索能力。随后，作者分别深入展示了每种类型的具体用法。对于list，文章重点演示了如何通过索引切片获取或删除多个元素，如何利用enumerate高效遍历，以及append、insert、pop等关键操作方法，还特别提示了列表复制时的引用与克隆区别。Tuple部分则简明介绍了其初始化、访问以及与列表的相互转换。Dictionary章节聚焦于其丰富的内置方法，如get提供安全的键值获取、keys/values/items用于遍历、update用于合并字典等，并说明了如何为同一个键赋值多个值。这些内容的讲解都附带了清晰的代码示例，非常实用。文章最后帮助读者理解：当你需要动态调整集合内容时，list是首选；当需要确保数据不被意外修改时，可选Tuple；而当需要基于唯一标识快速查找数据时，Dictionary则最为高效。

IT 累计浏览 12,542

HashMap解决hash冲突的方法

这篇讲的是 HashMap 如何巧妙处理哈希冲突。作者直接从 put 方法的源码切入，展示了当不同 key 通过哈希算法映射到同一个数组索引（即“桶”）时，HashMap 采用的“链表法”解决方案。核心思路很清晰：当发生冲突时，新的键值对并不会替换旧的，而是像插入单链表一样，通过 `addEntry` 方法被添加到该桶的链表头部。文章特别指出，这个新插入的 Entry 对象会指向原先位于该桶的 Entry，从而形成一条单向链表。这就解释了为什么在冲突严重时，get 操作会从直接定位退化为需要遍历链表，最坏情况下复杂度会达到 O(n)。文章还点出了一个关键的设计权衡——负载因子。默认的 0.75 是空间与查询效率之间的折中：过大会节省内存但查询变慢，过小则查询更快但更耗内存。总的来说，这篇分析没有停留在概念层面，而是通过源码把链表如何形成、负载因子如何影响性能这些细节讲透了，适合想弄懂 Java 集合框架底层原理的开发者阅读。

IT 累计浏览 2,141

数据映射–映射概述

作者从“映射”这一计算机基础数据结构出发，梳理了从CPU到文件系统无处不在的映射关系。文章首先明确了映射的数学定义，并列举了它在查找文件、网络数据、数据库记录等场景中的关键作用。接着，作者用一组简单对应（如2->4, 1->2）作为示例，对比了三种实现映射的方式：使用集合（如数组）存储键值对、定义一个数学函数、以及编写穷举算法。文章指出，后两种方式因需理解数据规律或硬编码而适用性有限，从而将讨论聚焦于更通用的集合类数据结构。为了优化最基础的数组线性遍历效率低下的问题，文章深入介绍了两种核心的查找算法：要求数据有序的二分查找（时间复杂度O(log₂N)），以及利用哈希函数实现近乎O(1)效率的哈希查找。作者以哈希查找为例，解释了如何通过键值计算快速定位，并详细说明了“哈希碰撞”问题及使用链表解决的常见方法。最后，文章总结道，不同的应用场景（如是否需要范围查询、自动扩展、磁盘存储或并行处理）将决定对映射集合的具体技术选择，而这些底层选择正是各类数据库性能差异的根源。

IT 累计浏览 13,162

Linus：利用二级指针删除单向链表

这篇讲的是Linus Torvalds如何用二级指针来优雅地删除单向链表节点。文章从Linus在slashdot上对一段“标准”代码的批评切入，他直言那种需要维护`prev`指针并判断是否为表头的写法，表明作者“不懂指针”。核心对比了两种实现思路。传统写法（很多教科书和面试题的标准答案）需要额外维护一个`prev`指针，并在删除时判断当前节点是否为链表头，代码中存在条件分支。而Linus推崇的“core low-level coding”技巧，是直接使用一个指向节点指针的指针（即二级指针`node** curr`）来遍历和操作链表。其精妙之处在于，无论要删除的是表头还是中间节点，都可以通过统一的`*curr = entry->next`操作完成，无需任何条件判断。文章通过逐行代码解析和示意图，阐明了这种写法如何将“前驱指针”的概念融入到对`next`指针本身的间接操作中，最终生成更清晰、更可能被编译器优化出高效指令的代码。这种对指针的深刻理解和运用，体现了Linus所看重的注重细节、追求高效底层编码的审美。

IT 累计浏览 5,181

Tips of Linux C programming

这篇文章分享了Linux内核和GNU C中一些不那么为人所知却非常实用的编程技巧。作者从链表的非常规定义讲起，展示了如何将链表节点嵌入到数据结构中，并利用`container_of`宏从节点地址反推出宿主结构体，这种方法比传统教科书定义更灵活优雅。随后，文章深入到编译器与硬件层面：介绍了用`likely`/`unlikely`宏提示编译器优化分支预测，减少流水线冲刷；演示了通过内联汇编和`lock`指令前缀实现原子加法，保证多处理器环境下的数据一致性；还探讨了GNU C特有的零长度数组特性，用于在运行时动态分配结构体尾部的变长数组。最后，简短提到了三目运算符`a = x ? : y`这种简洁的省略写法。这些技巧都源自真实的内核开发或GCC特性，能帮助C程序员写出更高效、更地道的代码。文章穿插了关键的代码片段和原理剖析，对希望提升底层编程技巧的读者很有启发。

IT 累计浏览 2,401

多核环境下cache line的测试

这篇讲的是作者从一个关于数组内部链表的内存池技术题目出发，对CPU cache，特别是cache line，进行的探索和测试。文章首先点明了这种数据结构的优势——通过保持地址连续来提升缓存命中率，非常直观。作者指出，对程序员来说，CPU高速缓存本是一个透明部件，我们通常无法直接干预其操作。但正因了解其工作特点，我们可以通过特定的代码优化，让程序更好地利用它。文章的核心价值在于，作者并未止步于理论。他深入到多核环境下，对cache line进行了实际的测试与分析。这为理解在复杂硬件场景下，数据如何影响缓存行为提供了第一手的观察。通过这次从实际问题到硬件原理的挖掘，作者将抽象的缓存概念落地，展示了如何从日常编程细节中洞察底层性能的关键。

IT 累计浏览 2,240

关于hashcode 里面使用31 系数的问题

这篇从Java源码中常见的“乘以31”现象切入，详细探讨了为什么在实现hashCode方法时，开发者普遍选择31这个特定系数。作者没有停留在“它是质数”的简单结论上，而是深入剖析了31在计算机二进制表示下的独特优势：它不仅是质数，能减少哈希冲突，更关键的是31 * i 可以被编译器优化为 (i << 5) - i 的位运算操作，在保证分布均匀的同时，显著提升了计算效率。文章进一步对比了其他可能的质数（如17、33），用数据和理论说明了31在“性能”与“冲突概率”之间取得的绝佳平衡点。通过阅读String类等核心库的hashCode实现，我们可以看到这个设计选择背后的工程智慧。对于想深入理解哈希表底层优化的开发者来说，这篇文章提供了一个非常扎实的微观视角。

IT 累计浏览 3,583

浅析Linux Kernel中的那些链表

这篇讲的是Linux内核中链表的实现。作者从内核开发者最熟悉的链表结构切入，指出它与数据结构教材中的标准链表有着本质区别。文章的核心在于剖析内核链表的巧妙设计。它并非传统意义上“节点包含数据”，而是采用侵入式设计：链表节点（`list_head`）被嵌入到你想要管理的数据结构本身中。这样，一套通用的链表操作代码就能管理任意类型的数据，无需为每种数据重写实现。作者详细对比了侵入式链表与非侵入式链表的差异。传统链表需要为数据分配单独的节点内存，而内核链表将节点与数据合为一体，在内存管理上更为高效和灵活。这种设计使得通过一个数据结构中的链表节点，可以反向定位到包含它的整个结构体，这是理解后续很多内核数据结构（如进程队列）的关键。文章最后可能总结，这种设计牺牲了一点点直观性，但换来了极大的通用性、性能和内存效率，是内核编程中“空间与时间”、“通用与专用”权衡的经典范例。对于想深入理解内核源码的开发者来说，厘清这个基础结构至关重要。

IT 累计浏览 3,983

开源世界中的算法与数据结构 3 -- Linux Kernel List 和GList

这篇讲的是 Linux 内核和 GLib 中两种经典链表实现的设计哲学与实践权衡。作者没有纠缠于基本的增删操作，而是从工程实现的底层逻辑出发，对比了它们的差异。核心差异在于内存模型：Linux 内核链表是侵入式的，它不另立节点存储数据，而是将 `list_head` 结构体直接“嵌”到你的数据结构里，通过 `container_of` 宏从节点反推出宿主对象。这带来了极致的内存效率和访问速度，节点与宿主数据一体，缓存友好。但代价是链表节点不能脱离宿主数据独立存在。相反，GLib 的 `GList` 是通用的、非侵入式的。每个节点都是独立的内存块，通过 `prev` 和 `next` 指针串联，节点里用一个 `gpointer data` 指向实际数据。这带来了灵活性——节点可以被多个链表共享，生命周期也容易管理。但每一次插入、删除或访问数据，都需要额外的指针解引用，在性能敏感的内核路径上可能无法接受。文章正是通过这两种截然不同的设计，揭示了在“通用性/灵活性”与“高性能/低开销”之间做选择时的典型工程考量。读完能理解，为何没有完美的链表，只有最适合特定场景的实现。

IT 累计浏览 2,980

多核环境下编写程序需注意Cache

这篇讲的是作者从一道关于数组内部链表（常见于内存池）的编程题出发，发现这种连续地址的数据结构比普通链表更易于命中CPU Cache，从而展开对Cache的研究与分享。文章首先为读者普及了CPU高速缓存（Cache）的基础知识。在程序员的视角中，Cache通常是一个透明的硬件部件，我们无法直接对其进行干预操作。但这并不意味着我们无事可做。关键恰恰在于理解Cache的“透明性”背后所隐藏的工作机制——它会根据程序访问数据的局部性原理，自动缓存最近或频繁使用的数据。因此，虽然我们不能“控制”Cache，却可以通过编写对Cache友好的代码来主动“利用”它的这一特点。作者正是基于这个核心思路，去探索如何通过代码优化来提升程序在多核环境下的性能表现。

IT 累计浏览 3,742

Redis中7种集合类型应用场景

这篇讲的是Redis七种核心集合类型各自的“主战场”。作者从实际业务需求出发，没有停留在命令语法的层面，而是深入对比了String、List、Set、Hash、ZSet、HyperLogLog和Bitmap这七种结构在底层设计上的关键差异。比如，它明确指出了Set的“唯一性”特征如何天然适合实现标签系统和社交关系交集；而ZSet的有序性与评分机制，则是构建实时排行榜和延迟队列的绝佳选择。文章还特别提到了Bitmap在处理用户签到、在线状态等海量二值统计场景时，如何用极低的内存开销完成高效计算。这种从“数据结构特性”推导至“典型业务场景”的讲述方式，让读者能清晰地看到Redis并非一个简单的键值库，而是一个针对不同数据模式提供了高度优化解决方案的工具集。当你面临一个具体的数据存储或计算问题时，这篇文章能帮你快速定位到最合适的数据结构，做出更优雅高效的技术选型。

IT 累计浏览 4,362

Redis源代码分析

这篇讲的是作者兑现承诺，从文件结构入手深度剖析Redis服务端源代码的硬核文章。作者没有直接钻进某段代码，而是先从宏观视角把Redis服务端所有源码文件铺开，逐一厘清它们各自承担的职责。这种从架构布局切入的写法，能让读者先建立起清晰的“地图”，再跟着作者深入实现细节。 Redis以高性能著称，其单线程模型、高效的网络协议处理与内存数据结构是关键。文章将带领读者跟随代码，看Redis如何巧妙地将事件驱动、非阻塞I/O等机制编织在一起，从而在单线程内实现高并发的命令处理。作者对每个文件核心逻辑的解读，旨在揭示Redis在工程实现上的精巧与克制，比如其简洁的协议解析和极致优化的内存管理。对于想超越表面使用、一窥Redis内部运作奥秘的开发者来说，这份逐文件的源码导读提供了一个扎实的起点。

IT 累计浏览 3,040

mysql innodb 文件相关的三个重要结构体

这篇讲的是 MySQL InnoDB 引擎里三个关键的物理结构体——数据页、undo日志页和插入缓冲页。它们虽然都以 16KB 的统一页面格式存储在磁盘文件中，但头部的二进制结构和核心职责却大不相同。作者从 InnoDB 最小的磁盘 I/O 单位“页”出发，拆解了它们的设计。数据页是存储行数据的“仓库货架”，页头详细记录了校验和、记录数、空闲指针等元信息。undo日志页则像“事务的草稿纸”，专门存放数据被修改前的版本，为回滚和 MVCC 服务。而插入缓冲页是一个临时“集结点”，负责批量合并多个非唯一二级索引的插入操作，以减少随机 I/O。这三个结构体的区分设计很巧妙：它们共享了通用的页面框架（如校验和、页类型标识），但在头部结构和数据区布局上各司其职。理解这种“同形不同职”的差异，能让我们更清晰地看到 InnoDB 如何在统一的文件架构下，高效地兼顾了数据存储、事务一致性和索引写入性能。这为深入理解数据库底层如何运作提供了很好的视角。

IT 累计浏览 7,600

Redis作者谈Redis应用场景

这篇来自Redis作者的技术分享，没有停留在Redis的通用介绍，而是直接从实践出发，细数了那些真正“用对了”的场景。作者指出，Redis并非万能钥匙，它的高性能源于内存操作和单线程模型，因此最适合解决那些“读写极快、数据结构匹配”的特定问题。文中列举了几个典型用例：作为高速缓存加速数据库查询；利用Sorted Set实现实时排行榜；借助Pub/Sub构建轻量级消息系统；以及使用HyperLogLog进行基数统计。这些都是Redis“数据结构即服务”理念的完美体现。但更关键的是，作者强调了“避坑”指南。例如，当数据量远超内存、需要复杂查询或强事务保证时，关系型数据库仍是更稳妥的选择。这种对适用边界的清醒认知，恰恰是许多技术团队在选型时最需要的视角。文章帮助读者建立了一个清晰的心智模型：不是Redis能做什么，而是在什么场景下，它才是那个最优解。

IT 累计浏览 3,281

算法收集

这篇讲的是经典的插入排序算法。作者从最核心的思想切入：当我们遍历序列时，前面的N-1个元素可以假定已经排序完成。此时的任务，就是为当前第N个元素在前面已排好的部分中找到一个合适位置插入，使之仍然保持有序。这个过程重复进行，直到遍历完整个序列。算法的执行效率可以很直观地计算出来。处理第1个元素无需比较，处理第2个最多比较1次，第3个最多2次……依此类推，总的比较次数上限是1 + 2 + 3 + … + (N-1)，因此其时间复杂度为O(N²)。这是一个非常直接且易于理解的复杂度分析。尽管复杂度较高，插入排序在特定场景下依然非常实用。例如，当数据量很小，或者数据本身已经基本有序时，它的表现会接近线性时间，非常高效。此外，它是一种稳定的排序算法，且在原数组上操作，空间复杂度为常数。这些特性让它在处理小型或近乎有序的数据集时，成为一个简单、可靠的选择。