这里介绍一些常见的错误哈希函数，并给出反例。这些哈希函数可能易于实现，并对于随机数据效果不错，所以广受人民群众喜爱(包括我)，但对于某些确定的树结构会出问题。
(“正确”的哈希函数应当对于任何树结构都可以保证极小的出错概率，出错与否是无法由测试数据设计者控制的。)
记号：以下用 $x$ 表示字母树上的一个结点，$y_1,\dots,y_d$ 表示结点 $x$ 的孩子集合，$s(x)$ 表示结点 $x$ 的文件夹名，$h(x)$ 表示结点 $x$ 的哈希值，$h(s)$ 表示字符串 $s$ 的哈希值。令 $M$ 代表随便选的一个数，$P$ 代表大质数。

一些错误的哈希函数：

1. $h(x)=M\cdot \sum_{1\leq i\leq d}h(y_i)+h'(s(x))~~(\bmod~P)$.
   这个函数的问题是太线性了。当我们把不同儿子的哈希值加起来时，如果对一个儿子的哈希值加1，对另一个儿子的哈希值减1，那么结果不变。对于比较简单的 $h'(\cdot)$ 这很容易做到。
   实现举例1 举例2 变种3(周赛CN第8名的代码 @JTJL)
   反例：
   [["a"],["b"],["a","b"],["a","d"],["b","a"],["b","e"]]
2. $h(x)=1+M\cdot \sum_{1\leq i\leq d}h(y_i)\cdot h'(s(y_i))~~(\bmod~P)$.
   这是上一个函数的变种，因为有 $h'$ 的存在，看起来更复杂了。但即使 $h'$ 很复杂，如果我们把所有的 $h'(s(y_i))$ 看成变量，那么最终结果是关于它们的多项式。我们可以用多种方法(对应多棵不同的树)凑出同一个多项式，例如 $1+M((1+Ma)\cdot b+1\cdot a)=1+M((1+Mb)\cdot a+1\cdot b)$。此时即使并行使用多个模数也不能带来任何帮助。
   实现举例1(更新后) 举例2(这个例子实现时有个小错误，反而卡不掉了。修正之后可以卡掉。)
   反例：
   [["y"],["y","a"],["y","a","b"],["y","b"],["z"],["z","b"],["z","b","a"],["z","a"]]
   即使混合使用 $\bmod P$ 与自然溢出，当$P$较大时我们也可以用类似的办法构造数据使得出错概率较大(这可能有点反直觉，$P$大了反而容易出错)：
   实现举例3 反例：
   [["xtiiadgbdw"], ["xtiiadgbdw", "monetnwzju"], ["xtiiadgbdw", "monetnwzju", "uqqiqmeoqw"], ["xtiiadgbdw", "uqqiqmeoqw"], ["djjdtgpgmf"], ["djjdtgpgmf", "uqqiqmeoqw"], ["djjdtgpgmf", "uqqiqmeoqw", "monetnwzju"], ["djjdtgpgmf", "monetnwzju"]]
   实现举例4 反例：
   [["ztnorzuybq"], ["ztnorzuybq", "pyjmbyiqtv"], ["ztnorzuybq", "pyjmbyiqtv", "vfsicaayya"], ["ztnorzuybq", "vfsicaayya"], ["omvuigvvjx"], ["omvuigvvjx", "vfsicaayya"], ["omvuigvvjx", "vfsicaayya", "pyjmbyiqtv"], ["omvuigvvjx", "pyjmbyiqtv"]]
   它们跟前一个反例的树结构是相同的，但字符串随机选取。
3. 令 $h_i(x)=(h_{i-1}(x)\cdot M+h(y_i)\cdot M+h'(s(y_i)))\bmod P$ 为前 $i$ 个儿子的 hash 值, 而 $h(x)=h_d(x)$.
   这个哈希函数类似Rabin-Karp，但有个重要的漏洞：如果我们把取模前的最终结果看成一个 $M$ 进制大数，则多个结点可能共享同一位。如果选取的 $h'(s)$ 函数过于简单，例如使用线性函数，则我们可以容易地对一个后代结点的哈希值加1，对相应的另一个后代结点的哈希值减1，并保持结果不变。
   实现举例
   反例：
   [["y"],["z"],["a"],["i"],["j"],["e"],["y","a"],["y","a","b"],["y","d"],["y","d","e"],["z","i"],["z","i","b"],["z","d"],["z","d","j"]]
   正确的做法应当记录子树大小$\mathrm{size}(y_i)$，合并一个子结点时乘上 $M^{\mathrm{size}(y_i)}$ 而不是 $M$。
4. 在例三的基础上，即使选取较为复杂的函数 $h'(s)$，例如std::hash()，我们也可以换一种攻击方式：采用类似例二的方法，把所有的 $h'(s(y_i))$ 看成变量，并用多种方法凑出同一个多项式。常见的办法是找到两个共享答案同一位的点，并交换两个点在树中的位置。
   以下例子使用的是 $h_i(x)=(h_{i-1}(x)\cdot M^2+h(y_i)\cdot M+h'(s(y_i)))\bmod P$，原理是一样的。
   实现举例
   反例：
   [["y"],["y","b"],["y","b","a"],["y","d"],["y","d","c"],["z"],["z","d"],["z","d","c"],["z","d","c","b"],["z","d","c","b","a"]]
5. 在例四的基础上，令 $h(x)=(h_d(x)\cdot M+B)\bmod P$，即在尾巴上添加一个随便选的常数 $B$. 注意如果在头上添加常数 $B$，即令 $h_0(x)=B$，则反例4已经能卡掉了。这个反例的构造方式是类似的。
   实现举例1 变种2(周赛CN第4名的代码 @wifiii)
   反例：
   [["y"],["y","b"],["y","b","a"],["y","d"],["y","d","c"],["z"],["z","c"],["z","c","a"],["z","d"],["z","d","b"]]