EfficientHashing

EfficientHashing

EfficientHashing replaced hashing algorithm of `Vec3i` (and its subclasses like `BlockPos`) with one that's much much more collision resistant, providing performance improvement in basically wherever its hashcode is used.

Collision Resistant

We can prove this by doing a simple test. Test is perform by hashing every combination of `BlockPos` between `new BlockPos(-100, -20, -100)` and `new BlockPos(100, 50, 100)` (inclusive), with the total object count reaching 2,800,000+.

Vanilla algorithm produced 194,571 unique hashcode in total. This means that at least 93% of all BlockPos hashcode are colliding with each other.

And PhiMix, the algorithm used by EfficientHashing, produced 2868471 unique hashcode in total. This means that every unique BlockPos object gets its unique hashcode, and NONE of all BlockPos hashcode are colliding.

| | Unique Hashcode | Collision | Collision Rate | |------------------|-----------------|-----------|----------------| | Vanilla | 194,571 | 2,673,900 | 93.2% | | EfficientHashing | 2,868,471 | 0 | 0% |

If you're curious about the actual test code, see: here

Performant

Benchmark time:

``` Benchmark Mode Cnt Score Error Units VecHashingBenchmark.mixin thrpt 5 47.012 ± 1.029 ops/s VecHashingBenchmark.vanilla thrpt 5 49.326 ± 1.507 ops/s ```

PhiMix is about 95.3% the performance of original hashing algorithm. Yes, it's slower, but this performance gap is relatively tiny compared to other hashing solution, and can be easily outweighed by the significant improvement in hash collision resistance.

If you're curious about the actual benchmark code, see: here

Vanilla compatible

In vanilla hashing algorithm, if you hash the "default" instance of `BlockPos`/`Vec3i`, aka `new BlockPos(0, 0, 0)`, the produced hashcode will be `0`, which happens to be the "default" instance of integer. This special behavior is also present in PhiMix, providing the best possible vanilla compatibility.