标签：Hash Table

共 10 篇相关文章

IT 累计浏览 1,828

对象到数字 ID 的映射

这篇讲的是如何用一个高效的数据结构，为对象分配并管理短生命周期的数字 ID。在像 skynet 这样的并行系统中，直接使用 C 指针来标识服务对象是危险的，容易引发悬垂指针、误释放等问题。因此，通常会用数字 ID 来间接引用。作者提出了一个具体的需求：既要快速映射，又希望尽量不复用已释放的 ID（避免误用），这与操作系统常见的文件句柄复用策略不同。为了满足这个需求，核心方案是设计一张专门的哈希表。每次分配新 ID 时，在上次值的基础上递增，并检查哈希表中对应位置是否冲突，若冲突则继续递增。这保证了 key 永不冲突，让查询速度最快，且实现相对简洁。更进一步，作者将这部分实现从 skynet 中抽离出来，做成了一个独立的开源库。文章详细介绍了其提供的 5 个 API（创建、销毁、分配、抓取、释放），并重点说明了为实现线程安全而采用的读写锁策略：对表的修改加写锁，而对 ID 的抓取和释放操作则加读锁，允许并发。这份实现还适配了 Windows 的原子操作。整体上，这是一个解决特定工程问题的精巧数据结构，其实现思路（如不复用 ID 的哈希策略、引用计数与读写锁结合）对需要管理对象生命周期的系统设计很有参考价值。

IT 累计浏览 2,191

数据映射–映射概述

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

IT 累计浏览 2,450

用词典查找代替VLOOKUP

这篇讲的是用Excel内置的词典函数（如XLOOKUP）来替代经典的VLOOKUP，核心出发点是追求更简洁、更可靠的公式体验。作者从一个常见痛点切入：VLOOKUP在实际使用中经常因插入列、模糊匹配等问题需要复杂的辅助列或嵌套函数。而新推出的词典查找类函数，比如XLOOKUP，直接支持向左查找、多条件匹配，并且默认精确匹配，大幅简化了公式逻辑。文章对比了两者的典型使用场景：VLOOKUP适合对已有简单表格进行快速列查找，但在数据结构可能变动的分析模型中显得笨拙；词典查找函数则更灵活健壮，尤其适合需要动态引用、反向查找或处理多行多列结果的场景。通过几个实际用例的对比，可以看出后者不仅减少了公式的出错率，还显著提升了可读性和维护效率。总的来说，对于尚未接触过新函数的Excel用户，这篇文章提供了一个非常实际的升级路径——无需引入Python等外部工具，仅通过学习并应用Excel自身的进化功能，就能让日常数据处理工作变得更轻巧、更直接。

IT 累计浏览 5,029

PHP哈希表碰撞攻击原理

这篇深度技术解析揭开了PHP数组底层实现中一个曾引发广泛拒绝服务攻击的漏洞原理。它从Zend引擎的源码出发，详细拆解了PHP中名为HashTable的数据结构。核心发现是，PHP为了追求极致效率，使用了极其简单的哈希算法（整数key直接按位与nTableMask，字符串key则通过Times33转换后按位与）。碰撞的数据通过单链表解决。文章的关键在于将原理与攻击结合。攻击者可以精心构造一系列数据，让它们经过这套简单算法计算后，全部落入同一个哈希桶，迫使原本高效的O(1)查找退化为O(N)的链表遍历。这直接导致CPU资源被海量比较操作耗尽，服务器无法响应正常请求。作者通过展示nTableMask的二进制规律和构造攻击数据的具体例子，清晰地演示了如何利用算法弱点实现这种碰撞。文章的启示在于，它揭示了系统底层设计中效率与安全性之间的经典权衡。许多语言的哈希实现因追求简单快速而为这类攻击埋下伏笔，后续各大语言的紧急修复也印证了其影响的广泛性。

IT 累计浏览 5,194

Memcached内存管理机制浅析

作者从 Memcached 源码入手，深入剖析了其内存管理的核心机制——Slab Allocation。不同于简单介绍，文章直接切入 Memcached 为解决内存碎片化问题而设计的这套高效方案。核心思路是将内存预先分割成固定大小的内存块（Slab Class），每个 Slab 内部再细分为相同尺寸的 Chunk。当数据存入时，Memcached 会根据数据大小找到最匹配的 Slab Class，从中分配一个 Chunk。这种“分类定长”的分配方式，极大减少了内存碎片，提升了分配与回收的效率。文章还具体分析了 Slab 的扩展策略以及内存池（Memcached_arena）在其中的作用。通过源码级解读，文章清晰地展现了 Memcached 如何用看似简单的“空间换时间”策略，实现了高性能、低碎片化的内存管理，揭示了其在实际高并发场景下能够保持稳定高效的底层原因。

IT 累计浏览 3,017

浅析Linux Kernel 哈希路由表实现(二)

这篇讲的是Linux内核在发送数据包时，如何通过一个清晰的函数调用链找到路由的实现细节。作者从外层函数ip_route_output_key()出发，一步步追踪到最终的执行者__ip_route_output_key()。核心焦点就集中在__ip_route_output_key()这个函数上。它是内核路由查找的真正引擎，负责根据目标地址、源地址等关键信息，在哈希路由表中高效地匹配出最佳路由项。文章没有停留在概念层面，而是直接潜入内核源码，剖析这个函数如何处理不同的查找场景，比如它是如何利用路由缓存加速，以及在复杂情况下如何进行精确的匹配与回溯。通过这样的分析，读者能清晰地看到内核网络栈为了兼顾性能与准确性，在路由查找路径上做出的精巧设计。这种对底层实现逻辑的拆解，对于理解数据包的旅程和网络性能优化都很有启发。

IT 累计浏览 4,553

redis源代码分析 - hash table

这篇深入剖析了Redis核心数据结构之一——哈希表（dict）的实现。作者从`dict.c`源码出发，揭示了Redis如何用一个结构同时管理两张哈希表（`ht[0]`和`ht[1]`），并在`rehash`过程中巧妙地通过“渐进式迁移”来避免阻塞。文章的关键在于讲清楚了“渐进式rehash”的运作机制：当需要扩容或收缩时，Redis并不会一次性完成迁移，而是将rehash过程分散到后续的每一次增删改查操作中，每次只迁移一小部分。同时，它详细说明了触发rehash的负载因子阈值，以及在rehash期间如何通过一个标志位确保操作的正确性。这种设计使得即使在处理百万级键值的大型哈希表时，Redis也能保持极低的延迟。文章将这个精巧的工程实现拆解得清晰易懂，展现了Redis为追求高性能而做出的底层权衡与智慧。

IT 累计浏览 3,002

Hopscotch Hashing

这篇讲的是Hopscotch Hashing，一种旨在显著提升查询速度的开放地址哈希方法。作者直接点明，传统思路（如链地址法或其它开放寻址方式）在哈希表负载较高时，性能会急剧下降，查询复杂度难以维持。文章的核心方案围绕一个巧妙的插入时调整策略展开：通过在插入数据时主动将其“路由”到目标桶的邻近区域，让每个桶的“邻居”形成一个高效的数据簇。这个过程有点像精心规划交通，确保前往某个目的地（桶）时，所有相关的车辆（数据）都停在旁边的几个固定停车位里，而不是散落在整个停车场的各个角落。这种设计带来的关键差异和结论是，它能在最坏情况下也保证查询操作的时间复杂度为一个常数，这是很多传统哈希方法难以做到的。无论哈希表装得多满，你查找任何一个键的耗时基本都是确定的，这对于需要稳定低延迟的应用场景非常有价值。文章没有停留在理论层面，而是清晰地阐述了这种算法如何通过“预见性布局”来克服开放寻址哈希的经典痛点，真正承诺了性能的稳定可预测。

IT 累计浏览 3,137

思考mysql内核之初级系列7---innodb的hash表实现

这是系列文章《思考MySQL内核之初级》的第7篇，前文讨论了InnoDB文件系统管理时引出了两个基础结构：hash_table_t和UT_LIST_NODE_T。本篇接着这个线索，专门聚焦于hash_table_t这个在内核中被广泛使用的哈希表结构。作者从这两个常用结构切入，旨在带领读者理解哈希表在数据库存储引擎内核中的具体实现与核心作用。文章并未停留在概念层面，而是深入到了实现细节，探讨了InnoDB如何利用哈希表这一经典数据结构来高效管理其内存与数据元信息。这种对底层数据结构实现的剖析，恰恰是理解大型软件系统内存管理和性能优化的关键。它揭示了在复杂的数据库内核中，一个看似基础的工具是如何被精巧地设计和应用的。对于想进一步了解InnoDB内部运作机制或学习系统级编程的读者来说，这篇聚焦于一个具体实现点的讨论，提供了扎实且有价值的视角。

IT 累计浏览 2,783

PHP中的Hash算法

这篇讲的是PHP中核心数据结构Hash Table的底层实现。作者从“Hash Table是PHP的心脏”这一观点切入，深入剖析了PHP如何通过哈希算法管理数组、对象等数据，揭示了其高效运作背后的关键。文章详细拆解了PHP哈希表的实现机制，重点对比了PHP 5与PHP 7在哈希算法上的重大升级——从DJBX33A到SipHash-1-3的演变。作者不仅解释了SipHash算法在抵御哈希碰撞攻击方面的安全性优势，还结合源码，分析了PHP 7如何通过优化内存布局（如将哈希表拆分为arData和arHash两部分）和引入紧凑的存储结构，显著提升了查询效率与内存利用率。通过具体的源码片段和性能对比，文章清晰地展示了一次看似简单的数组访问（`$arr['key']`）在底层经历了哈希计算、冲突解决、值定位等一系列精妙操作。这种从原理到实现的贯通分析，有助于开发者理解PHP“快”与“安全”背后的工程抉择。