For a pangenome deduplication tool I’m working on (pandedup), I’m using 128-bit hashes as “unique” identifiers of substrings.

Sadly, it turns out that gxhash128 has a hash collision between the two strings of length 88 below that only differ in 5 positions, regardless of the value of the seed.

Looking at the strings, this clearly isn’t a random collision. Those could be expected when doing \(2^{64}\) lookups in a dictionary of \(2^{64}\) keys, but my data is nowhere near that large.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

use gxhash::gxhash128;

fn main() {
    //                                                                     *                     ****
    let a = "GGAGGAAGTCCCCCAGGAGTCCTGGGATGAAGGTTATTCGACTCTCTCAATTCCTCCTGAAATGTTGGCCTCGTACCAGTCTTAAGCA";
    let b = "GGAGGAAGTCCCCCAGGAGTCCTGGGATGAAGGTTATTCGACTCTCTCAATTCCTCCTGAAAGGTTGGCCTCGTACCAGTCTTACAGC";
    for _ in 0..1000000 {
        let seed = rand::random::<i64>();

        let hash_a = gxhash128(a.as_bytes(), seed);
        let hash_b = gxhash128(b.as_bytes(), seed);
        eprintln!("A: {a} => {hash_a}");
        eprintln!("B: {b} => {hash_b}");
        assert_eq!(hash_a, hash_b); // This passes, even though I don't want it to.
    }
}

If we drop the first character from each, then the hashes do become distinct. In general, making similar changes to both strings seems to still give the same problem, but not always. For example, changing the G at index 3 to a C does result in different hashes.

Anyway, I shall search for a better hash function.

References Link to heading