起：

我有一大串(1024^2)三元組稱為ori，其中很多是需要合并的（如果只是正負號和排列順序不同）。需要得到合并后的三元組列表

承：

如果用一般算法，就是新建一個list，將ori中的三元組一個一個加進去，每一次加進去，就要遍歷list中所有三元組，能合并的合并。

這樣做顯然會很慢，在我的機子上跑了90s。

轉(zhuǎn)：

如果三元組按大小排列是(a,b,c)，想到用a作為hash下標。這樣判斷融合的時候就只要hash到a下標，然后解決沖突嘗試融合：

沖突解決，一開始我實現(xiàn)是最簡單的，如果a位置已經(jīng)占元素了，就往后找空位：

但實際用下來沖突很多，所以還是很慢。因為我的ori中有大量a相同但b,c不同的三元組。

所以想到，如果解決一次沖突，后移的次數(shù)(k)太多，那就重新Hash到另一個位置。

因為我的數(shù)據(jù)a的特征是1e6，且?guī)缀?lt;5e5的數(shù)，而hashArr預(yù)設(shè)的大小是1e6，所以后半截幾乎是空的，可以轉(zhuǎn)到后面去：

但這樣只快了25%，感覺reverse了之后還是沖突了很多。于是想尋找一個更好的reverse方法（也就是對a的hash方法。因為a已經(jīng)是對trip的一種hash方法了，所以這里隨便叫reverse）。

我受git上開源PNG壓縮用的hash代碼啟發(fā)，以沖突a‘為種子，再a進行位移和異或：

速度直接從90s到3s，省97%！終于感覺到Hash的力量了

合

以前覺得算法和數(shù)據(jù)結(jié)構(gòu)不重要，因為沒有hit到硬件性能瓶頸，包括光追的BVH?，F(xiàn)在都得還債...