用于基于阵列的数据存储和搜索的系统及方法

摘要

本发明涉及一种用于基于阵列的数据存储和搜索的系统及方法。提供了用于有效地产生和更新排序的阵列以用于快速数据访问的计算机设备和方法。该阵列分配比其所存储的元素所需的空间更多的空间。换句话说，阵列在元素之间留下空的空间，使得对新元素的插入仅需移动阵列中的少量现有元素，或者甚至不移动阵列中的现有元素。

权利要求

1.一种在阵列中插入输入数据元素的方法，包括：

a)计算机处理器将阵列加载到计算机可读存储器中，其中所述阵列的大小为B，用于存储最多B个数据元素，其中，所述阵列包含T个数据元素，其中所述数据元素在所述阵列中被排序，使得所述阵列中的任何不是空的位置包含的数据元素比所有存储在左侧的位置中的数据元素大，且比所有存储在右侧的位置中的数据元素小；

b)在所述阵列中确定小于所述输入数据元素的所有数据元素中最大的第一数据元素、和大于所述输入数据元素的所有数据元素中最小的第二数据元素，其中，所述第一数据元素和所述第二数据元素彼此相邻或者被所述第一数据元素和所述第二数据元素之间的一个或多个空位置分隔；以及c)i)如果所述第一数据元素和所述第二数据元素处于相邻的位置，则将所述第一数据元素和所有左侧相邻的数据元素向左侧移动一个位置，然后将所述输入数据元素放置到所述第一数据元素空出的位置中，或者将所述第二数据元素和所有右侧相邻的数据元素向右侧移动一个位置，然后将所述输入数据元素放置到所述第二数据元素空出的位置中，或者ii)将所述输入数据元素放置到所述第一数据元素和所述第二数据元素之间的位置中，其中，当比值f＝T/B大于预定的阈值时，通过将用于L－B个附加位置的内存分配给所述阵列来将所述阵列的大小扩大至L。

2.根据权利要求1所述的方法，其中，B至少比T大20％。

3.根据权利要求1所述的方法，其中，所述第一数据元素和所述第二数据元素被至少三个空位置分隔，且所述输入数据元素被放置到所述空位置中的中间位置中。

4.根据权利要求1所述的方法，其中，所述预定的阈值在0.5和0.9之间。

5.根据权利要求1所述的方法，其中，移动所述阵列中的一个或多个数据元素，使得所述述阵列中的空位置分布得更均匀。

6.根据权利要求1所述的方法，其中，针对一个或多个新的输入数据元素重复步骤b)和步骤c)。

7.根据权利要求6所述的方法，其中，针对不同的输入数据元素，步骤i)和步骤ii)都被执行。

8.根据权利要求1所述的方法，其中，在第二索引阵列的位置p插入值i，其中p是所述输入数据元素的散列函数输出，i是所述输入数据元素在所述阵列中的位置。

9.根据权利要求8所述的方法，其中，所述阵列和所述第二索引阵列的长度相同。

10.根据权利要求8所述的方法，其中，所述散列函数针对所述阵列中的每个数据元素产生唯一的非负整数值。

11.一种用于将输入数据元素插入阵列中的计算机系统，包括处理器和存储器，所述存储器存储程序指令，所述程序指令当由所述处理器执行时，使所述系统配置成：a)将阵列加载到存储器中，其中所述阵列的大小为B，用于存储最多B个数据元素，其中，所述阵列包含T个数据元素，其中所述数据元素在所述阵列中被排序，使得所述阵列中的任何不是空的位置包含的数据元素比所有存储在左侧的位置中的数据元素大，且比所有存储在右侧的位置中的数据元素小；

b)在所述阵列中确定小于所述输入数据元素的所有数据元素中最大的第一数据元素、和大于所述输入数据元素的所有数据元素中最小的第二数据元素，其中，所述第一数据元素和所述第二数据元素彼此相邻或者被所述第一数据元素和所述第二数据元素之间的一个或多个空位置分隔；以及c)i)如果所述第一数据元素和所述第二数据元素处于相邻的位置，则将所述第一数据元素和所有左侧相邻的数据元素向左侧移动一个位置，然后将所述输入数据元素放置到所述第一数据元素空出的位置中，或者将所述第二数据元素和所有右侧相邻的数据元素向右侧移动一个位置，然后将所述输入数据元素放置到所述第二数据元素空出的位置中，或者ii)将所述输入数据元素放置到所述第一数据元素和所述第二数据元素之间的位置中，其中，当比值f＝T/B大于预定的阈值时，通过将用于L－B个附加位置的内存分配给所述阵列来将所述阵列的大小扩大至L。

12.一种从阵列中删除查询数据元素的计算机系统，包括处理器和存储器，所述存储器存储程序指令，所述程序指令当由所述处理器执行时，使所述系统配置成：a)访问包含T个数据元素的阵列，其中所述阵列的大小为B，用于存储最多B个数据元素，所述数据元素在所述阵列中被排序，使得所述阵列中的任何不是空的位置包含的数据元素比所有存储在左侧的位置中的数据元素大，且比所有存储在右侧的位置中的数据元素小；

d)确定所述阵列中包含与所述查询数据元素相同的数据元素的位置；以及c)将所述位置标记为空，其中，所述程序指令还使所述系统配置成：当比值f＝T/B小于预定的阈值时，移动所述阵列中的数据元素，使得所述阵列的一端具有一个或多个空位置，并从所述阵列中删除所述空位置，从而减小所述阵列的大小。

13.根据权利要求12所述的计算机系统，其中，所述预定的阈值在0.1和0.7之间。

14.根据权利要求12所述的计算机系统，其中，在所述一端的所述空位置的数量为B的至少10％。

说明书

用于基于阵列的数据存储和搜索的系统及方法

背景技术

[0001] 在计算机系统中阵列是常见的、有用的、和重要的用来存储和处理数据的数据结构。阵列是在同一名称下组合的一组连续的内存位置，其中每个单独的位置经由其索引或下标访问。在计算机科学中，阵列通常用于实现静态查找表以保存具有相同数据类型的多个值。对阵列进行排序可用于以有序的形式组织数据和迅速获得这些数据。

[0002] 排序的阵列中的元素使用以O(log n)表示的二分搜索来查找；因此，排序的阵列适用于需要能够快速查找元素的情况。查找的复杂度与自平衡二叉搜索树的复杂度相同。

[0003] 然而，已知在排序的阵列中插入和删除元素是成本高的。在排序的阵列中插入和删除元素以O(n)执行。这是因为需要对待插入或待删除的元素以后的所有元素进行移动。相比之下，自平衡二叉搜索树以O(log n)进行插入和删除。

[0004] 例如，当建立含有n个元素的新的排序的阵列时，用于将所有n个元素一个接一个插入到阵列中的成本为O(n2)。当n大时，成本非常高且使得常规阵列无法用于存储排序的数据元素。

[0005] 然而，阵列是简单的且具有良好的局部引用性。在现代计算机系统中，阵列能利用高速缓存存储器来发挥其高性能。

发明内容

[0006] 本公开提供了用于创建和使用排序的阵列的计算机系统和方法，该排序的阵列被快速搜索且也快速形成和更新。在本发明的计算机系统和方法中实现的新的数据结构被称为“排序的弹性阵列”(SEA)。SEA分配比实际存储的元素更多的阵列单元，但并不包含如在二叉搜索树或多路树中的所有指针，因此其存储效率仍然高效。更重要的是，它将插入操作从O(n)改进为O(log n)。

[0007] 因此，在一个实施方式中，提供了一种用于将输入数据元素插入阵列中的计算机系统，包括处理器、存储器和程序指令，所述程序指令当由处理器执行时，配置所述系统以便：(a)将阵列加载到存储器中，其中所述阵列的大小为B用于存储最多B个数据元素，其中，所述阵列包含T个数据元素，其中所述数据元素在所述阵列中被排序，使得所述阵列中的任何不是空的位置包含的数据元素比所有存储在左侧的位置中的数据元素大，且比所有存储在右侧的位置中的数据元素小；(b)在所述阵列中确定小于所述输入数据元素的所有数据元素中最大的第一数据元素、和大于所述输入数据元素的所有数据元素中最小的第二数据元素，其中，所述第一数据元素和所述第二数据元素彼此相邻或者被所述第一数据元素和所述第二数据元素之间的一个或多个空位置分隔；以及(c)(i)如果所述第一数据元素和所述第二数据元素处于相邻的位置，则将所述第一数据元素和所有左侧相邻的数据元素向左侧移动一个位置，然后将所述输入数据元素放置到所述第一数据元素空出的位置中，或者将所述第二数据元素和所有右侧相邻的数据元素向右侧移动一个位置，然后将所述输入数据元素放置到所述第二数据元素空出的位置中，或者(ii)将所述输入数据元素放置到介于所述第一数据元素和所述第二数据元素之间的位置中。

[0008] 在一些方面，B至少比T大20％。在一些方面，所述第一数据元素和所述第二数据元素被至少三个空位置分隔，且所述输入数据元素被放置到所述空位置中的中间位置中。

[0009] 在一些方面，所述程序指令还使所述系统配置成：当比值f＝T/B大于预定的阈值时，通过将用于L－B个附加位置的内存分配给所述阵列来将所述阵列的大小扩大至L。在一些方面，所述预定的阈值在0.5和0.9之间。

[0010] 在一些方面，所述程序指令还使所述系统配置成移动所述阵列中的一个或多个数据元素，使得所述述阵列中的空位置分布得更均匀。

[0011] 在一些方面，所述程序指令还使所述系统配置成针对一个或多个新的输入数据元素重复步骤(b)和步骤(c)。在一些方面，针对不同的输入数据元素，步骤(i)和步骤(ii)都被执行。

[0012] 在一些方面，所述程序指令还使所述系统配置成在第二索引阵列的位置p插入值i，其中p是所述输入数据元素的散列函数输出，i是所述输入数据元素在所述阵列中的位置。在一些方面，所述阵列和所述第二索引阵列的长度相同。

[0013] 在一些方面，所述散列函数针对所述阵列中的每个数据元素产生唯一的非负整数值。

[0014] 在一个实施方式中，还提供了一种从阵列中删除查询数据元素的计算机系统，包括处理器、存储器和程序指令，所述程序指令当由所述处理器执行时，使所述系统配置成：(a)访问包含T个数据元素的阵列，其中所述阵列的大小为B用于存储最多B个数据元素，所述数据元素在所述阵列中被排序，使得所述阵列中的任何不是空的位置包含的数据元素比所有存储在左侧的位置中的数据元素大，而比所有存储在右侧的位置中的数据元素小；(d)确定所述阵列中包含与查询数据元素相同的数据元素的位置；以及(c)将所述位置标记为空。

[0015] 在一些方面，所述程序指令还使所述系统配置成：当比值f＝T/B小于预定的阈值时，移动所述阵列中的数据元素，使得所述阵列的一端具有一个或多个空位置，并从所述阵列中删除所述空位置，从而减小所述阵列的大小。在一些方面，所述预定的阈值在0.1和0.7之间。在一些方面，在所述一端的所述空位置的数量为B的至少10％。

附图说明

[0016] 作为本公开的实施方式，仅以示例性而非限制性的方式提供了附图，其中：

[0017] 图1是示出包含四个数据元素和五个空阵列单元的存储单元阵列的示意图；

[0018] 图2是示出包含到外部数据元素的四个引用和五个空阵列单元的存储单元阵列的示意图；

[0019] 图3是示出将弹性阵列从长度B调整(增大)到长度L的示意图；

[0020] 图4是示出将来自旧的阵列的元素重映射到新的阵列后阵列元素的大小和位置的示意图；以及

[0021] 图5是示出弹性阵列中的数据元素和对应的索引散列元素的示意图。

[0022] 应当认识到，这些图中的一些或全部是示例性的示意图，因此，这些图并不一定反映示出的元素的实际相对大小或位置。这些图为了清晰地说明一个或多个实施方式的目的而给出，并不用来限制以下给出的权利要求的范围或含义。

具体实施方式

[0023] 本公开提供了采用用于快速数据访问和存储的排序的阵列的计算机系统和方法。如上所述，更新传统的排序的阵列是成本高的，这是因为根据新的元素应当所要插入的位置，插入每个新的元素需要对阵列中现有元素的大约一半进行移动。然而，在一个实施方式中，本发明的技术提供了分配比其所存储的元素所需要的空间更多的空间(即阵列中的位置或单元)的排序的阵列。也就是说，该阵列在元素之间留下空的空间，使得插入新的元素需要移动少量现有元素或者甚至不移动现有元素。由于这样的阵列能够容纳新的元素而不需要在每次插入时都增加其大小，因此该阵列也被称为“排序的弹性阵列(SEA)”。

[0024] 即使需要增加存储空间，由于该阵列具有更大的尺寸以包含空位置，与保存有相同数量的元素的二叉树相比，SEA还需要更少的内存。例如，假设SEA包含T个元素但包含B个位置(或“空间”、“储存区”、“单元”或“槽”)用于保存元素，并假设B是T的约两倍(即B＝2T)，则SEA仅需要足够的存储空间用于保存2T个元素。为了保存相同数量(T)的元素，二叉树将需要T个节点加上至少2×T个指针或引用以将这些节点连成树；因此，总的内存至少为3T，不算可能比简单的数据元素占用更多的存储空间的指针。

[0025] 然而，由于需要更小的存储空间，对SEA的搜索和更新与二叉树具有相同的成本效益，如下文更详细地描述。因此，在存储空间要求和运行效率方面，本发明的技术优于基于二叉树的技术。

[0026] 负载因子

[0027] 本公开的SEA例如包括索引为0,1,…B-1的B个位置。在特定时刻，SEA包含总共T个实际存储的元素，其中T＜B。

[0028] 假设T个元素随机分布在B个存储单元中。一个存储单元将包含t个数据元素的概率由以下二项式分布给出：

[0029]

[0030] 当T和B都大时，即T>>1,B>>1，二项式概率可近似为泊松分布：

[0031] P(t)～＝(T/B)te-T/B/t！＝fte-f/t！

[0032] 其中f＝T/B表示“负载因子”，以及e为指数函数。

[0033] t的统计平均值由泊松分布的E(t)表示：

[0034] E(t)＝f

[0035] 且标准偏差为：

[0036]

[0037] 从上面的公式可以看出，当负载因子f减小时，包含在一位置中的数据元素的平均数也下降。当负载因子f为0.5时，平均每两个存储单元将包含仅一个元素且标准偏差仅为0.71，其是窄的范围。

[0038] 在插入或删除操作过程中，如果负载因子超出了(太大或太小)预期的范围，该阵列可以被扩大或缩小，以保持对于阵列最优的负载因子。

[0039] 排序的弹性阵列的创建和元素的插入

[0040] 以包含从左到右按升序排列的元素的阵列为例。然而，应当理解，方向“左”和“右”并不受限制，因为只是为了便于说明而使用它们作为相对的术语。

[0041] 在步骤1中，本公开的计算机系统为初始阵列分配大小为B的内存，B是非零整数。该系统标记该阵列中的所有位置为空。

[0042] 在步骤2中，第一个元素被插入到初始阵列中的任何位置，优选中心位置。

[0043] 在步骤3中，插入新的元素。首先，在当前阵列中进行二分搜索，从而为待插入的新的元素找到合适的位置p，以保留该阵列中的所有元素的顺序。换句话说，p在紧接地小于该新元素的元素(即小于新元素的所有元素中最大的元素)的右侧且在紧接地大于该新元素的元素(即大于新元素的所有元素中最小的元素)的左侧。

[0044] 在二分搜索期间，第一指针、最后的指针、和中间点的指针可能偶尔指向空单元。在这种情况下，将它们移动到下一个非空的位置。一旦找到正确的位置，按照如下插入新的元素。

[0045] 如果在位置p的单元是空的且两侧是两个非空的位置，每个非空的位置由两个直接相邻的元素占据，则直接将新的元素插入到由p指向的位置。

[0046] 如果在位置p的单元不是空的，或者换句话说，两个直接相邻的元素占据彼此紧挨的位置且两者之间没有空位置，则该阵列将这两个元素中的一个元素沿着其相应的侧进一步移动。有时，这两个元素中的任一者或两者的直接下游(进一步沿着左侧或右侧)没有空位置，使得移动它们中的任一者将需要移动所有直接下游元素。因此，在这方面，优选其移动需要移动较少数量的直接下游元素的元素。

[0047] 有时，新的元素可以小于或大于所有现有元素，因此新的元素将被插入到阵列的一端(最左侧或最右侧)的任何空位置。然而，该新的元素优选被插入到该端的连续空位置的中心位置。在一些方面，该新的元素可以被插入，空隙的宽度等于1/f(负载因子的倒数)。

[0048] 在移动元素的过程中，如果待移动的元素的数量超过预定的阈值，且存在足够数量的紧邻这些元素的空单元，则该阵列将这些元素分散到这些空单元中，使得这些元素之间有空隙(空位置)。在一个方面，预定的阈值为3、4、5、6、7、8、9或10，或为阵列大小(B)的约1％、约2％、约3％、约4％、约5％、约10％或约15％。

[0049] 在当前阵列中的元素的数量超过预定的阈值(由负载因子f确定)时，可通过分配更多的内存来扩大当前阵列或由尺寸更大的新阵列替换当前阵列。新阵列的尺寸由L(见图3)表示，扩大因子由g表示，因此L＝gB，其中B为旧尺寸。新阵列中不使用的单元标记为空。
在一些方面，f的预定阈值为至少0.5，或为至少0.5、至少0.55、至少0.65、至少0.7、至少
0.75、至少0.8、至少0.85或至少0.9。在一些方面，f的预定阈值不大于0.95、不大于0.9、不大于0.85或不大于0.8。在一些方面，g为至少1.1、至少1.2、至少1.3、至少1.4、至少1.5、至少1.6、至少1.7、至少1.8、至少1.9或至少2。在一些方面，g不大于2.5、不大于2.4、不大于
2.3、不大于2.2、不大于2.1、不大于2、不大于1.9、不大于1.8、不大于1.7、不大于1.6或不大于1.5。

[0050] 一旦阵列被扩大，它可以被重新映射，使得该阵列中的元素在新阵列中分布得更均匀(见图4)。在一些方面，重映射过程从该阵列中最右侧的元素开始以避免重写和数据丢失。

[0051] 元素的删除

[0052] 元素的删除可通过在一位置识别该元素并标记该位置为空来实现。不需要额外的操作，如移动，因为本公开的阵列允许空位置。

[0053] 在新的负载因子变得小于阈值的情况下，元素可被重映射(移动)到较窄的范围，以在阵列的任一端留下连续数量的空位置。通过对这些空位置的删除，新的缩小的阵列将具有增大的负载因子。在一些方面，f的预定阈值为至少0.1，或为至少0.2、至少0.3、至少0.4、至少0.5、至少0.55、至少0.65、至少0.7、至少0.75、至少0.8、至少0.85或至少0.9。在一些方面，f的预定阈值不大于0.95、不大于0.9、不大于0.85、不大于0.8、不大于0.75或不大于0.7。新阵列的尺寸由S表示，扩大因子由g表示，因此B＝gS，其中B为旧尺寸。在一些方面，g为至少1.1、至少1.2、至少1.3、至少1.4、至少1.5、至少1.6、至少1.7、至少1.8、至少1.9或至少2。在一些方面，g不大于2.5、不大于2.4、不大于2.3、不大于2.2、不大于2.1、不大于2、不大于1.9、不大于1.8、不大于1.7、不大于1.6或不大于1.5。

[0054] 最坏的情况

[0055] 在创建新的SEA时，当输入元素被预排序时会出现最坏的情况。在这种情况下，新的元素总是被添加到阵列的右端或左端，最终主要进行移动操作，SEA表现得像常规排序的阵列。在这种情况下，插入的成本为O(N)。

[0056] 为了避免最坏的情况，可以保持有序性测量，即Ω，以测量输入元素的有序度。为了量化测量，当输入元素全部升序时使Ω＝1；当输入元素全部降序时使Ω＝-1；当输入元素随机进入系统时使Ω＝0。设计有序性Ω的一个实施方式为：

[0057] Ω＝(Si–Sd)/N

[0058] 其中Si是输入元素大于其前一个输入元素的累积计数，Sd是输入元素小于其前一个输入元素的累积计数。Ω采用范围-1<＝Ω<＝1内的连续值。

[0059] 根据该有序性参数，可以在随机数据输入的情况下修改插入方法。目的是针对升序元素，阵列将现有元素插入并重新映射到该阵列的左端，并将新的元素添加到右端；针对降序元素，可以将现有元素插入并重新映射到该阵列的右端，因此新的元素被插入到左端。

[0060] 两个控制参数可用于修改的重映射：一个是新映射的元素的跨度，记为W；另一个是所有新映射的元素的中心位置，记为C。

[0061] 一个实施方式使用线性模型：

[0062] 使W＝a|Ω|+b，L是新扩大的阵列的大小。符号|Ω|表示Ω的绝对值。在输入元素全部为随机顺序，即Ω＝0的情况下，W应等于L，因此

[0063] L＝a|0|+b；

[0064] 因此，b的解为b＝L。

[0065] 当Ω＝1，即输入元素全部升序时，W可等于阵列(相邻元素之间存在一个空隙)中的元素数量的两倍：

[0066] 2fB＝a+b

[0067] 其中B是旧阵列的大小：L＝gB。

[0068] 可对a进行求解：a＝2fB–b＝(2fL/g)–L＝(2f/g-1)L。

[0069] 现在可以得到W的完整的表达式：

[0070] W＝a|Ω|+b＝(2f/g–1)L|Ω|+L＝[(2f/g-1)|Ω|+1]L

[0071] 对于参数C，也可使用线性模型：

[0072] 假设C＝aΩ+b

[0073] 当Ω＝0时，使C等于L/2：则b＝L/2。

[0074] 当Ω＝1时，使C等于阵列中的所有元素：

[0075] C＝T＝fB＝(fL)/g

[0076] 因此a＝C–L/2＝(2f/g-1)L/2

[0077] 现在可以得到C的完整的表达式：

[0078] C＝[(2f/g-1)Ω+1]L/2

[0079] 从W和C获得的参数是新映射的元素的开始位置：

[0080] S＝C–W/2

[0081] ＝[(1-2f/g)(|Ω|-Ω)]L/2

[0082] 新映射的元素的结束位置为：

[0083] E＝C+W/2

[0084] ＝L-[(1-2f/g)(|Ω|+Ω)]L/2

[0085] 因此，针对Ω的任何值，可以将元素均匀分布至新调整大小的阵列的范围[S，E]。

[0086] SEA中的数据类型

[0087] 本公开的SEA可用来存储可被排序的任何数据类型。例如，SEA中的数据元素可以是查询键、键和值对、或任何其它数据类型。图1示出了包含四个数据元素和五个空位置，总共九个位置的SEA。存储的元素e1至e4可以是端数据，例如数字。在一些方面，存储在这些位置的数据元素为数字、字符串或数据块，没有限制。

[0088] 在另一方面，这些元素可以是引用其它值(e1至e4)的键(图2中的r1至r4)。如果存储了引用，跟随该引用可以获得实际的数据。移动操作可能仅涉及对引用而非实际的数据的操作。

[0089] 查找散列表(索引阵列)

[0090] 可以保持查找散列表用以在阵列中快速查找键。散列表的大小至少与弹性阵列本身的大小相同(图5)。使用散列表，阵列中的元素可以被编索引，使得可以以O(1)快速访问阵列中的元素。

[0091] 参考图5，SEA(A)包含四个元素a1、a3、a4和a7，其中数字1、3、4和7反映了它们在阵列中的位置。索引阵列(I)也在内存中创建，其长度(即，槽数)Ni大于阵列A中的元素的个数。在一个实施方式中，阵列A和I具有相同的长度。

[0092] 针对阵列A中的每个元素，阵列I在位置p包含该元素对应的整数i。位置p是以元素值作为输入的散列函数的输出。

[0093] 例如，如果hash(a7)＝0，则p为0。则在位置p，所存储的是a7的位置(索引)，即7。

[0094] 因此，当搜索a7时，计算机可以(1)先进行a7的散列函数操作，得到结果0，(2)查找阵列I的位置0，得到值7，(3)在阵列A的位置7找到a7。这样的话，不需要进行二分搜索，这样的搜索成本为O(1)，甚至比传统的阵列更快。

[0095] 为了最大化索引阵列的值，优选地，选择散列函数使得阵列A中的所有元素的散列值为0到L-1的长度之间的整数，且没有重叠。

[0096] 当阵列A中的多个元素被映射到阵列I中的相同位置时，可以采取线性探测来解决散列冲突。当新的元素被插入到阵列A时，新元素也被插入到索引阵列的具有如上所述的值的位置p。

[0097] 这种具有对应的散列函数的索引阵列可以大大提高SEA的性能。例如，在大小为N的弹性阵列中，使用8字节的引用(地址类型)，每个引用可涉及32字节的数据。假设选择0.75作为负载因子阈值(f＝0.75)，2作为扩大因子(g＝2)。没有散列表的存储大小为(0.75N×32+8N)＝32N。加入散列表的开销大小为8N，提供8/32＝25％的额外存储。考虑到键查找的成本效益为O(1)，在一些应用中，25％的额外存储是保证的。

[0098] 计算机系统和网络

[0099] 本文中描述的方法可以在计算机系统或网络中实现。合适的计算机系统可至少包括处理器和存储器；可选地包括存储由处理器执行的计算机代码的计算机可读介质。一旦代码被执行，则计算机系统执行所描述的方法。

[0100] 在这方面，“处理器”是可以执行计算机程序的电子电路。合适的处理器例如但不限于中央处理单元、微处理器、图形处理单元、物理处理单元、数字信号处理器、网络处理器、前端处理器、协同处理器、数据处理器和音频处理器。术语“存储器”是指存储用于检索的数据的电气装置。因此，在一个方面，合适的存储器是保存数据和辅助计算的计算机单元。更普遍地说，用于提供必要的网络数据传输的合适的方法和设备是已知的。

[0101] 还考虑包括用于执行所描述的方法的可执行代码的非暂时性计算机可读介质。在某些实施方式中，该介质还包括该方法所需的数据或数据库。

[0102] 实施方式可包括程序产品，该程序产品包括非暂时性机器可读存储介质，用于携带或具有存储在其上的机器可执行指令或数据结构。这样的机器可读介质可以是可由通用或专用计算机、或其它具有处理器的机器访问的任何可用介质。通过举例的方式，这样的机器可读存储介质可包括RAM、ROM、EPROM、EEPROM、CD-ROM或其它光盘存储器、磁盘存储器或其它磁性存储装置、或任何可用来存储所需的机器可执行指令或数据结构形式的程序代码且可由通用或专用的计算机、或其它具有处理器的机器访问的其它介质。上述的组合也在“机器可读介质”的范围内。例如，机器可执行指令包括使通用计算机、专用计算机或专用处理机器执行特定功能或功能组的指令和数据。

[0103] 本公开的实施方式已在方法步骤的通用上下文中进行了描述，在一个实施方式中，该方法步骤可由程序产品例如以程序模块的形式来实现，该程序产品包括机器可执行指令，如程序代码，该程序模块由网络环境中的机器执行。通常，程序模块包括执行特定任务或实现特定抽象数据类型的例程、程序、逻辑、对象、组件、数据结构等。机器可执行指令、相关数据结构和程序模块代表用于执行本文中公开的方法步骤的程序代码的例子。这样的可执行指令或相关数据结构的特定序列代表用于实现在这样的步骤中描述的功能的对应行为的例子。

[0104] 如前所述，本公开的实施方式可在网络环境中使用到一个或多个具有处理器的远程计算机的逻辑连接来实现。本领域技术人员应当明白，这样的网络计算环境可能包含许多计算机类型，包括个人电脑、手持设备、多处理器系统、基于微处理器的或可编程的消费电子产品、网络计算机、小型计算机、大型计算机等等。本公开的实施方式也可在分布式和云计算环境中实现，在分布式和云计算环境中，任务由本地和远程处理设备来执行，本地和远程处理设备通过通信网络由硬线链路、无线链路、或硬线链路或无线链路的组合来链接。在分布式计算环境中，程序模块可位于本地和远程存储设备中。

[0105] 虽然上述讨论可以涉及方法步骤的特定顺序和组成，应当理解，这些步骤的顺序可能不同于所描述的顺序。例如，两个或两个以上的步骤可以同时执行或部分同时执行。此外，一些作为离散的步骤来执行的方法步骤可以合并，作为合并的步骤执行的步骤可分为离散的步骤，某些过程的顺序可以颠倒或改变，离散过程的性质和数量可以被改变或变化。根据替选实施方式，任何元件或装置的次序或顺序可以被改变或替换。因此，所有这些修改都应包含在本公开的范围内。这样的变化将取决于选择的软件和硬件系统和设计者的选择。应当理解，所有这些变化都在本公开的范围内。类似地，本公开的软件和Web实现可由使用基于规则的逻辑和其它逻辑的标准编程技术来完成，以完成各种数据库搜索步骤、相关步骤、比较步骤和决定步骤。

[0106] 除非另有规定，本文中所使用的所有技术和科学术语的含义与本公开所属领域的普通技术人员普遍理解的含义相同。

[0107] 此处示例性描述的本公开可在缺少此处没有具体公开的任何元件、限制的情况下适当地实现。例如，术语“包括”、“包含”、“含有”等应被可扩展地而非限制地理解。此外，本文中采用的术语和表述用来作为描述的术语而非限制；因此，对这样的术语和表述的使用并不意欲排除示出和描述的特征或其部分特征的任何等同物。相反，应当认识到，在本公开所要求保护的范围内各种修改是可行的。

[0108] 同理，当本公开已由优选的实施方式和可选的特征具体公开时，读者将理解此处体现的主题的修改、改进和变化。这些修改、改进和变化考虑在本公开的范围内。

[0109] 此处已经广泛地且大体地描述了本公开。落入本公开的每个更窄的类型和亚属分组也构成本公开的一部分。这包括具有从该属中去除任何主题的限制性条件或否定限制的本公开的一般描述，不管是否具体描述删除部分。

[0110] 在本公开的特征或方面参考Markush组来描述时，本公开还可根据Markush组的任何单个成员或成员的子组来描述。

[0111] 本文中提及的所有出版物、专利申请、专利和其它参考文献的全部内容通过应用明确并入，与每一者分别通过引用来并入的程度相同。在冲突的情况下，包括定义的本说明将控制。

[0112] 虽然已经结合上述实施方式描述了本公开，上述描述和例子的目的是为了说明而非限制本公开的范围。本公开范围内的其它方面、优点和修改对于本公开所属领域的技术人员来说是显而易见的。