EfficientHashing

EfficientHashing

EfficientHashing заменяет алгоритм хеширования Vec3i (и его подклассов, таких как BlockPos) на гораздо более устойчивый к коллизиям, что даёт прирост производительности практически везде, где используется его хеш-код.

Устойчивость к коллизиям

Это можно доказать простым тестом. Тест выполняется путём хеширования каждой комбинации BlockPos между new BlockPos(-100, -20, -100) и new BlockPos(100, 50, 100) (включительно), при общем количестве объектов, достигающем 2 800 000+.

Ванильный алгоритм выдал всего 194 571 уникальный хеш-код. Это означает, что как минимум 93% всех хеш-кодов BlockPos конфликтуют друг с другом.

А PhiMix, алгоритм, используемый EfficientHashing, выдал 2 868 471 уникальный хеш-код. Это означает, что каждый уникальный объект BlockPos получает свой уникальный хеш-код, и НИ ОДИН из всех хеш-кодов BlockPos не конфликтует.

Если вам интересен сам код теста, смотрите: здесь

Производительность

Время бенчмарка:

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 показывает около 95.3% производительности оригинального алгоритма хеширования. Да, он медленнее, но этот разрыв в производительности относительно невелик по сравнению с другими решениями для хеширования, и его легко перекрывает значительное улучшение устойчивости к коллизиям хешей.

Если вам интересен сам код бенчмарка, смотрите: здесь

Совместимость с ваниллой

В ванильном алгоритме хеширования, если вы хешируете "стандартный" экземпляр BlockPos/Vec3i, то есть new BlockPos(0, 0, 0), полученный хеш-код будет равен 0, что совпадает со "стандартным" значением целого числа. Это особое поведение также присутствует в PhiMix, обеспечивая наилучшую возможную совместимость с ваниллой.