动机

在实现 XLex 和 XParse 的过程中，有一个反复出现的需求，判断一个无序集合是否出现过。

例如，使用子集法构造 DFA 时，每个 DFA 状态对应一个 NFA 结点的无序集合，当算法转移到一个得到新的 DFA 状态时，需要判断它的 NFA 结点集合是否已经出现过。构造 LR(1) 项目集自动机时，也需要对项目集合的存在性进行查询。

一个传统的实现方式是，为项目集元素确定一个顺序（例如创建时间的编号），将无序集合排序后作为键，存入平衡搜索树或哈希表等查询结构中。假定待查询的项目集为 ，单次数据结构查询的时间为 ，则做一次完整查询的时间复杂度是 。

算法

对一个类型 的无序集合 ，我们使用一个随机数生成器，为其中每个元素随机生成一个 位的整数，记为 ，定义无序集合的哈希函数 ，，即将一个无序集合映射成每个元素对应随机整数的异或和。

在具体实现中，我们不需要一开始真的对所有元素 生成 的值，这里我们可以使用一个查询的数据结构（平衡搜索树或哈希表）缓存下所有出现过的元素即可。这里你也可以自定义一些均匀的哈希函数，就避免多使用数据结构维护函数 ，但是你必须提防碰撞的发生。判断无序集合是否出现，这里就等价于判断哈希值是否出现，同样使用数据结构维护即可。假定查询 函数的时间为 ，查询哈希值存在的数据结构耗时为 ，则做一次完整查询的时间复杂度是 。

对碰撞的概率进行一些粗略的分析，假设有两个无序集合 ，我们固定集合 ，考察 的概率。若 ，那么碰撞的概率就等于 ；否则 ，前 个元素可以任意选择，若要发生碰撞，那么集合 的最后一个元素只有唯一一种取值。因此碰撞概率为 。

实现

见 yjl9903/SetMap (opens new window)。