Определение хеша объекта как суммы хешей его членов

Question

У меня есть класс, который представляет неориентированные ребра в графе. Каждое ребро имеет два члена vertex1 и vertex2, представляющих соединенные вершины. Проблема в том, что для ребра можно указать два направления. Моя идея состояла в том, чтобы определить хэш ребра как сумму хешей его вершин. Таким образом, направление больше не играет роли, хэш будет таким же. Есть ли какие-либо подводные камни с этим?

Answer 1

Мне пришлось решить аналогичную проблему, и я обнаружил, что использование суммы хэшей в качестве хэша приводит к слишком большому количеству коллизий. Распределение суммы хэшей просто недостаточно распределено.

Я обнаружил, что использование продукта хэшей приводит к гораздо меньшему количеству столкновений. Это, конечно, зависит от природы хэшей для отдельных вершин.

Установите тестовый стенд и протестируйте несколько симметричных хеш-функций, а затем выберите лучший на основе коллизий.

Вы можете попробовать

h(x,y) = x+y
h(x,y) = x*y
h(x,y)  = x * y + (x ^ y)
h(x,y) = x *y + x + y

где x ^ y = min (x, y)