Эффективное хеширование

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

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

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

Алгоритм Vanilla создал в общей сложности 194 571 уникальный хеш-код. Это означает, что по крайней мере 93% всего хэш-кода BlockPos являются сталкиваясь друг с другом.

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

| | Уникальный хэш-код | Столкновение | Частота столкновений | |------------------|-|---------------------------|----------------| | Ваниль | 194 571 | 2 673 900 | 93,2% | | Эффективное хеширование | 2 868 471 | 0 | 0% |

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

Исполнитель

Время тестирования:

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, обеспечивая наилучшую совместимость с ванилью.