POJ3349 Snowflake Snow Snowflakes

定义 $\text{Hash}$ 函数 $H(a_{i, 1}, a_{i, 2}, \cdots, a_{i, 6}) = \sum_{j = 1}^{6} a_{i, j} + \prod_{j = 1}^{6} a_{i, j} \mod{P}$，其中 $P$ 是我们自己选取的一个较大的质数。显然，对于两片形状相同的雪花，它们六个角的长度之和、长度之积都相等，因此它们的 Hash 函数值也相等。

建立一个 $\text{Hash}$ 表，把 $N$ 片雪花依次插入。对于每片雪花 $a_{i, 1}, a_{i, 2}, \cdots, a_{i, 6}$，我们直接扫描表头 $H(a_{i, 1}, a_{i, 2}, \cdots, a_{i, 6})$ 对应的链表，检查是否存在与 $a_{i, 1}, a_{i, 2}, \cdots, a_{i, 6}$ 形状相同的雪花即可。对于随机数据，期望的时间复杂度为 $\mathcal{O}(N^2 / P)$；取 $P$ 为最接近 $N$ 的质数，期望的时间复杂度为 $O(N)$。