Hashed sorting is typically faster than hash tables
- Сортировка с хешем быстрее хеш-таблиц: на больших данных 1,5–4×, несмотря на «O(n log n)».
- Память: хеш-таблица тянет 128 Б на 8-Б ключ (64 чтение + 64 запись), радикс-сорт 3 прохода — 48 Б (вся линия кэша используется).
- Плохие распределения (мало заполненных корзин) замедляют радикс-сорт; решаем хешем
hash(key) перед сортировкой. Берём обратимую функцию (Murmur3, MulSwapMul), хешируем «на лету» в первом проходе.
- Результат: 2 ГиБ уникальных uint64 за 1,9 с против 2,6 с у оптимизированной хеш-таблицы.
- Подходит, когда порядок не важен, а нужны только уникальные значения; иначе остаёмся на хеш-таблицах.