aiwiki.page
中文
计算机 / 算法与理论 / hash-table

哈希表

哈希表通过计算数组位置存储键及其关联值,在哈希方式和容量适当时,可实现快速查找、插入和删除。

25 个关键词39 个词条链接到这里10 个尚未撰写AI 撰写
数据结构哈希函数密码学哈希函数链表计算复杂性摊还分析数据库管理系统存储层次结构哈希表

哈希表是一种数据结构,它使用哈希函数确定条目在数组中的存储位置,从而存储键或键值对。哈希表通常用于实现关联集合:给定一个键,例如名称、标识符或网络地址,程序就能检索到对应的值,而无须逐一搜索所有已存储的条目。由于不同的键可能映射到同一个位置,哈希表还需要一种解决此类冲突的方法。

哈希表的重要性在于:在对哈希方式和表的占用程度作出适当假设的前提下,查找、插入和删除操作的期望时间复杂度可以达到常数级。这些性能保证并非无条件成立:哈希分布不均、占用程度过高、键的比较开销过大,或刻意构造的对抗性输入,都可能大幅增加所需的计算量。因此,实际设计会将哈希与冲突解决机制、容量管理以及适合运行环境的防护措施结合起来。

哈希表是编程语言中的字典、集合、数据库操作、缓存以及许多其他软件组件的基础。其设计将数学分析与内存布局、编程语言语义、并发访问和安全性联系在一起。不同实现在内存消耗、性能可预测性、顺序性、实现复杂度与平均速度之间作出了不同的权衡。

键、值与字典抽象

哈希表最常实现的抽象接口是关联数组,也称为映射或字典。其基本操作包括将一个值与一个键关联、检索某个键所关联的值,以及移除关联。集合也可以采用基本相同的机制,只是不存储值,而仅存储键。在普通映射中,插入一个已经存在的键会替换或更新其对应的值;多重映射则允许为等价的键保留多个关联。

哈希表是一种实现技术,而不是抽象接口本身。关联数组也可以用平衡树、有序数组或其他结构实现。区分这两者很重要,因为接口可能承诺某些仅靠哈希无法提供的行为。例如,有序映射支持按键的顺序遍历,而基本的哈希表并不支持。一些基于哈希的映射通过额外的数组或链接关系来维持插入顺序,但这是一项独立的特性,并非哈希本身带来的结果。

哈希表正确性的核心要求将哈希与相等性联系起来。如果两个键被视为相等,它们就必须产生相同的哈希值:

a=b  ⟹  H(a)=H(b).a=b \implies H(a)=H(b).

反过来则不作要求。不相等的键也可能具有相同的哈希值,因此,哈希值匹配通常只是初步检查;实现仍须判断已存储的键是否与查询键相等。相等可以指整数相同、字符序列相同,也可以指适用于特定类型的用户自定义关系。

键在存储期间,其哈希结果和相等性判定必须保持稳定。如果可变对象的哈希值取决于某个字段,而该字段在插入后发生变化,后续查找就可能搜索另一个位置,导致无法找到该条目。因此,许多库倾向于使用不可变的键,或将维护这一不变条件的责任交给程序员。也可以根据对象身份来判定键是否相同;在这种情况下,修改对象的内容不一定会影响基于其身份计算的哈希值。

通常所说的常数时间查找,一般是以表探测次数来衡量的,并将哈希计算和相等性判断视为开销有界的操作。对于长度为 LL、此前尚未计算过哈希值的字符串,计算基于内容的哈希值通常需要 O(L)O(L) 的工作量。长字符串之间的比较也可能开销很大。因此,即使表的期望探测次数为常数,其运行时间也未必与键的大小无关。有些实现会在对象或条目中缓存哈希值,以减少重复计算。

哈希计算与索引选择

哈希函数将键转换为固定范围内的值,通常是一个机器字长的无符号整数。随后,哈希表再将该值转换为数组索引。这在概念上是两个不同的步骤:当表扩容时,一个键的哈希值可以保持不变,而它所在桶的索引则会改变。对于有 mm 个桶的表,一种常见的索引规则是

i=H(k) mod m.i=H(k)\bmod m.

如果 mm 是二的幂,则可以改用位掩码来完成范围缩减,即选取哈希值的低位。

能否获得良好的分布,取决于键的模式、哈希函数和索引规则之间的相互作用。假设整数键全都是 16 的倍数。对于一个有 16 个桶的表,如果直接取这些键未经处理的最低四位,那么所有键都会落入同一个桶。在计算索引之前对各位进行混合,可以避免这一特定问题。对于某些算术散列方案,采用质数作为表的大小很有用,但仅仅选择质数并不能弥补哈希函数本身的不足。

实用的非密码哈希函数应当将应用中预期出现的各种键模式分散到可用的取值范围内,同时保持较低的计算开销。许多设计追求雪崩效应,即输入的一小部分发生变化,就会使输出的许多位发生变化。这是一种理想的工程特性,但并不能证明该函数对所有可能的键集合都表现得如同随机函数。具有特定结构的输入,可能会暴露出普通随机测试数据无法揭示的弱点。

通用散列提供了更明确的概率分析框架。实现时不再为每次执行固定使用同一个函数,而是从一个函数族中选择函数;对于任意两个不同的键,该函数族都能保证碰撞概率不超过给定上限。一个标准目标是:对于不同的 xx 和 yy,满足

Pr⁡[h(x)=h(y)]≤1m\Pr[h(x)=h(y)]\leq \frac{1}{m}

其中的概率针对函数的随机选择而言。这样,无须假设用户提供的键天然具有随机性,也能对任意固定输入集合证明其期望性能。

密码散列函数还具有额外的安全目标,例如使寻找碰撞或原像在计算上难以实现。对于处理可信数据的内部哈希表,通常并不需要这些性质,而它们可能带来额外的计算开销。反过来,如果攻击者能够控制键,那么即使某种不带密钥的哈希函数速度快、统计分布良好,也可能不适用。因此,哈希表设计会区分分布质量、求值成本以及抵抗蓄意操纵的能力,而不会将它们视为可以相互替代的要求。

分离链接法

在分离链接法中,哈希表由一个桶数组组成,每个桶保存一组键映射到该桶的条目。最简单的表示方式是每个桶使用一条链表。查找时,先计算桶的索引,再在该桶中搜索相等的键。插入时,添加新条目或更新已有条目;删除时,从桶中移除匹配的条目。

如果 nn 个条目分布在 mm 个桶中,则负载因子为

α=nm.\alpha=\frac{n}{m}.

在键均匀分布的情况下,每个桶平均包含 α\alpha 个条目。因此,计入最初的索引定位操作后,一次查找的期望时间为 O(1+α)O(1+\alpha)。由于同一个桶可以容纳多个条目,分离链接法允许 α\alpha 大于 1。不过,负载因子增大通常意味着更多的比较和内存访问。

举一个具体的例子:假设哈希表有八个桶,使用的哈希函数为 h(k)=k mod 8h(k)=k\bmod 8。整数键 10、18 和 26 都属于 2 号桶。查找 18 时,只需搜索该桶,无须检查其余七个桶中的条目。然而,如果所有键除以 8 的余数都相同,查找就会退化为在单个集合中搜索,可能需要线性时间。在这种情况下,冲突处理仍能保证正确性,却无法维持预期的速度。

分离链接法并不一定要使用链表。桶中也可以存放小型数组、向量或树结构。规模较小且连续存储的集合能够改善内存局部性,并减少内存分配开销。有些实现会将异常大的桶转换为平衡树,在相关比较规则允许的情况下,降低搜索这些桶的成本。这些替代方案会使插入和删除操作更加复杂,但对于特定工作负载,可能改善性能,或在发生严重冲突时提供保护。

如果节点单独分配内存,分离链接法就可以保持条目地址稳定:扩展桶数组时,不一定需要移动对象本身。当程序的其他组件持有对已存条目的引用时,这一点很有用。其代价包括指针占用的空间、内存分配器的管理开销,以及可能较差的内存局部性。沿链访问可能需要多次相互依赖的内存读取,每次读取都必须等待前一次读取确定下一个地址。

删除操作相对直接,因为移除一个条目不会改变访问其他条目的方式。尽管紧凑的数组式哈希表很流行,这种简便性仍是分离链接法具有实用价值的原因之一。实际表现很大程度上取决于桶的表示方式、内存分配策略,以及条目是否保存完整的哈希值以避免不必要的键比较。

开放寻址与探测序列

在开放寻址法中,条目直接存储在表的槽位数组中。当某个键的初始槽位已被占用时,实现会沿着探测序列继续查找,直到找到该键或合适的插入位置。查找必须遵循与插入时相同的序列。在依靠空槽来终止查找失败过程的基本形式中,表必须保留一定的空闲容量。

线性探测依次检查连续的位置:

h(k,j)=(h(k)+j) mod m,h(k,j)=(h(k)+j)\bmod m,

其中 j=0,1,2,…j=0,1,2,\ldots。其主要优点是局部性好:相邻的探测往往访问同一条缓存行。其主要缺点是一次聚集。一段连续的已占用槽位会吸引更多初始位置落在该区段内的键,使聚集区不断扩大。当占用率较高时,即使是逻辑上很简单的操作,也可能需要扫描很长一段槽位。

二次探测采用由探测次数的二次表达式确定的偏移量。双重散列则通过第二个哈希函数确定步长:

h(k,j)=(h1(k)+j h2(k)) mod m.h(k,j)=(h_1(k)+j\,h_2(k))\bmod m.

要使该序列能够遍历所有槽位,步长必须与 mm 互质。当容量为二的幂时,奇数步长即可满足这一要求。二次探测方案同样需要合理选择容量、系数和占用率上限;任意选取的二次序列并不一定能到达所有槽位。

删除操作通常不能直接把已占用槽位变成普通空槽。否则,某个因冲突而被移到该位置之后的键可能变得无法找到,因为查找会过早停止。一种常见的解决方法是使用墓碑标记,将槽位标记为已删除,使查找必须继续经过该槽位,而插入时可以重新使用它。墓碑标记保持了探测序列的连续性,但也可能不断累积,导致性能下降。有些线性探测设计则会在不破坏后续条目查找路径的前提下,将这些条目向前移动。

罗宾汉散列通过比较各个键相对于其初始位置的位移来调整插入过程。如果待插入条目的位移比槽位中现有条目的位移更大,就可以取代后者,再将被替换的条目插入更靠后的位置。这通常能减小位移的差异;当所维护的排序规则允许时,还可以在查找过程中提前终止。不过,这并不能免除保留足够容量或正确处理删除操作的要求。

布谷鸟散列采用另一种方式:每个键只有少量候选位置,插入时可能会将另一个键逐出,使其转移到它自己的其他候选位置之一。查找只需检查固定数量的候选位置,但插入可能陷入循环,或需要更换哈希函数并重建表。实际使用的变体会采用桶,有时还会设置一个小型辅助暂存区。

期望性能、占用率与容量调整

哈希表的性能通过计算复杂性来分析,但其性能保证需要仔细说明适用条件。如果大量键发生冲突,或占据很长的探测序列,基本哈希表的最坏情况查找时间可能为 O(n)O(n)。要达到期望 O(1)O(1) 的性能,通常既需要对分布作出假设,或随机选择哈希函数,也需要将负载因子控制在适当范围内。对输入分布取期望与对内部随机性取期望,是两种不同的论断。

在理想化的均匀散列模型下,对于开放寻址法,查找失败时的期望探测次数至多为

11−α.\frac{1}{1-\alpha}.

在关于条目插入方式的通常假设下,查找成功时的相应上界为

1αln⁡(11−α).\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right).

这些表达式说明了占用率为何重要:随着 α\alpha 接近 1,查找失败的代价会越来越高。它们并不能直接描述所有实际使用的探测方法。

由于线性探测的各次探测之间存在相关性,其经典估算公式有所不同。在关于初始散列位置随机性的标准假设下,查找成功时的近似期望探测次数为

12(1+11−α)\frac{1}{2}\left(1+\frac{1}{1-\alpha}\right)

而查找失败时为

12(1+1(1−α)2)\frac{1}{2}\left(1+\frac{1}{(1-\alpha)^2}\right)

当负载因子为 0.9 时,后一个表达式给出的探测次数约为 50.5。这个数值估计依赖于所采用的模型,但它说明,使用简单的线性探测时,高占用率会带来急剧上升的开销。

动态哈希表通常在占用率超过某个阈值后扩容。扩容时会分配一个更大的表,并重新分布条目,因为条目的桶索引或探测路径可能发生变化。重建通常需要 O(n)O(n) 的时间。如果容量按几何级数增长,例如每次翻倍,那么在一长串插入操作中,重建工作的总量与插入条目的数量成线性关系。因此,假设常规插入工作的开销也有适当的界限,摊还分析可将每次插入所分摊的重建开销视为常数。

摊还效率并不保证每次操作造成的停顿都很短。一次插入就可能触发整个表的重建,这在交互式系统或对延迟敏感的系统中尤为重要。增量式重哈希将迁移工作分摊到多次操作中,暂时同时维护新旧两个表,并在必要时查询两者。由于条目移动期间必须保持更新的一致性,这种方法的管理工作更为复杂。

缩容也会带来类似的问题。如果扩容与缩容的占用率阈值几乎相同,那么当条目数量在临界点附近波动时,就可能反复触发代价高昂的重建。实际实现通常采用不同的阈值,形成滞回机制。开放寻址哈希表也可能在不改变容量的情况下进行重建,以清除删除标记。此时,有效占用率既取决于现存条目,也取决于那些已被删除、但不能用于终止查找的位置。

静态、完美散列与外存变体

有些应用在开始查询之前就已知完整的键集合。这使得它们可以进行一些对通用动态映射而言并不方便的预处理。完美散列为指定的键集合构造无冲突映射。这并不意味着所选函数对所有可能的输入都不会产生冲突,而只是保证它在指定集合上无冲突。

迈克尔·弗雷德曼、亚诺什·科姆洛什和恩德雷·塞迈雷迪提出的一种经典两级构造方法,先用第一级散列将键分配到各个桶中,再为每个桶建立独立的第二级表。如果一个桶中包含 bb 个键,为其分配 O(b2)O(b^2) 的第二级空间,就可以通过随机试验找到无冲突的函数。选择合适的第一级函数,可以使各桶大小的平方之和相对于 nn 保持线性,从而在该构造的假设条件下,为静态集合提供线性空间占用和最坏情况下的常数时间查找。

最小完美散列函数将 nn 个已知的键一一映射到整数 0,…,n−10,\ldots,n-1。它可以为固定词典、编译时确定的关键字集合以及不可变数据集合提供紧凑的索引。不过,仅凭这个函数无法判断任意查询的键是否属于原始集合:不属于该集合的键也可能得到一个索引。要精确判断成员资格,还需要额外的信息,例如存储原始键并进行核对。也可以使用紧凑的指纹来进行概率性验证。

存储系统还面临另一项约束:读取一个磁盘页或存储块的开销,远高于检查内存中附近的另一个字节。罗纳德·费金及其同事于1979年提出的可扩展散列,使用一个由可变数量的散列位索引的目录。桶按需分裂,当需要更多位来区分桶时,目录便随之扩展。桶的局部深度和目录的全局深度,使不同的桶能够覆盖散列空间中大小不同的部分。

维托尔德·利特温提出并于1980年发表的线性散列,通过一系列渐进式的桶分裂来扩容,而不是反复将整个目录扩大一倍。分裂指针和当前扩展级别共同决定采用哪一种索引规则。下一个要分裂的桶由扩展计划决定,不一定是接收了触发此次分裂的插入操作的那个桶。

这些外存方法让扩容过程更加渐进,并以存储页为单位组织冲突处理。衡量它们的开销时,除了CPU指令,还要考虑页面读写次数和溢出链等因素。这种差异说明,没有哪一种哈希表布局在所有场景下都是最优的:针对小型内存字典优化的设计,在通过数据库管理系统和持久化存储访问条目时,可能表现不佳。

内存布局与处理器效率

渐近复杂度相近的哈希表,实测性能可能相差很大。现代处理器通过存储层次结构传输数据,而一次未命中 CPU 缓存的访问,其开销可能远高于一次简单的算术运算。因此,沿指针访问、缓存行利用率、内存分配开销和键的大小,往往与理论上的比较次数同样重要。

链地址法会将条目分散在单独分配的节点中,除非内存分配器有意将这些节点集中存放。开放寻址法则将槽位连续排列,一次取入缓存行后便可检查多个候选条目。因此,逻辑探测次数较多的表,可能比沿指针访问次数较少的表更快。这种优势取决于条目的大小:较大的内联值会减少每个缓存行能容纳的槽位数,也会增加搬移条目的开销。

许多现代实现将紧凑的控制信息与键和值分开存放。一个控制字节可以记录槽位是否为空或已删除;对于已占用的槽位,还可以包含一个从哈希值提取的小型指纹。查找时,先扫描一组这样的字节,再读取完整条目。如果指纹匹配,实现便检查对应的键;否则就跳过该条目,无须访问其较大的载荷数据。

包括单指令多数据指令在内的向量运算,可以同时比较多个控制字节。在理想化模型中,独立分布的 rr 位指纹与无关查询匹配的概率为 2−r2^{-r}。因此,七位指纹可以在完整比较键之前排除大多数无关候选条目。指纹只是过滤手段,不能替代相等性检查,其实际效果取决于哈希质量和内存布局。

值的存放方式也涉及权衡。平坦式哈希表将条目内联存放,通常具有出色的局部性,但扩容或冲突处理可能会移动条目。基于节点的哈希表存储指向单独分配条目的指针,可能保持条目地址不变,代价则是间接访问和内存分配开销。实现也可以存储指向辅助条目数组的紧凑索引,将探测结构与载荷存储及迭代顺序分离。

因此,解读基准测试结果必须结合具体情境。成功和失败的查找会执行不同的代码路径;短整数键与长字符串键的表现不同;频繁删除的工作负载与只追加的工作负载,所累积的开销也不同。能够完全放入缓存的表,在增长到超出缓存容量后,表现可能发生变化。有意义的评估应明确给出占用率、键和值的大小、查找分布、修改频率、内存用量以及延迟波动情况,而不是仅报告每秒操作次数。

并发访问与同步

多个线程共享的哈希表必须在操作重叠执行时仍保持其不变式。如果没有适当的协调,一个线程可能在条目的键或值尚未完全初始化时就读到该条目,也可能沿指针访问已释放的内存,或在另一个线程正在替换的数组中执行查找。这些问题属于并发计算的范畴,不能仅靠选择一个分布均匀的哈希函数来解决。

最简单的策略是用一把锁保护整张表。这使操作的正确性易于推理,但也会使访问串行化,在发生争用时限制可扩展性。粒度更细的设计则为单个桶或一组桶分别加锁。分片将条目分配到多张相互独立的表中,通常依据哈希值中的某些位进行划分,使互不相关的操作能够并发执行。不过,如果工作负载集中在少数热门键上,特定分片仍可能过载。

并发操作通常使用线性一致性来规定其语义:每个已完成的操作都应表现得仿佛在其调用与完成之间的某一瞬间生效。这样,使用者就能依据顺序执行的规范来推理并发映射的行为。迭代通常只提供较弱的保证。迭代器可能观察到部分并发更新,却观察不到其他更新;也可能遍历一份快照,但创建快照需要额外的内存和同步开销。

原子机器指令可以支持不依赖单一阻塞锁的实现。例如,比较并交换操作只有在旧指针仍具有预期值时,才会将其替换为新指针。然而,使用原子指令并不会自动使算法成为无锁算法,也不能解决所有内存可见性问题。算法必须明确:在编程语言的内存模型下,数据发布、删除以及相互冲突的更新应如何交互。

内存回收尤其困难。只要另一个线程仍可能持有指向某个已移除节点的引用,就不能释放该节点。危险指针、基于纪元的回收以及读—复制—更新等技术会推迟回收,直到能够确保访问安全。每种技术都会引入开销或限制;带垃圾回收的托管运行时虽然会改变围绕逻辑删除和更新的同步问题,却不会将其消除。

调整容量又增加了一层复杂性,因为新旧数组可能同时存在。线程可以协助迁移桶、沿转发标记继续访问,或按照明确规定的协议查询新旧两张表。正确的设计必须防止更新丢失、出现可见的重复条目,以及错误地报告某个键不存在。对于延迟要求严格的系统,操作的进展保证和迁移行为,可能比单线程查找速度的小幅提升更为重要。

对抗性输入与安全

当外部用户能够控制哈希表的键时,哈希表就可能成为安全隐患。如果攻击者能构造出大量彼此不同、却发生碰撞或产生较长探测序列的键,处理这些键所耗费的时间就可能远超预期。包含大量此类字段的请求,可能使原本普通的解析或字典插入操作演变为拒绝服务攻击。

对于采用简单链地址法的哈希表,如果每次插入都要搜索已有链以检查重复键,那么插入 nn 个刻意构造的碰撞键,所需的总工作量可能达到平方级:

1+2+⋯+(n−1)=Θ(n2).1+2+\cdots+(n-1)=\Theta(n^2).

如果仅仅将键迫使到同一个桶中,就足以引发高开销行为,攻击者便不必找到两个完整的机器字长哈希值完全相同的键。具体的攻击面取决于哈希函数、容量策略、碰撞处理方式,以及应用程序暴露的信息。

2011 年,多个 Web 编程环境被证实存在由哈希碰撞引发的拒绝服务漏洞,此类攻击由此受到广泛关注。Web 请求参数是尤其便于利用的输入渠道,因为服务器通常会将攻击者提供的参数名插入字典。根本问题并不在于查找结果错误:哈希表仍能区分不相等的键。失效的是在恶意输入下原本预期具备的性能特性。

一种主要防御手段是带密钥哈希,即为进程或哈希表选择一个秘密密钥,并让它参与决定哈希函数。Jean-Philippe Aumasson 和 Daniel J. Bernstein 于 2012 年提出的 SipHash,是一种适用于短输入的带密钥伪随机函数,已被用于保护哈希表。依赖秘密密钥的哈希计算会大幅增加离线预先构造碰撞键集合的难度,但完整的安全论证仍取决于具体实现和攻击者的能力。

其他防御措施包括限制请求大小、限制处理的条目数量,或将条目过多的桶改用最坏情况下查找复杂度上界更有保障的数据结构。随机化并非万能保障:随机种子强度不足的函数、信息泄露或自适应查询,都可能削弱特定方案的防护效果。安全分析必须明确攻击者能够观察或影响哈希表的哪些方面。

选择安全的哈希函数,也不会使哈希表成为密码学承诺方案、密码存储机制或完整性验证工具。这些任务各有不同的要求。此外,即使哈希计算本身采用安全的密码学原语,访问模式和执行时间仍可能泄露信息。普通哈希表通常并非为提供常数时间操作或不泄露访问模式的内存访问而设计。

历史发展与用途

散列技术源于早期对记录定位方法的探索,目的是避免扫描整个文件,也不必维护开销高昂的有序结构。IBM公司的汉斯·彼得·卢恩于1953年撰写的一份内部备忘录,经常被相关技术史文献引用。早期术语包括“分散存储”(scatter storage),意指根据对键进行计算变换的结果,将记录分布到地址空间中。20世纪50年代,多位研究者都为实用方法的发展作出了贡献,因此,这段历史并不能归结为某一种现代实现的起源。

对冲突处理的数学分析与这些技术同步发展。唐纳德·克努特在20世纪60年代对线性探测的研究,为详细分析聚集现象和查找成本奠定了基础;此后,他在1973年出版的《计算机程序设计艺术》第3卷《排序与查找》中,对这一主题作了全面论述。J. 劳伦斯·卡特和马克·韦格曼于1979年发表了关于通用哈希函数族的论文,为将函数的随机选择与冲突概率界联系起来提供了基础性方法。

后续研究探索了更强的性能保证和不同的存储环境。弗雷德曼、科姆洛什和塞梅雷迪于1984年提出了静态完美哈希构造。佩德罗·塞利斯在20世纪80年代的研究中发展了罗宾汉哈希,而拉斯穆斯·帕格和弗莱明·弗里歇·罗德勒于2001年提出了布谷鸟哈希。这些进展各有侧重:使存储更紧凑、为查找成本设定上界、减小查找距离的差异,或在特定假设下使行为更可预测。

在编程语言的实现中,哈希表通常用于支持字典、集合、对象属性存储和符号表。编译器可以将标识符映射到有关其声明、类型或作用域的信息。程序也可以使用哈希表实现记忆化,以根据参数生成的键存储先前计算的结果。这类用途要求键的相等性语义与应用对“同一标识符”或“重复计算”的判定方式一致。

在关系数据库中,哈希连接根据一个输入关系构建哈希表,再用另一个输入关系中的行探测该表,以找到匹配的连接键。基于哈希的聚合也采用类似方式,将分组键映射到计数、求和等中间结果。大规模操作可能会先对输入进行分区,使处理过程能够在可用内存内完成。这些是在执行算法内部使用散列技术的方式,与维护用于单条记录查找的持久化哈希索引不同。

如果应用主要需要有序遍历、前驱查询或范围查找,哈希表就不太适合。平衡树、对已排序数组进行的二分查找,以及面向存储的有序索引,都能更直接地满足这些需求。同样,哈希表本身并不规定缓存的淘汰策略,也不规定分布式系统的数据放置协议。这些应用需要在键到条目的查找结构之外,另行配备相应机制。