This work presents a systematic evaluation of four similarity hashing techniques applied to ELF binaries compiled in three Linux distributions. Two structural, opcode-based approaches (MinHash and SimHash) and two widely used byte-based techniques (ssdeep and TLSH) are compared under real recompilation scenarios. The analysis includes global statistics, intra- and inter-family separation, and ordinal metrics of agreement between similarity rankings. The results show that MinHash and SimHash preserve internal relationships among recompiled variants and yield relatively stable rankings, whereas ssdeep and TLSH exhibit asymmetric distributions, a predominance of near-zero similarities, and limited ability to distinguish equivalent variants. These findings indicate that structural approaches are better suited for comparing recompiled ELF binaries across different distributions and system versions.