Мне нужна быстрая и простая хеш-функция, которая создает уникальный идентификатор для пары значений uint32_t, то есть одно и то же хеш-значение для (2,7) и (7,2).
Есть идеи?
Коммутативная хэш-функция для пар значений uint32_t
20.07.2013
- Создайте uint64, сдвинув меньшее (или большее) из двух чисел и добавив другое. Тогда вам просто нужно хэшировать 64-битный int. (В качестве альтернативы хеш-функция скопирует пару, затем поменяет местами элементы, чтобы гарантировать порядок, и применит реальный хэш к этой паре) 20.07.2013
- @DavidRodríguez-dribeas: Да, тем временем я придумал решение, спасибо. У меня уже был материал для битового сдвига, но вы помните меня, что сравнение — это волшебство. 20.07.2013
Ответы:
1
Чтобы ответить на мой собственный вопрос, решение:
uint64_t hash(uint32_t x, uint32_t y)
{
const uint64_t a = static_cast<uint64_t>(x);
const uint64_t b = static_cast<uint64_t>(y);
if (x < y) return (b << 32) | a;
else return (a << 32) | b;
}
Который можно улучшить до версии без филиалов.
uint64_t hash(uint32_t x, uint32_t y)
{
const uint64_t a = static_cast<uint64_t>(x);
const uint64_t b = static_cast<uint64_t>(y);
const uint64_t h0 = (b << 32) | a;
const uint64_t h1 = (a << 32) | b;
return (x < y) ? h0 : h1; // conditional move (CMOV) instruction
}
Эти методы являются идеальными хеш-функциями — они гарантируют нулевые коллизии. Однако у них есть недостаток, заключающийся в том, что вы не можете хешировать значения выше 2^32 - 1.
20.07.2013
2
constexpr uint32_t hash_max = ...;
constexpr uint32_t commutative_hash(uint32_t i, uint32_t j) {
return (i*j + (i*i)*(j*j) + (i*i*i)*(j*j*j)) % hash_max;
};
Дополнительные скобки для компилятора - так будет проще оптимизировать это выражение.
Не используйте никакие условные инструкции (или std::max/std::min), которые прерывают конвейер процессора (и работают медленно), если вы хотите сделать быструю функцию.
20.07.2013
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально
Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение
Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования
Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv)
Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..
if (x>y), когда у меня была точно такая же потребность, как и у вас, но теперь, когда я думаю об этом,hash(x) ^ hash(y)подошёл бы также (с той проблемой, что все пары идентичных элементов(x, x)имеют одинаковый хэш. Это может быть проблемой для некоторые приложения) 28.07.2013max << 32вызывает неопределенное поведение (поскольку вы выполняете сдвиг на величину ›= размеру типа данных). Только после|результат гарантированно будет приведен кuint64_t. На практике ваш компилятор все равно выполняет 64-битные вычисления, но это нельзя предполагать наверняка. 06.03.2017