使用具有一组经常访问的桶和一组不经常访问的桶的哈希表的系统和方法

摘要

一种方法和设备对第一键执行第一哈希操作，其中偏置所述第一哈希操作以将所述第一键和关联值映射到哈希表的一组经常访问的桶。将所述第一键的条目和关联值存储在所述一组经常访问的桶中。对第二键执行第二哈希操作，其中偏置所述第二哈希操作以将所述第二键和关联值映射到所述哈希表的一组不经常访问的桶。将所述第二键的条目和关联值存储在所述一组不经常访问的桶中。所述方法和设备在所述一组经常访问的桶中执行所请求键的哈希表查找，如果未找到所述所请求键，则在所述一组不经常访问的桶中执行哈希表查找。

说明书

发明背景

哈希表是实现相关联阵列的数据结构。对于一些哈希表，使用一个或多个哈希函数将给定“键”映射到一个或多个索引，这些索引标识哈希表内的桶，所述桶可能保存与键相关联的“值”(或指向所述值的指针)。通常，桶包含多个“槽”，每个槽可以保存单个键值对。桶中的槽是完全关联的，因为桶中的任何槽都可以保存映射到所述桶的任何项。哈希表广泛用于许多应用领域。理想的哈希表尝试将其内容均匀地分布在其所有桶中。例如，由应用程序调用的软件库采用核心原语，例如哈希表，所述哈希表在包括关系数据库、键值存储区、机器学习应用程序和其他用途的广泛的应用程序领域中提供广泛的适用性。

然而，在非常大的哈希表的情况下，在所有桶中均匀分布内容可能会导致高速缓存性能不佳，即使数据本身具有时间局部性，因为每个桶通常最终会混合使用经常访问(FA)和不经常访问(IA)的数据。例如，硬件高速缓存被设计成尝试捕获经常访问的数据。然而，通过设计(即，项均匀分布和放置在桶中)，哈希表将经常访问的项与不经常访问的项混合在相同的高速缓存行中，从而阻碍了高速缓存捕获热工作集的能力。

一些传统的高性能哈希表通常使用多个映射哈希函数(通常是两个)来将给定的键映射到哈希表中的多个候选桶。图1中示出简化示例。通常在将新的数据项10插入到哈希表12中时，并行计算哈希函数14和16的输出，然后将所述项插入到具有最多未占用槽的候选桶中。在具有八个桶和每个桶四个槽的示例哈希表中，占用的槽以灰色显示且空槽以白色显示。如图所示，针对所标识的候选桶5和0使用两个哈希函数F1()和F2()插入具有键K和值V的新项(K,V)。如果插入策略是插入负载最小的候选桶中，则在此示例中将(K,V)插入到桶5中。这有助于使哈希表的不同桶上的加载更均匀，从而即使在高负载因子下也允许均匀加载。或者，可以连续地评估哈希函数，并且遇到插入到具有可用空间的第一候选桶中的项。如果所有候选桶都是满的，则使用驱逐(例如布谷鸟驱逐)，其中驱逐现有项中的一个，从而为新数据项腾出空间。然后将驱逐的项重新插入到其备用候选桶之一中。如果所有候选桶也都是满的，则驱逐链继续，直到驱逐终止，例如当最后一个驱逐的项能够放入其候选桶之一中时。

在查找操作期间，对被查找的键应用映射哈希函数以定位候选桶。然后，搜索候选桶中的每个槽，从而将感兴趣的键与候选桶的每个槽中的键进行比较。由于桶内的槽完全关联(即映射哈希函数仅标识桶，而不是桶内的特定槽)，因此需要在所有槽中进行搜索。因为哈希表通常试图将数据元素均匀地分布在桶中，所以大型哈希表的高速缓存性能较差。例如，即使对数据集的大部分访问是针对小部分的数据项，它们也分布在整个哈希表中。此外，哈希桶的大小通常被设计为使得桶的多个槽适合于单个高速缓存行。因此，将单个经常使用的项提取到高速缓存中可能还会提取作为同一桶的一部分的多个不经常使用的项，从而降低高速缓存捕获一组有用的经常访问项的能力。

因此，为高速缓存或其他用途提供改进的哈希表操作将是非常有利的。

附图说明

当结合以下附图时，鉴于以下描述，将更容易理解实现方式，其中相同的附图标记表示相同的元件，并且在附图中：

图1是示出使用多个哈希函数来确定用于插入哈希表条目的合适桶的哈希表的一个示例的现有技术框图；

图2是示出根据本公开中阐述的实施方案的计算系统的部分的一个示例的框图；

图3是示出由图2中所示的计算系统的部分执行的方法的一个示例的流程图；

图4是示出根据本公开中阐述的一个示例的哈希表的一个示例的图，所述哈希表采用由经常访问的桶和不经常访问的桶隔开的不同组的桶；

图5是示出根据本公开中阐述的一个示例的用于将哈希表条目插入哈希表中的方法的一个示例的流程图；

图6是示出根据本公开中阐述的一个示例的用于查找哈希表条目的方法的一个示例的流程图；

图7是示出根据本公开中阐述的一个示例的用于移动哈希表条目的方法的一个示例的流程图；

图8是示出根据本公开中阐述的一个示例的用于存储哈希表条目的方法的一个示例的流程图；以及

图9是示出根据本公开中阐述的一个示例的计算系统的一个示例的框图。

具体实施方式

简而言之，系统和方法将哈希表的桶划分为两个不相交的集合，即经常访问的桶和不经常访问的桶。术语“不经常”和“稀少地”在本文中可互换使用。在一些实现方式中，选择经常访问集合中的多个桶，使得经常访问的桶可能适合于硬件高速缓存。在一些实现方式中，偏置可以被称为经常访问(FA)映射函数的映射哈希函数的子集以主要映射到哈希表中的所述一组经常访问的桶，并且其余哈希函数是被偏置以主要映射到哈希表中的所述一组不经常访问的桶的映射哈希函数的子集。在一些实现方式中，维护跟踪数据以标识哪些数据项经常访问，而哪些数据项不经常访问。基于跟踪数据，标识经常访问的元素并且将它们移动到哈希表的经常访问的桶，而不经常访问的数据项保留在不经常访问的桶中。

根据某些实现方式，由一个或多个处理器执行的方法对第一键执行第一哈希操作，其中偏置第一哈希操作以将第一键和关联值映射到哈希表的第一组桶内的第一候选桶，所述第一组桶用作一组经常访问的桶。所述方法包括将第一键的条目和相关联值存储在哈希表的第一组桶内的第一候选桶中，例如大小设计成适合于所述一组经常访问的桶集合的高速缓存存储器中。所述方法还包括对第二键执行第二哈希操作，其中偏置第二哈希操作以将第二键和关联值映射到哈希表的第二组桶内的第二候选桶，所述第二组桶用作一组不经常访问的桶；以及将第二键的条目和关联值存储在哈希表的第二组桶内的第二候选桶中。响应于对键的查找请求，所述方法包括在第一组经常访问的桶中执行所请求键的哈希表查找，如果未找到所请求键，则所述方法包括在所述一组不经常访问的桶中执行所请求键的哈希表查找。在其他实现方式中，所述方法包括并行使用哈希函数和两组桶来执行查找。

在一些示例中，所述方法包括偏置第一和第二哈希操作，使得第一哈希操作将第一键和关联值排他地映射到哈希表的用作所述一组经常访问的桶的第一组桶，并且使得第二哈希操作将第二键和关联值排他地映射到哈希表的用作所述一组不经常访问的桶的第二组桶。

在某些示例中，默认优先级给定为将条目存储在不经常访问的桶中。在一些实施方案中，首先将所有键值对插入到所述一组不经常访问的桶中，然后如果事实证明经常访问所述值，则将所述值移动到经常访问的桶集合。在一些示例中，所述方法包括当哈希表的用作不经常访问的桶的第二组桶满时驱逐哈希表条目，然后将哈希后的第二键的条目存储在第二组桶中。可以基于条目的访问频率来选择驱逐的条目，使得将更经常访问的条目从用作不经常访问的桶的第二组桶中驱逐并且将它们移动到用作经常访问的桶的第一组桶。

在某些示例中，所述方法包括产生跟踪数据，所述跟踪数据表示已经访问哈希表的第一组经常访问的桶和哈希表的第二组不经常访问的桶内的桶中的每个槽的次数。在一些示例中，所述方法包括基于跟踪数据将条目从第二组不经常访问的桶移动到第一组经常访问的桶，或反之亦然。

在一些示例中，所述方法包括响应于表条目请求在加权的基础上执行第一和第二哈希操作。在某些示例中，所述方法包括存储和使用每桶充满度数据以确定是否在哈希表的第一和第二组桶之间移动哈希表条目。

根据某些实现方式，计算装置包括哈希表逻辑，所述哈希表逻辑对第一键执行第一哈希操作，其中偏置第一哈希操作以将第一键和关联值映射到哈希表的第一组桶内的第一候选桶，所述第一组桶用作一组经常访问的桶；以及将第一键的条目和关联值存储在哈希表的第一组桶内的第一候选桶中。在一些实现方式中，哈希表逻辑对第二键执行第二哈希操作，其中偏置第二哈希操作以将第二键和关联值映射到哈希表的第二组桶内的第二候选桶，所述第二组桶用作一组不经常访问的桶；以及将第二键的条目和关联值存储在哈希表的第二组桶内的第二候选桶中。响应于对键的查找请求，在某些实现方式中，哈希表逻辑在第一组经常访问的桶中执行所请求键的哈希表查找，如果未找到所请求键，则在不经常访问的桶集合中执行所请求键的哈希表查找。在其他实现方式中，通过并行使用哈希函数和两组桶来执行查找。

在某些示例中，计算装置偏置第一和第二哈希操作，使得第一哈希操作将第一键和关联值排他地映射到哈希表的用作所述一组经常访问的桶的第一组桶，并且使得第二哈希操作将第二键和关联值排他地映射到哈希表的用作所述一组不经常访问的桶的第二组桶。

在某些示例中，当哈希表的用作不经常访问的桶的第二组桶满时驱逐哈希表条目，然后将哈希后的第二键的条目存储在第二组桶中。可以基于条目的访问频率来选择驱逐的条目，使得将更经常访问的条目从用作不经常访问的桶的第二组桶中驱逐并且将它们移动到用作经常访问的桶的第一组桶。

在一些示例中，哈希表逻辑还包括槽访问计数器结构，所述槽访问计数器结构产生跟踪数据，所述跟踪数据表示已经访问哈希表的第一组经常访问的桶和哈希表的第二组不经常访问的桶内的桶中的每个槽的次数。在某些实现方式中，哈希表逻辑基于跟踪数据将条目从第二组不经常访问的桶移动到第一组经常访问的桶，且反之亦然。

在某些示例中，哈希表逻辑响应于表条目请求在加权的基础上执行第一和第二哈希操作。在一些示例中，哈希表逻辑存储和使用每桶充满度数据以确定是否在哈希表的第一和第二组桶之间移动哈希表条目。在某些示例中，计算装置包括存储器，所述存储器包括哈希表，并且计算装置包括作为哈希表逻辑操作的一个或多个处理器。

根据一些实现方式，一种非暂时性存储介质包括可执行指令，所述可执行指令在由一个或多个处理器执行时使一个或多个处理器：对第一键执行第一哈希操作，其中偏置第一哈希操作以将第一键和关联值映射到哈希表的用作一组经常访问的桶的第一组桶内的第一候选桶；将第一键的条目和关联值存储在哈希表的第一组桶内的第一候选桶中；对第二键执行第二哈希操作，其中将第二哈希操作偏置以将第二键和关联值映射到哈希表的用作一组不经常访问的桶的第二组桶内的第二候选桶；将第二键的条目和关联值存储在哈希表的第二组桶内的第二候选桶中；以及响应于对键的查找请求，在第一组经常访问的桶中执行所请求键的哈希表查找，如果未找到所请求键，则在不经常访问的桶集合中执行所请求键的哈希表查找。在其他实现方式中，通过并行使用哈希函数和两组桶来完成查找。

在某些示例中，非暂时性存储介质包括可执行指令，所述可执行指令在由一个或多个处理器执行时使一个或多个处理器偏置第一和第二哈希操作，使得第一哈希操作将第一键和关联值排他地映射到哈希表的用作所述一组经常访问的桶的第一组桶，并且使得第二哈希操作将第二键和关联值排他地映射到哈希表的用作所述一组不经常访问的桶的第二组桶。

在某些示例中，非暂时性存储介质包括可执行指令，所述可执行指令在由一个或多个处理器执行时使一个或多个处理器当哈希表的用作不经常访问的桶的第二组桶满时驱逐哈希表条目，然后将哈希后的第二键的条目存储在第二组桶中。可以基于条目的访问频率来选择驱逐的条目，使得将更经常访问的条目从用作不经常访问的桶的第二组桶中驱逐并且将它们移动到用作经常访问的桶的第一组桶。

在一些示例中，非暂时性存储介质包括可执行指令，所述可执行指令在由一个或多个处理器执行时使一个或多个处理器：产生跟踪数据，所述跟踪数据表示已经访问哈希表的第一组经常访问的桶和哈希表的第二组不经常访问的桶内的桶中的每个槽的次数；以及基于跟踪数据将条目从第二组不经常访问的桶移动到第一组经常访问的桶，或反之亦然。

图2示出计算系统的一部分的一个示例，例如硬件服务器、智能手机、可穿戴设备、打印机、膝上型计算机、台式机或使用哈希表的任何其他合适的计算装置的一部分的一个示例。在此示例中，计算装置的部分包括例如高速缓存的存储器200和例如中央处理单元(CPU)、图形处理单元(GPU)、加速处理单元(APU)的处理器的主存储器、专用集成电路(ASIC)，或包括哈希表202和哈希表逻辑204的其他集成电路。哈希表逻辑204与存储器200介接以填充和组织哈希表202。在一个示例中，哈希表逻辑204实现为可编程处理器，所述可编程处理器执行存储在存储器中的可执行指令，所述可执行指令在执行时使处理器作为本文所述的哈希表逻辑操作。在其他实现方式中，哈希表逻辑实现为离散逻辑、一个或多个状态机、现场可编程门阵列(FPGA)或执行指令的处理器和其他硬件的任何合适组合。在此示例中，哈希表逻辑204包括多个哈希生成器206和208、选择器210、控制逻辑212、槽计数结构214、哈希表桶充满度确定器216、桶移动器218和查找逻辑220。将认识到，示出功能块并且可以根据需要组合或分离各种操作。还将认识到，并非在所有实现方式中都需要所有功能块。

在操作中，在填充哈希表202时，哈希表逻辑204从应用程序、计算系统中的服务或其他装置接收键(K)222和关联值(V)以用于输入哈希表202。在将所请求键填充(即，插入)到哈希表202中之后，应用程序或其他实体可以从使用哈希表202的高速缓存请求回存储的值来检索高速缓存的数据。因此，接收到哈希表查找请求224，并且查找逻辑220处理哈希表条目请求以基于哈希表202的使用来检索高速缓存的数据，如下文进一步描述。

还参考图3和图4，根据本文阐述的一个示例结合图2的框图以及哈希表202的示例示出操作的方法300。在一些实现方式中，哈希生成器206实现排他地映射到还被称为不经常访问(IA)的桶集合的一组IA桶(桶3到桶7)的哈希函数，并且哈希生成器208是仅映射到还被称为经常访问(FA)的桶集合(参见图4)的一组FA桶(桶0到桶2)的哈希函数。这些函数的示例如下所示，并使用如图1中所示的作为不同哈希函数的类似命名法。

f1'(x)＝mod(f1(x),N)(其中x是键) 等式1

f2'(x)＝N+mod(f2(x),M) 等式2

等式1示出由哈希生成器208实现的哈希函数f1'(x)的示例，而等式2表示由哈希生成器206提供的哈希函数运算f2'(x)。与图1的系统不同，本文所描述的系统将哈希表的桶分成一组经常访问的桶(桶0到桶2)和一组不经常访问的桶(桶3到桶7)，使得哈希表的第一N个桶对应于FA桶集合228并且剩余的桶M-N划分为不经常访问的桶集合230，其中M是哈希表中的桶的总数。在一些实现方式中，FA桶集合存储在高速缓存中，并且IA桶存储在主存储器或其他存储器中。

再次参考等式1和2，当N和M是2的幂或者可能不是2的幂时，可以实现模运算。哈希生成器206和208提供哈希操作，例如，每个哈希操作分别以某种方式偏置，使得偏置由哈希生成器208提供的哈希操作以将键和关联值映射到哈希表的用作一组经常访问的桶，即FA桶集合228的一组桶，而哈希生成器206对键执行哈希操作并且偏置以将键和关联值映射到分配为不经常访问的桶230(还被称为IA桶集合230)的另一组不同桶。由哈希生成器206生成的哈希键示为H

如框302中所示，所述方法包括对具有关联值(V)的键(K)222执行哈希操作，其中在此示例中，偏置哈希操作以将键222和关联值映射到哈希表的用作一组经常访问的桶，即FA桶集合228的一组桶。因此，在本示例中，控制逻辑212发送选择控制信号232来控制选择器210，以允许将键222传递给哈希生成器208。如框304中所示，哈希生成器208将键222的条目存储在与哈希表中的经常访问的桶集合相对应的FA桶集合228中。例如，这可能在不经常访问的桶集合230满时发生。然而，也可以使用任何其他合适的标准。

如框306中所示，所述方法包括对提供给哈希表逻辑204的另一键(也被称为键222)执行另一哈希操作。偏置另一哈希操作以将键222和关联值映射到哈希表的用作不经常访问的桶集合230的另一组桶。因此，控制逻辑212将选择控制信号232提供给选择器210以将键222提供给哈希生成器206，所述哈希生成器对键执行哈希操作并且如框308中所示，将哈希键的条目存储在哈希表的IA桶集合230中。如框中310所示，响应于来自应用程序或其他服务的哈希表查找请求224，为了从哈希表请求值，所述方法包括在经常访问的桶集合228中执行所请求键的哈希表查找。因此，查找逻辑220使哈希生成器208对作为哈希表查找请求224的一部分的所接收键执行哈希，如哈希生成请求238所示，并且查找逻辑220在经常访问的桶集合228中搜索哈希键。如果未找到所请求键，则如哈希生成请求241所示，查找逻辑220请求哈希生成器206生成键的哈希，然后查找逻辑220在另一桶集合，即不经常访问的桶集合230中搜索所述哈希。将认识到，本文所描述的操作可以任何合适的顺序进行，包括并行或根据需要的任何其他不同顺序。如果最初在经常访问的桶集合228中找到键，则查找逻辑220检索值240并响应于哈希表查找请求224提供包括检索到的值240的哈希表回复242。查找逻辑220根据需要为每次查找执行哈希表检索。

如上面关于等式1和2所指出，哈希生成器206和208通过由相应哈希生成器执行的哈希函数偏置。例如，一个哈希操作排他地将键和关联值映射到哈希表的用作一组经常访问的桶的一组桶。另一哈希生成器被配置成使得哈希操作排他地将键和关联值映射到哈希表的用作一组不经常访问的桶的另一组桶。

可以采用许多不同的哈希表插入技术。在一些实现方式中，总是对不经常访问的桶集合230执行插入到哈希表202中，除非当候选的不经常访问的桶满时。当候选IA桶满时，使用布谷鸟驱逐来实现插入到IA桶中。在其他实现方式中，如果候选IA桶是满的，则控制逻辑212控制选择器210以插入到FA桶集合228中。在其他实现方式中，基于启发式(例如整个表或IA桶的充满度)使用两种方法的混合。在一些示例中，当候选桶是满的并且IA桶集合230上的总负载比FA桶集合228上的总负载高设定余量时执行插入到FA桶中，否则使用布谷鸟驱逐来插入到IA桶中。

在其他实现方式中，在静态或动态确定的概率分布基础上，在控制逻辑212的控制下执行插入到IA桶集合230和FA桶集合228两者中。在一些实现方式中，随机数生成器用于为每次插入确定是否切换选择器以使哈希生成器206或哈希生成器208执行哈希操作并将哈希键和关联值放置在FA桶集合228或IA桶集合230中。

在另一个示例中，执行访问跟踪。例如，查找逻辑220或槽计数结构214产生跟踪数据400，所述跟踪数据表示已经访问哈希表的所述一组经常访问的桶和哈希表的所述一组不经常访问的桶内的桶中的每个槽的次数。在一种实现方式中，元数据用作跟踪数据400并且存储在哈希表202内。在其他实现方式中，例如槽计数器的槽访问计数器结构214产生跟踪数据400。在此示例中，计数器与哈希表中的每个槽相关联，以标识每个槽的访问频率。为了减少容量开销，计数器可以被限制为少量位，例如每个计数器两个或三个位，并且一旦达到最大值，允许饱和而不是溢出。在一个示例中，将例如访问计数器超过阈值的槽的数据项从IA桶集合230中的不经常访问的桶移动到经常访问的桶集合228中的桶。例如，这可以使用经常访问的映射函数来完成。在一些示例中，映射可能类似于新插入到经常访问的桶集合中，例如在经常访问的集合中利用布谷鸟驱逐。

在一些实现方式中，周期性地重置计数器，以确保仅访问频率足以达到计数器重置之间的阈值的项被标识为经常访问。在其他实现方式中，将不再经常访问的项重新映射回到不经常访问的桶集合。如果太多槽或没有足够的槽被标识为经常访问，这表现为FA桶集合与IA桶集合之间的占用率存在很大差异，则更改阈值或计数器重置频率以改变视为经常访问的标准。这可以由查找逻辑220执行。在使用计数器结构的情况下，可以将另一数据结构视为硬件或软件管理的高速缓存，其中仅保留经常访问的项子集的计数器。访问频率不足以使其计数器保留在计数器高速缓存中的任何项都可以被视为不经常访问。然而，可以采用任何合适的计数机制。

对于访问行为不会随时间快速变化的数据集，访问频率跟踪仅需要周期性地进行，而无需一次全部执行。一旦已经收集足够的配置文件信息，就可以暂停进一步的访问跟踪，以避免此种跟踪的性能开销。在其他示例中，访问跟踪仅以概率方式执行，其中跟踪开销仅发生在一小部分查找上。

在某些实现方式中，在查找期间，总是首先使用经常访问的映射函数来查找项。如果在FA候选桶中没有找到所述项，则使用IA映射函数在IA桶集合中查找。尽管与先前系统相比，这会增加高速缓存访问的次数，但对于IA桶中的元素(例如，由于首先检查FA桶)，所述方法可以减少数据集的主存储器访问次数，其中大多数查找针对小子集(例如，一些形式的社交网络数据)。同样如上所示，使用两个映射哈希函数，但是可以使用任何合适的数量。例如，可以使用两个IA映射函数，并且可以使用一个FA映射函数，或者可以使用任何合适数量的哈希函数。

在其他实现方式中，例如针对与FA桶的查找并行发出的IA桶的存储器读取，可以采用不同的查找方法，使得IA桶的存储器访问延迟与检查FA桶重叠。与其他实现方式相比，这可以改进延迟。

哈希表桶充满度确定器216在每个桶级别上确定哪些桶是满的，并且在另一个示例中，在每个桶集合级别上和/或确定哪个桶集合是满的。控制逻辑212例如在IA桶满时通知桶移动器218驱逐哈希表条目，然后将所述条目存储在第二组桶中。哈希表桶充满度确定器216向控制逻辑提供桶充满度数据250，所述桶充满度数据指示哪些桶是满的和/或桶集合是否满。将认识到，所描述的功能块可以根据需要与其他功能块组合或以其他方式变化。

图5是示出用于将哈希表条目插入哈希表中的方法500的一个示例的流程图。将认识到，所描述的操作可以任何合适的顺序执行，并且可以根据需要采用其他操作。在此示例中，首先对不经常访问的集合执行哈希表插入，除非当候选的不经常访问的桶满时。当候选的不经常访问的桶满时，使用布谷鸟驱逐来实现插入到不经常访问的桶中。在一些实现方式中，如果候选的不经常访问的桶是满的，则执行插入到经常访问的桶集合中。还可以基于启发式(例如整个哈希表或IA桶的充满度)使用两种方法的混合。例如，在一些实现方式中，当候选桶是满的并且不经常访问的桶上的总负载比经常访问的桶上的总负载高一定余量时执行插入到经常访问的桶中，否则执行布谷鸟驱逐来插入到IA桶中。

如框501中所示，所述方法包括对键执行哈希操作，将所述哈希操作偏置以将键和关联值映射到哈希表中的用作一组不经常访问的桶的一组桶。如框502中所示，所述方法包括确定候选的不经常访问的桶是否满。在一个示例中，控制逻辑212使用桶充满度数据250来确定是否在哈希表202的IA桶集合230与FA桶集合228之间移动哈希表条目。例如，哈希表桶充满度确定器216跟踪IA桶集合230中的桶3到7中的每一个。如果IA桶集合230中的候选桶是满的，则方法继续到框504，在一个示例中，其中控制逻辑212使哈希生成器208对键执行经常访问的哈希，并且哈希生成器208将键和关联值排他地存储在经常访问的桶集合228中，如框506中所示。在其他实施方案中，如框508中所示，如果不经常访问的桶集合230中的候选桶是满的，但整个不经常访问的桶集合未满，则控制逻辑212在IA桶集合230中执行布谷鸟驱逐。或者，当不经常访问的桶中的所有桶都满时(图5中未示出)，控制逻辑212使桶移动器218将一个或多个条目从IA桶集合230移动到经常访问的桶集合228。因此，当不经常访问的桶满时驱逐哈希表条目，然后将哈希键的条目存储在第二组桶中。

如框510中所示，所述方法包括可能在当哈希表的候选IA桶满时执行哈希表条目的驱逐之后，将哈希键的条目和关联值存储在哈希表的用作不经常访问的桶的桶中。

因此，在查找期间，在某些实现方式中，总是首先使用经常访问的映射函数来查找条目。如果在FA候选桶中没有找到所述条目，则使用IA映射函数查找IA桶。尽管与某些现有技术哈希表查找方法相比，这会增加高速缓存访问的次数，但是所述操作可以减少对数据集的主存储器访问次数，其中大多数查找针对哈希表中的键和值的子集。

图6是示出用于查找哈希表条目的方法600的一个示例的流程图。哈希表逻辑204接收哈希表查找请求224，如框601中所示。如框602中所示，哈希表逻辑204使用哈希生成器208对键(K)222执行哈希操作以标识FA桶集合228中的候选桶，所述哈希操作对应于用于经常访问的桶集合228的哈希。因此，当执行哈希表查找时，在IA桶集合230之前搜索FA桶集合228。例如，响应于哈希表查找请求224，查找逻辑220使用在哈希表查找请求224中接收到的键，并向哈希生成器208提供哈希生成请求238以对键执行哈希操作。如框604中所示，查找逻辑220在FA桶集合228的候选桶中搜索键K。哈希函数标识要在其中搜索的候选桶。一旦标识所述桶，就会在所述桶中搜索原始键。如框606中所示，如果在FA桶集合228中找到键K，则方法继续到框608，其中使对应于键的值从FA桶集合228中的候选桶中适当的槽返回。如框610中所示，对于被访问的槽，使槽计数器递增。

返回到框606且如框612中所示，如果在FA桶集合中没有找到键，则通过使用哈希生成器206执行与不经常访问的桶相关联的哈希操作并搜索不经常访问的桶集合230，重新哈希所述键以产生哈希键(H

图7是示出用于移动哈希表条目的方法700的示例的流程图。如框701中所示，控制逻辑212确定槽访问频率。这通过控制逻辑212评估槽计数器以确定哈希表202中的每个槽的槽计数来完成。如框702中所示，例如，通过控制逻辑将槽访问计数与阈值相比较。如果槽访问计数超过阈值，则哈希表逻辑204使用哈希生成器208将条目移动到经常访问的桶集合228。在一些实现方式中，仅对访问计数超过阈值的IA桶集合中的项执行此移动。如果项已经在FA集合中，则无需移动所述项。因此，控制逻辑212例如通知桶移动器218从IA桶集合中移除条目，并且控制逻辑使哈希生成器208采用排他地映射到FA桶集合的哈希操作。这在框704中示出。例如，系统使用来自槽的键的副本或其表示，所述副本或表示由另一哈希函数，即哈希生成器208所使用的经常访问的哈希函数使用。如框706中所示，所述方法包括将来自槽的键和关联值排他地存储在FA桶集合228中。如果需要，则也可以在必要时在FA桶集合中使用布谷鸟驱逐。如框708中所示，如果槽访问不超过阈值，这意味着槽不被视为经常访问，则使用哈希生成器206将条目移动到IA桶集合。例如，这在项处于FA桶集合中但访问计数低于阈值的情况下进行。控制逻辑212通知桶移动器218将条目从一个桶集合移动到另一桶集合。例如，这可以在FA桶集合中的槽已经在FA桶集合228中移动后没有足够经常地访问FA桶集合中的槽的情况下完成。如框710中所示，所述方法包括将来自槽的键和关联值排他地存储在IA桶集合230中。

图8是示出用于将哈希表条目插入哈希表中的方法800的一个示例的流程图。响应于表条目插入请求，在加权的基础上完成执行与经常访问的桶集合相对应的哈希操作和执行与IA桶集合相对应的哈希操作。例如，如框801中所示，响应于接收到表条目插入请求，控制逻辑212确定接收到的键(K)222处于FA桶集合中的概率。例如，控制逻辑212可以具有与每个哈希映射操作相关联的预存储加权因子，使得在一个示例中，给定应将键放置在FA桶集合228中的概率为10％并且应将键放置在IA桶集合230中的概率为90％因此，使用哈希生成器206将接收用于插入的90％键放置于IA桶集合中，并且使用哈希生成器208将10％所述键放置于FA桶集合228中。如框802中所示，控制逻辑212确定概率是否有利于将键放置在FA桶集合228中。如果不是，则由哈希生成器206对键执行不经常访问的哈希以确定候选桶，如框804中所示。如框806中所示，哈希表逻辑204将键和关联值排他地存储在IA桶集合230中。然而，如果控制逻辑212确定概率是将接收到的键放置在FA桶集合228中，如框808中所示，则使用哈希生成器208对键采用经常访问的哈希操作来确定候选桶，并且如框810中所示，哈希表逻辑204将键和关联值排他地存储在FA桶集合228中。可以使用任何合适的概率确定，包括使用随机数生成器来等于50％的概率，或者可以根据需要使用任何其他预定义的概率。

已经发现，所描述的本发明适用于经常访问的数据集在很长一段时间内稳定的数据结构。在所述集合经常更改的情况下，可以将FA桶中的项积极迁移到最近未访问的IA桶。这可以通过定期将此类项迁移回IA桶来主动完成，或者可以在将新项移动到FA桶并需要释放空间时按需完成。可以基于访问跟踪数据确定最近没有经常访问的项。

本文中的一些实现方式在FA桶是前N个桶并且后(M-N)个桶作为IA桶的上下文中呈现。本发明设想并涵盖替代的划分方法。这些替代方案包括使用任何连续的N个桶作为FA桶并将剩余的桶作为IA桶的方法，以及将一组不连续的N个桶作为FA桶并将剩余的桶作为IA桶的方法。类似地，对FA映射函数的要求是它们映射到合适的N个桶(即FA桶)且不限于上述具体实施方案。

此外，上述实现方式讨论FA映射函数排他地映射到FA桶并且IA映射函数排他地映射到IA桶的情况。然而，设想替代实施方案，其中FA映射函数以比IA桶更高的概率映射到FA桶(但不排他地)，并且IA映射函数以比FA桶更高的概率映射到IA桶(但不排他地)。

此外，在一些实现方式中，如果使用跟踪数据，则跟踪数据可以在与数据项相关联的绝对计数的上下文中。然而，可以设想替代实施方案，其中频率跟踪通过例如布隆过滤器的近似数据结构来完成。例如，当第一次访问时，项的键可能在布隆过滤器中标记为已访问，并且在随后的访问中，如果已在布隆过滤器中找到所述项，则所述项可被视为经常访问的。虽然这可能会导致误报，但这是可以接受的，因为这是一种性能优化且不会影响正确性。在此变体中，可以周期性地重置布隆过滤器，以确保仅在已知和有界时间间隔内的重复访问才被视为经常访问。或者，例如计数布隆过滤器的更复杂的近似集合成员跟踪结构可以用于保持近似的访问计数(而不仅仅是之前至少访问一次项的事实)并强制执行阈值访问次数，超过所述阈值的项被视为经常访问。

可以通过使用用于确定重复项的其他形式的算法来提供访问跟踪数据。例如，存在可以提供项序列(例如，在本发明的情况下，访问的项序列)内的最常见项的近似值的现有技术。此类方法还可以用于定期标识最近访问最经常的项并将它们重新映射到FA桶。

将认识到，将项放置在IA桶集合或FA桶集合中是一种性能优化且不会影响正确性。因此，任何给定的实现方式都可以将本文所讨论的任何优化视为尽力而为。例如，如果将标识为经常访问的数据项移动到FA集合中会导致布谷鸟驱逐，则实现方式可以决定不执行所述移动以避免驱逐的开销。或者，此移动可能会调用布谷鸟驱逐，但可以通过将元素移动到IA集合以在某个阈值驱逐次数处终止驱逐链，即使经常访问所述元素。

在一些实现方式中，本发明在哈希表的上下文中描述，其中布谷鸟哈希作为示例起点。然而，本发明适用于支持多个映射函数的任何哈希表。此外，本发明还适用于依赖于使用一个或多个确定性函数将数据项映射到一组桶的其他数据结构，例如哈希图和其他集合成员数据结构，包括近似集合成员数据结构。

图9示出使用具有FA桶集合和IA桶集合的哈希表的计算系统900的实施方案。通常，计算系统900体现为许多不同类型的装置中的任一种，包括但不限于膝上型计算机或台式计算机、移动装置、服务器、网络交换机或路由器、片上系统、集成电路、多封装装置等。在此示例中，计算系统900包括通过总线901彼此通信的许多组件902-908。在计算系统900中，组件902-908中的每一个都能够直接通过总线901或者经由其他组件902-908中的一个或多个与任何其他组件902-908通信。计算系统900中的组件902-908包含在单个物理外壳内，例如膝上型或台式计算机机架或移动电话壳体，或在一些实现方式中为片上系统或其他配置。在替代实施方案中，计算系统900的一些组件体现为外围装置，使得整个计算系统900不驻留在单个物理外壳内。

在一些实现方式中，计算系统900还包括用于从用户接收信息或向用户提供信息的用户接口装置。具体地，计算系统900包括输入装置902，例如键盘、鼠标、触摸屏或用于从用户接收信息的其他装置。计算系统900经由例如监测器、发光二极管(LED)显示器、液晶显示器或其他输出装置的显示器905向用户显示信息。然而，不需要采用此类装置。

在某些实现方式中，计算系统900另外包括用于通过有线或无线网络传输和接收数据的网络适配器907。计算系统900还包括一个或多个外围装置908。外围装置908可以包括大容量存储装置、位置检测装置、传感器、输入装置、或由计算系统900使用的其他类型的装置。

计算系统900包括处理单元904。处理单元904接收并执行存储在主存储器906中的指令909。在一个实施方案中，处理单元904包括驻留在共用集成电路衬底上的多个处理核心。存储器系统906包括由计算系统900使用的存储器装置，例如随机存取存储器(RAM)模块、只读存储器(ROM)模块、硬盘和其他非暂时性计算机可读介质。一些存储器装置用作处理单元904的存储器200。

在某些实施方案中，例如存储器906的非暂时性存储介质包括可执行指令，所述可执行指令当由例如处理单元904的一个或多个处理器执行时使所述一个或多个处理器对键执行哈希操作，其中排他地配置或偏置哈希操作以将键以及其关联值映射到哈希表的用作一组经常访问的桶(还称为FA桶集合)的一组桶。在一些实现方式中，哈希表的FA桶集合的大小被设定为适合高速缓存。在一些实现方式中，存储介质包括可执行指令，所述可执行指令当由一个或多个处理器执行时使一个或多个处理器将哈希键的条目存储在哈希表中的FA桶集合中。在某些实现方案中，存储介质包括可执行指令，所述可执行指令当由一个或多个处理器执行时使所述一个或多个处理器对键执行不同的哈希操作，所述键可以是相同或不同键，其中偏置哈希操作以将键和关联值映射到哈希表的用作一组不经常访问的桶(还被称为IA桶集合)的一组桶，并且将哈希键的条目存储在哈希表的IA桶集合中。响应于对键的查找请求，一个或多个处理器在经常访问的桶集合中执行所请求键的哈希表查找，如果未找到所请求键，则在不经常访问的桶集合中执行所请求键的哈希表查找。

在一些实现方式中，非暂时性存储介质存储可执行指令，所述可执行指令在由一个或多个处理器执行时使一个或多个处理器偏置哈希操作，使得第一哈希操作中的一个将键和关联值排他地映射到经常访问的桶集合，并且另一个哈希操作将键和关联值映射到不经常访问的桶集合。在一些实现方式中，存储介质存储可执行指令，所述可执行指令使一个或多个处理器如参考图2到图8所描述操作。

计算系统900的一些实施方案可以包括比图9中所示的实施方案更少或更多的组件。例如，在没有任何显示器905或输入装置902的情况下实现某些实施方案。其他实施方案具有多于一个特定组件；例如，计算系统900的实施方案可以具有多个处理单元904、总线901、网络适配器907、存储器系统906等。

虽然上面以特定的组合描述了特征和要素，但是每个特征或要素可单独使用而无需其他特征和要素，或者以具有或不具有其他特征和要素的各种组合使用。在一些实现方式中，本文提供的设备通过使用并入非暂时性计算机可读存储介质中的计算机程序、软件或固件制造，以便由通用计算机或处理器执行。计算机可读存储介质的实例包括只读存储器(ROM)、随机存取存储器(RAM)、寄存器、高速缓存存储器、半导体存储器装置、例如内部硬盘和可移动磁盘的磁性介质、磁光介质以及例如CD-ROM盘和数字通用光盘(DVD)的光学介质。

在各种实施方案的以上详细描述中，已经参考构成其一部分的附图，并且其中通过图解的方式示出可以实践本发明的特定优选实施方案。以足够的细节描述这些实施方案，以使得本领域技术人员能够实施本发明，并且应理解，可以利用其它实施方案并且可作出逻辑、机械和电气变化而不背离本发明的范围。为了避免并非使本领域技术人员能够实践本发明所必需的细节，所述描述可以省略本领域技术人员已知的某些信息。此外，本领域技术人员可以容易地构建包含本公开的教导的许多其他变化的实施方案。因此，本发明不旨在限于本文所阐述的特定形式，而是相反，本发明旨在涵盖可以合理地包括在本发明范围内的此类替代、修改和等同物。因此，前面的详细描述不被视为具有限制性意义，并且本发明的范围仅由所附权利要求限定。对实施方案和其中描述的示例的以上详细描述仅出于说明和描述的目的而非限制性的目的呈现。例如，所描述的操作以任何合适的顺序或方式进行。因此，预期本发明涵盖落入上文所公开和本文所要求保护的基本根本原理范围内的任何和所有修改、变化或等同物。

已仅出于说明和描述的目的而非限制性的目的呈现以上详细描述和本文所描述的示例。