用Hash避免合并问题中的遍历

起：

我有一大串(1024^2)三元组称为ori，其中很多是需要合并的（如果只是正负号和排列顺序不同）。需要得到合并后的三元组列表

承：

如果用一般算法，就是新建一个list，将ori中的三元组一个一个加进去，每一次加进去，就要遍历list中所有三元组，能合并的合并。

这样做显然会很慢，在我的机子上跑了90s。

转：

如果三元组按大小排列是(a,b,c)，想到用a作为hash下标。这样判断融合的时候就只要hash到a下标，然后解决冲突尝试融合：

冲突解决，一开始我实现是最简单的，如果a位置已经占元素了，就往后找空位：

但实际用下来冲突很多，所以还是很慢。因为我的ori中有大量a相同但b,c不同的三元组。

所以想到，如果解决一次冲突，后移的次数(k)太多，那就重新Hash到另一个位置。

因为我的数据a的特征是1e6，且几乎<5e5的数，而hashArr预设的大小是1e6，所以后半截几乎是空的，可以转到后面去：

但这样只快了25%，感觉reverse了之后还是冲突了很多。于是想寻找一个更好的reverse方法（也就是对a的hash方法。因为a已经是对trip的一种hash方法了，所以这里随便叫reverse）。

我受git上开源PNG压缩用的hash代码启发，以冲突a‘为种子，再a进行位移和异或：

速度直接从90s到3s，省97%！终于感觉到Hash的力量了

合

以前觉得算法和数据结构不重要，因为没有hit到硬件性能瓶颈，包括光追的BVH。现在都得还债...