摘要

在本文中，我们展示了一些具有某些所需属性的新类散列函数，并介绍了两种利用这些函数进行散列的新应用。 一个类包含少量功能，但几乎是通用的。 如果函数将n位长名称散列为m位索引，那么指定类的成员只需要 位与O（ n）复杂度的早期技术的比特相比。 对于长名称，这大约比m + log，n -log，m位的下限大m倍。 此类的应用程序是一种可证明安全的身份验证技术，通过不安全的行发送消息。 第二类函数满足比通用更强的属性。 我们提出了相等的测试集的应用。

验证技术允许接收器确定消息是真实的。 “敌人” - 即使拥有无限计算机资源的人 - 无法在未经检测的情况下伪造或修改消息。 集合相等技术允许在预期的恒定时间内以小于指定的错误概率执行包括“添加成员来设置”，“从集合中删除成员”和“测试两个集合以进行相等”的操作。

介绍

散列函数是从较大域映射到较小范围的函数，它们可以被视为将缩写分配给名称的方法。散列函数的期望属性是“大部分时间”，当两个量的散列值相同时，量是相同的。虽然人们必须小心“大部分时间”的意思，但这种直觉导致了本文中描述的两个应用。例如，集合相等性测试器通过维护每个集合的缩写（即，其散列值）来工作。如果缩写相同，它将声明两组相等。因此，大多数情况下，当它表示集合相等时，它是正确的，并且当它表示它们不相等时总是正确的。虽然这个想法并不新鲜，但我们在这里使用通用散列技术，因此对于任何一对集合而言，产生错误的概率都很小，而不仅仅是随机选择的集合。我们首先将简要总结通用散列，以使这种区分更加清晰。

散列可用于实现各种应用程序的快速平均性能，最明显的是用于关联存储器，例如编译器的符号表或数据库。人们希望“平均性能”表示应用程序将在其上运行的所有输入的平均性能。但是，人们通常不知道实际数据，因此选择一个散列函数，假设每个输入具有相同的可能性，它将很好地工作。最近开发了一种散列方法，它允许人们实现并证明快速的平均性能，而不需要假设任何关于输入的概率分布[6]。在这种方法中，采用的是一个具有哈希函数的集合，而不是一个哈希函数。每次运行应用程序时，都会从集合中随机选择一个哈希函数。 （如果这是不切实际的，可以不那么频繁地选择函数，或者可能只选择一次。参见[6]以获得更完整的讨论。）如果仔细选择函数集来称为通用类，那么许多应用程序对于任何输入分布而言，散列将具有可证明的良好预期性能，而不仅仅是均匀分布。

已知的通用类包含相当多的散列函数。 例如，典型类中的函数可以散列n位长名称，并且该类包含2o（n）个函数。 因此，需要O（n）位来指定随机选择的函数。 在第3节中，我们提出了一组“几乎”强通用的函数，并且它们要小得多 - 只需要log（n）位。 这种改进可以使哈希的一些实际可行，例如下面描述的认证技术。 此外，如果与[9]的可扩展散列方案结合使用，可以制作一个快速，实用且完全通用的关联存储器子程序包。

第2节中描述的这些功能的一个可能重要的用途是可证明安全的认证系统。 该系统允许消息的接收者确定消息的真实性 - 消息未被未经授权的“敌人”伪造或修改。发送者和接收者必须共享长度为的密钥。 根据消息长度的日志顺序，但与基于公钥密码系统的数字签名不同，可以证明该系统即使对抗具有无限计算能力的敌人也是安全的。 此外，没有任何消息恰好易于伪造。

第4节给出了身份验证系统的改进，允许使用相同的密钥发送许多消息，每个消息需要一个额外但更短的密钥。 发送多条消息所需的密钥总长度渐近地达到下限。

在第5节中给出了推动定义强通用的函数类的应用程序 - 集合相等测试器。假设使用某些指定的操作构造集合，我们给出了一种技术，它具有独立的输入和很小的错误机会来确定集合是平等的。算法的预期运行时间是独立输入的，并且在构造操作和相等测试的数量上是线性的。这是我们所看到的唯一一种可疑的区别，即需要对两种类型进行概率分析 - 它既可以犯错，也可以花费很长时间。正如吉尔观察到的那样[111，人们总是能够以更大的误差概率为代价使运行时间保持不变。或者，可以结合普通的集合相等测试方法使用该技术。如果概率测试表明集合不同，则必须是正确的。如果说集合相同，则可以执行常规测试。

最后，在第6节中，我们将展示如何构建一个强大的通用函数集。可以快速评估该集合中的功能。

强大的通用HASH函数集

随机选择的函数将两个A点映射到相同值的概率。 为了使一组函数具有强大的通用性，随机选择的函数必须以相同的概率将A的任何II个不同点映射到B中的任何n个值; 换句话说，任何n个点必须通过函数在整个B中随机分布。 更正式的，定义。 假设H是一组散列函数，H的每个元素是从A到B的函数。如果给出任何n个不同的元素a，...，a，A和任何n（不一定是不同的），则H是强通用的。 ）B的元素b ,, ...，b，然后] Hl /（lBl“）函数取a，到b ,, a，到b ,,等等。（IX）表示集合X中的元素个数 。）对于n的所有值，如果它是强通用的，则一组散列函数是强通用的。

Carter和Wegman [6]提出了几类哈希函数，这些函数最终具有很强的通用性。 可以使用有限域上的多项式来创建强大的通用函数集。 特别是，让A和B都是相同的有限域。 设H是小于n的多项式的类。 H是强通用的，因为给定A的任何n个不同元素和B的对应元素，恰好有一个小于n的多项式，其通过指定对“插入”。 （使用Vandermonde矩阵的可逆性的标准线性代数证明也适用于有限域。）

定义一组散列函数似乎很奇怪，A和B的大小相同。 但是，例如，通过选择散列值的最后几位，很容易使B变小。 如果场的大小是2的幂，那么结果仍将是一个强大的通用类函数; 否则，它仍然会“接近”。在第6节中，我们将展示一个强大的通用功能集。

数字签名和认证标签

通常希望能够通过不安全的线路发送消息，并且允许接收器确定发送者的身份。 （为方便起见，我们将使用“A”或“he”来表示消息的声称发送者，并使用“B”或“她”作为接收者。）在现代通信方法存在之前，A可以为a添加手写签名。 信息。 B可以将消息上的签名与她知道的A签名进行比较，以确保自己的消息是真实的。 截获邮件的人无法切断签名并将其粘贴到其他文档而不进行检测。 我们寻求在数字消息的情况下获得这些优势。

签名提供了许多功能：（1）它可以向B保证该消息是由A或他授权的人发送的。 （2）它可以用来证明（或许在法庭上）A或他授权的人发送信息，以及（3）它可以向B保证A本人，而不仅仅是A授权的人，实际上发送了该信息。

认证标签提供了完成这三个功能中的第一个的方法。 如果存在每个人都信任的代理商，那么也可以使用认证标签来提供第二功能。 在介绍这些身份验证标记之前，我们希望查看另外两种方法，这些方法还具有签名的一些属性 - 数字签名和加密。 我们将讨论的方法都不能用于第三个函数，因为这些方法不依赖于A的物理属性，而只依赖于他可以向其他人揭示的某些知识。

Diffte和Hellman [7]讨论的数字签名由一串连接到消息的比特组成。 只有A知道用于生成签名的函数，但他也发布了一个检查函数。 此检查功能允许任何人测试签名是否对特定消息有效。 此外，如果没有签名功能（但即使使用检查功能），也很难确定任何备用消息的正确签名。 对于所有消息，存在有效签名。 Diffie和Hellman [71，和Rivest等人。 [121]提出了“公钥密码系统”，允许上述内容（除了允许有趣的加密类型。）但是，

定理。 没有公钥密码系统是不可破解的。 也就是说，具有无限计算资源的敌人可以伪造消息。 证明：有足够时间的敌人可以猜测特定消息的所有可能签名，并在找到有效签名时使用它。 因此，所有这些签名方案都可以在非确定性多项式时间内被破解，并且迄今为止没有一个被证明是NP完全的。 事实上，[1,2]已经表明，除非NP = co-NP（许多人认为不太可能），否则公钥密码系统不能完全NP。

传统的加密方案还提供了签名的一些功能。 假设A和B已经同意加密和解密方法，他们保密。 当B接收到任何比特串时，她应用解密算法。 如果结果看起来合理，她可以确保比特串确实是A发送的消息。这种方法有几个缺点。 首先，可能发生的是，如果任何加密的有效消息的某一部分以某种方式被扭曲，那么结果仍然有可能成为加密的有效（但不同）消息。 如果是这样，即使没有能够解密任何消息，敌人也可能干扰通信。 这是一种制造恶意恶作剧的技巧。

如果敌人知道正在发送的消息，事情会更糟。例如，假设银行出纳员和中心局之间的消息是通过异或或随机且从不重用的位串加密的。 （众所周知，这可能是一种不可破解的加密技术。）小偷存款，出纳员将交易记录发送到中央办公室。小偷现在拦截编码的消息并阻止它被发送到中央办公室。由于窃贼知道明文和加密版本的消息，他可以将它们排在一起或一起恢复一次性随机位串。他现在可以用一个不同的消息替换 - 也许是一个更大的存款的记录 - 与现在已知的位串独有。道德是一种好的加密技术可能无助于证明作者身份。人们只能相信消息的真实性，以至于可以证明这种系统性变化是不可能的。使用加密来确定作者身份的第二个缺点是通信中必须存在一些冗余。如果大多数比特串是有效消息，并且如果加密过程没有增加消息的长度，则B将接受大多数传输作为有效。因此，必须注意对消息应用任何数据压缩。使用身份验证标记，可以将通信的保密方面与身份验证方面分开。可以在加密或不加密消息的情况下使用标签，并且所需的唯一冗余是标签本身所需的额外比特。与数字签名和加密不同，精心构建的认证标签系统具有以下特性：伪造者不可能具有创建消息的任意小的机会，接收者将接受该消息作为真实消息。认证标签系统可以如下形式化：存在一组M个可能的消息和一组认证标签。例如，M可能是长度为10,000或更小的所有字符串的集合，T可能是长度为100的位串集合。还有一个（公知的）函数集F，其中F映射中的每个函数为了使用该系统，A和B同意一个秘密“密钥”，它指定F中的一个函数f。当A在M中发送消息m时，他还发送认证标签f（m）。 B检查应用于她收到的消息的f确实是她收到的标签。如果是这样，她有一定保证收到的信息不是伪造的。必须无法从消息及其标记中找到该函数。否则，伪造者可能会拦截，分析和替换他们自己的消息。事实上，知道一条消息的值不能提供任何其他消息的值关闭信息。稍后我们将展示如何实现这一目标。

很自然地想知道，如果A和B已就任何人都没有任何知识的秘密认证功能达成一致，为什么系统不会自动完全牢不可破呢？为什么要将选择限制为来自函数集F？事实证明，对系统的安全性和可用性来说，指定F是很重要的。假设我们只是要求A和B合作选择一个函数。这需要时间和想象力，除非他们熟练，否则他们的选择可能很差。例如，如果他们确定消息的每个段落的第一个字母应该拼写出“GIPWOLLEY”，那么伪造者对消息的大多数小改动都会使这些字符保持不变，因此不会被检测到。因此，秘密函数必须依赖于消息中的大多数字符。如果通信者计划手动计算这样的功能，他们很可能会犯错误。因此要么他们必须知道如何编程计算机，要么必须有一个旨在帮助他们创建功能的软件包。如果它完全可用，这样的包将限制功能的选择，并且我们立即担心选择足够大以确保安全性 - 这当然是本节的主题。但是我们假设通信者能够编程。我们怀疑相当大比例的程序员在面对创建依赖于消息的所有位的秘密函数的问题时，会选择形式的函数，“仅接受与289模数一致的消息83 1 ，“或许”通过在32位块中将它们排除在一起来压缩消息，并且只接受结果为十六进制的消息'7A28E910'。“对于这两种方法，很容易将消息扭曲到另一个即使不知道所涉及的特定整数，也具有相同认证标记的消息。如果将所有小于1000的数字的最小公倍数添加到消息中，那么其小于1000的任何模数（以及模数很多其他数字）将保持不变。顺便提一下，该LCM长度小于1000 / n（2）位。欺骗异或技术甚至更容易：如果S是任何位串，使得使用32位异或的压缩S的结果是十六进制“00000000”，则S 0 M将压缩到与M压缩相同的值。至。本讨论的重点是说明为什么在认证方案背后有一个数学基础是很重要的。认证标签与签名的不同之处在于接收器B还可以创建认证标签，从而创建适当的消息。 B不能向第三方证明该消息源自A，因为第三方会意识到B可以制造它。似乎数字签名技术不能共享这个缺点。这只是部分正确。如果A想要拒绝他确实发送的信息的作者身份，他可以通过声称他不小心向B或其他人透露了他的秘密签名功能而这样做（代价有点尴尬）。

另一方面，如果存在普遍信任的代理商，则认证标签与用于建立消息的作者身份的数字签名一样好。其工作原理如下：每个人X只与代理商共享他的秘密功能。为了向B发送消息，A将其消息（使用他的功能标记）发送给代理商。邮件必须包含发件人和收件人的名称。该机构首先证明它收到的消息具有消息中指定的发件人的正确标签。然后它存储一个副本，通过fB将标签附加到消息，并将其转发到B.当B验证标签是否正确时，她接受该消息。 B现在可以向任何信任该机构的人证明A只是要求该机构检查其记录就向她发送了该消息。认证标签的第二个可能的缺点是只能使用特定功能发送有限数量的消息。我们将证明任何牢不可破的方案只能使用有限次数，该数字取决于密钥的大小和猜测正确标签的所需概率。我们还将展示我们的方案接近发送具有所需安全级别的给定数量的消息所需的最小密钥大小的理论界限。为了弥补这些缺点，我们可以构建一个可证明牢不可破的认证方案。也就是说，除了密钥知识之外，没有其他资源允许伪造者为伪造消息找到正确的标签。随着标签长度的增加，不知道密钥的伪造者将正确的标签附加到消息的可能性变得越来越远。为了使这更加精确，我们会说如果在随机选择函数f之后并且伪造者给出任何消息m和相应的tagf（m）之后，伪造者找不到不同的消息，那么认证系统是坚不可摧的。 '对他们来说，他们比猜测正确标签的概率更好。请注意，此定义必须适用于任何m，甚至伪造者选择的m。要创建一个具有确定性p的牢不可破的身份验证系统，我们可以简单地选择T以至少拥有l / p个元素，并且让F成为一个强通用的哈希函数类，从M到T.如果我们让H'为将m映射到f​​（m）的H的子集，我们看到伪造者可用的唯一信息是秘密函数是H'中的函数之一。然而，强通用的定义意味着对于与m不同的任何m'，将m'映射到任何特定标记t'的H'中的函数的比例是l /] TI。由于/ T /> l / p，伪造者的任何选择都不会超过p正确的概率。 Gilbert，MacWilliams和Sloane [lo]已经找到了相当复杂的强大通用功能集，正是出于这个目的。它们的集合和其他先前已知的强通用集合的困难在于函数集是如此之大以至于在类中指定函数需要至少与原始消息一样长的密钥。希望使用比消息短得多的密钥。第二个问题是每个密钥只能发送一个消息，因为两个消息标签对的知识可能会给某些第三个消息上的函数值提供一些信息。我们将分别解决这些问题。

一个小的，几乎强烈的通用，类

我们希望从一些大空间A'到空间B'构造一组散列函数。在上文中，A'是消息集，B'是可能的标签集。设a'和b'分别是消息和标签的长度。设s = b'+ log，log，（a'）。设H是一些强通用的函数类，它将长度为2s的位串映射到长度为s的位串。 [6]的乘法方案可以用于此目的。 H'的每个成员将由一系列长度log构成，一个成员的' - log，b'构成H. Supposef，fi，...是一些这样的序列。我们将指定如何将关联的成员'h'应用于消息。消息被分解为长度为2s的子字符串。如有必要，最后一个子字符串应填充空格。因此，消息将被分解为[a'/ 2s] substrings.f，应用于所有子字符串，并且连接得到的子字符串。通过连接生成的子串，我们获得了一个字符串，其长度大约是原始字符串长度的一半。使用＆，f3，...重复此过程，直到只剩下一个长度为s的子字符串。标签（即，散列函数f'的结果）是该子字符串的低位b'位。指定f'所需的关键是指定f，f * 9所需的键的串联... * [6]中建议的乘法方案的密钥大约是输入大小的两倍。如果此类用于H，则H'的键的大小将为4s log，（a'）。因此，密钥大约是标签长度的四倍乘以消息长度的日志。相比之下，乘法方案本身将具有一个密钥，其长度是消息的两倍。观察到假设H中的函数可以与s成比例的时间进行评估，H'中的函数也可以在与消息长度成比例的时间内进行评估。 H'“几乎”强烈普遍的意义在下面的定理中给出。定理。给定任意两个不同的消息m，m2和任意两个标签值t，和t，取m，取t的数量是l / JB'（乘以函数的总数。但是，少于2 /（这些函数的B'J也需要m2到t ,.证明草图。每次我们将消息的长度减半时，两个结果字符串现在相同的几率很小（1 /（2'））。我们迭代对分过程日志，' - log，b'次，两个字符串在倒数第二步相同的几率最多为log，a //（27，等于1 /（2b'）现在事实上，最后一次缩减的函数是从一个强通用的类中选出的，可以用来表示m，将被置于任何标记中的概率相等，只要倒数第二个字符串不同，mp也将被带入任何字符串，概率等于l /（B'I。因此，如果t，＃t ,,那么小于l / j B'）函数将采用m2到t ,,否则，更少比2 / j B']会的。

上面的定理可以与强通用的定义形成对比，它表示l /（B'（函数必须取m，t，而l / IB']这些函数也需要m2到I 在认证方案方面，定理表明在敌人知道一个消息标签对后，他最好不要找到另一个消息标签对，其概率为2 /（B'）是正确的。因此， 该方案在确定性2 / \ B'I时是牢不可破的，并且这种确定性可以小于任何预定值。

认证多个消息

上述方法不允许我们使用相同的函数标记多个消息，因为一旦敌人知道两个消息标记对，他就可以确定更多这样的对。解决这个问题的一种方法可能是使用一个通用的函数，它允许我们发送它 - 1条消息，但更好的方法如下：设F是一个强通用的函数集，从M到B，其中B是长度为k的位串组。 A4中的每条消息都必须包含1到n之间的消息号。发送方和接收方共享的密钥现在由两部分组成。第一部分指定F中的函数f。密钥的第二部分是B的元素的序列（b ,, ...，b，）。发送者必须确定永远不会发送具有相同消息号的两个消息。要为消息m（消息编号为i的消息）创建认证标记ti，发送方首先计算f（mi），然后使用bi对此结果进行异或。由于每条消息都包含一个消息号，因此接收方可以复制此过程以验证标记是否正确。 （如果邮件未编号，则会自动拒绝作为伪造。）我们希望证明此方案牢不可破，确定性为1 /（2k）。定理。假设从一组键中随机选择了一些键（f，（b ,, ...，6，））。设m，...，m，是任何n个消息，限制消息号必须都是dtrerent（我们假设m，有数字i。）假设一个伪造者只知道集F和消息集及其对应的标签ti = f（m，）0 bi。 （我们使用@来表示独占或操作。）然后没有新消息（带有任何消息号），伪造者有正确猜测标签的机会超过1 /（2k）。证明假设伪造者希望将标记猜到新消息m。在不失一般性的情况下，我们假设m具有消息号1.对于B中的每个t，定义S，=（（g，b））g EF，b EB，g（m，）@ b = t和g（ m）@ b = t}。换句话说，S是部分键的集合（部分因为只指定了b的n个元素中的第一个），这与m，具有标记t，并且在标记t中给出伪造消息的事实一致。 。不难表明，由于F具有很强的通用性，因此每个S都具有相同的尺寸。此外，正好有一种方法可以将S中的每个部分密钥扩展为一个完整的密钥，它也将标签ti分配给消息m，对于i = 2，...，n（即，让bi = g（m，）0因此，在所有与伪造者可用的信息一致的密钥中，许多密钥将任何一个标签分配给任何其他标签。因此，伪造者猜测m的正确标记的概率是1 /（2k）。

当你使用一个几乎强烈通用的类时，类似的定理成立。下一个定理表明该方案所需的比特数是渐近最优的。为了使其精确，我们将OPT（n）定义为防止伪造者在伪造n个消息中的至少一个消息时具有超过指定的成功概率所需的最小密钥大小。我们证明当n接近无穷大时，我们的方案用于发送具有相同安全性的n个消息的比特数除以OPT（n），接近1.Fak [8]也证明了类似的定理。我们将考虑稍微更一般的情况，其中消息不需要消息号。假设已从集合F中选择了一个函数。伪造者选择消息m，并尝试猜测正确的标记。然后告诉他正确的标签t ,.现在，伪造者选择第二条消息m2，尝试猜测标签，然后告诉正确的标签t，。该过程重复n次。如果我们愿意，我们可能要求伪造者从所有消息集的受限子集中选择每个消息，或者我们甚至可能有一个固定的消息序列 - 这些变化不会影响以下定理。 THEOhEM。在上面的场景中，如果伪造者对他的第i次猜测的成功概率是<pi，那么F必须至少包含l /（p，p，... ..）函数。对于i = 1，...，k}，证明令FO = F且Fk = {fe F] f（m，）= t。伪造者可能在他的猜测中使用以下策略：在选择第i个消息后，他枚举集合Fi-，随机选择其成员，并猜测tagf（m，）。由于这有成功的机会，所以必须是{fE Fi-，s.t。 f（mi）= ti} l <pi JFi_l]。左边的集合是F ,,所以我们有IF， - ，I>（l / pi）（F，I。对于每个i都是如此，所以我们有IF01>（l / p，）。 ...（l / p ,,）/ F，I。定理从FO = F和（F，1> 1. COROLLARY。当p，= p，= ... = p，然后它至少需要n（ -log，（p））用于为任何方案指定随机选择的F的成员，该方案具有确定性p且不能发送n个消息。请注意，我们上面提出的方案需要n（-log，（p） ）+ K比特，其中K是指定强通用哈希函数类的元素所需的比特数。

5.测试集合平等

在本节中，我们提出了一种线性时间算法，用于概率性地测试许多集合的相等性。 更正式地说，假设我们有一系列请求，可以命名任意数量的集合和任意数量的元素。 每个请求可以是以下四个命令之一：ADD（x，S） - 将元素x添加到名为S的集合中。如果x已经是S的成员，则不能使用此操作。如果先前未使用过S 在任何命令中，它都被视为空集的名称。

DELETE（x，S） - 从名为S的集合中删除元素x。仅当x是S的成员时才可以使用。'TEST（S ,, S，） - 如果由S命名的集合，则返回“true”和S相等，否则为“假”。当它们不是时，TEST可能会调用两组相等，但是当它们实际上相等时它不能称它们不相等。 FIND（S） - 返回等于S的集合名称列表.S将始终包含在此列表中。错误地，该列表可能包含实际上不等于S的集合的名称，但是不能忽略相等的集合。给定任何E> 0，我们可以在请求次数（-log（c））的预期时间内处理一系列请求。每个TEST请求的错误概率将小于E，并且对于每个FIND请求，小于请求时存在的设置名称数量的E倍。除了上面提到的四个请求之外，还可以有COPY和DIFF请求，或ELEMENT，LIST和CONTAINERS请求。它们的定义如下：COPY（S ,, S＆ - S，成为由S命名的集合的另一个名称.DIFF（S，S＆-Assigns S，是S和S的对称差异。）ELEMENT （x，S）---如果x是名为S的集合的成员，则返回“true”，否则返回“false”。此响应始终是正确的.LIST（S） - 返回名为set的元素的列表S. CONTAINERS（x +返回包含x的所有当前存在的集合的名称列表。执行这些操作的算法是对已知启发式的修改（参见[13]），当两个集合不相等时，有时会迅速确定它们是不相等的。（其余时间，启发式无法确定它们是否相等。）我们修改了方案，以便给定任何创建不等集的请求序列，算法将确定它们是不相等的概率。概率可能会很高，以至于缺乏显示它们不相等就足以证明这些概率应用程序将它们视为平等。例如，可以使概率小于计算机在执行完整测试所需的额外时间内发生硬件错误的概率。我们将此算法视为用于其他应用程序的工具，而不是因为我们直接对测试集合相等感兴趣。因此，重要的是我们可以证明犯错的概率不依赖于输入字符串的特定特征，否则我们的应用程序只能使用具有这些特征的请求序列。我们通过构造一类算法来实现这一点，并且表明对于最差输入，随机选择的算法产生错误的概率很小。

集合相等测试器背后的基本思想是，每个集合名称为Si，有一个“缩写”Vi。当对集合进行更改时，将更新缩写。如果它们的缩写相等，则声称两组是相等的。与每个缩写相关联，必须有一个当前具有该缩写的集名称列表。当然，我们将缩写（及其相应的列表）存储在哈希表中。顺便提一下，由于VI是通过散列产生的，所以简单地掩盖掉位作为用于将它们存储在该表中的散列函数就足够了。更具体地说，令G为具有操作0的组，并且用G表示G中的x的倒数。设h是从强通用的集合中选择的散列函数，该集合将被构造的集合的元素映射到G.可以实现这种方案，其中G是一定长度的位串集合，0是异或。该操作易于执行，并且逆操作 - 身份功能 - 甚至更容易。第一次使用集合名称Si时，其对应的Vi被设置为G的标识元素。请求按如下方式处理：ADD（x，S，）通过将Vi更新为Vi @ h（x）来实现，并且从与Vi的旧值关联的列表中删除Si并将其添加到新值。 （为了能够在恒定时间内执行删除，我们必须保留一个名为S的指针，该指针指向此名称在与Vi关联的列表中的位置。）DELETE（x，Si）的实现方式类似，除了h（x） - '用于代替h（x）。通过将Vi与Vi进行比较来实现TEST（S ,, Sj）。 FIND（S，）只返回与Vi关联的列表。 COPY（S ,, Sj）从VI列表中删除Si，设置Vi = Vj，并将Si添加到Vi的列表中。 DIFF（S ,, Sj）将Vi设置为Vi @ Vj，并相应地更新与旧缩写和新缩写相关联的列表。我们观察到，为了使DIFF正常工作，对于所有x E G，x-'必须为x，这是组操作为独占的情况。元素，列表和容器 - 为了能够执行这些操作，必须保留几个额外的哈希表。一个包含所有对（x，Si），它们是ADD请求的主题但不是DELETE请求。该表用于回答ELEMENT请求。第二个哈希表将每个x与包含x的集合列表相关联。咨询该表以执行CONTAINERS请求。为了能够在遇到DELETE（x，Si）请求时以恒定时间更新该列表，有必要将第一个哈希表中的对（x，Si）与指向相关列表中的Si的指针相关联。用x。最后，为了能够回答LIST（S，）请求，我们需要将名称Si与当前在Si中的元素列表相关联。同样，我们需要一个存储有对（x，S，）的指针，这将使我们能够在遇到DELETE（x，S，）请求时在常数时间内从与Si相关的列表中删除x。

可以修改这些技术以处理多组而不是组。多集类似于集合，除了计算元素插入多集的次数。仅当每个元素插入相同的次数时，两个多组相等。在上面的讨论中，我们建议使用异或作为操作0.如果使用普通加法，那么类似于上述方案的方案可以处理请求，ADD（x，k，S），其中添加k个副本x到S（我们不再需要x不在S中的限制），DELETE（x，k，S），TEST @ ,, Sj）和FIND @，）。类似于设置相等的情况，可以另外添加COPY和MULTISET-UNION命令，或ELEMENT，LIST和CONTAINERS命令。这里，ELEMENT（x，Si）返回x在Si中出现的次数。使用加法而不是排他性的困难 - 或者说Vi可以任意变大，因此假设操作需要恒定时间可能不再有效。然而。如果请求序列永远不会产生非常大的多集，那么这将不是问题。我们现在提到集合相等测试器的三个应用程序。 LR或LALR解析表的生成可以加速，因为花费了相当多的时间来检查一组项是新的还是已经生成的。这里，FIND命令特别有用。其次，图表可以表示为一组节点和一组边缘。现在可以轻松地测试标记图表的相等性。最后，计算机的存储状态可以表示为一组对，每对由地址和存储在该地址中的值组成[3]。如果内存中的值发生更改，我们将删除由地址和旧值组成的对，并添加地址对和新值。我们可以使用我们的方法来查看之前是否已经看到了内存状态，从而查看程序是否正在循环（参见[4]）。可以想象，相等测试可以扩展到其他请求。如果可以充分扩展相等性测试，那么像SETL这样的语言的很大一部分可能适合这样的方案。然而，最近的结果[141表明，不可能找到两组不相交的快速测试。

实施强大的通用，集

我们可以创建一个强通用的函数集，如下所示：每个函数都将集合元素的名称集（即集合相等测试器的XI'）映射到组G. [6]的技术给我们能够使用关联存储器，每个请求需要不变的预期时间。我们假设能够生成随机数。我们将使用这两种能力仅在我们看到的所有输入上创建部分函数.f（x）计算如下：如果在关联存储器中存在与x相关联的值，则f（x）是该值。否则，f（x）等于从G中随机选择的值，并且x和该值存储在关联存储器中。因此，任何元素上的散列值与其在任何其他元素上的值无关。我们现在可以证明：THEOREM。上述集合相等测试器错误地回答TEST请求的概率不超过组中元素数量的倒数。 ProojI有两个可以想象的错误：我们的算法可能会说两个相等的集合是不相等的，或者可能说两个不相等的集合是相等的。如果Vi＃V，则设置Sj和Si必须不相等。因此，不会发生第一类错误。我们现在将发现说两个不相等集的概率是相等的。如果集合Sj和Si不相等，那么集合Sj或集合Si必须具有不包含在另一集合中的元素。我们通过Xi，k枚举集合S的元素。在不失一般性的情况下，我们假设Si具有不包含在Sj中的元素xi。如果Vi = Vi则h（xi，）0 h（xi ,,）“ = h（xj，）0 h（xj，2）''当且仅当h（Xi，）时为真= h（Xi。，） - '哦（Xi，3） - '“'哦（Xj，）哦（Xj，）”'。它遵循强通用的定义，对于任何b EG（其中G是散列函数的范围），h（x ,,,）= b的概率独立于b的值和h的值其他元素，所以h（Xi，l）= h（Xi，Z） - '0 h（Xi，j）-l“'@ h（Xj，）@ h（Xj，*）”'的概率是因此，当Si＃Sj是G中元素数的倒数时Vi = Vj的概率。注意，确实需要使用强通用的函数集，因为上述推理要求h（S，）的值独立于集合S和Sj的所有其他元素上的h值。如果组元素都是长度为100的位串，则每次测试的错误概率为l / 2“'。这可能小于进行完整检查所需的额外时间内机器错误的概率。