Код ниже предназначен для подсчета количества линий на плоскости для различных значений наклона.Для обозначения наклона линии рекомендуется использовать пару положений по осям x и y, b / c, непосредственно вычисляющее деление y / x, будет иметь проблему точности с плавающей точкой.Все позиции x и y являются целыми числами.
Хотя метод I работает в тестовом коде, мне все еще есть что-то неясное:
1) Для метода I пара {5, 3} и{3, 5} будет иметь одинаковое хеш-значение (x ^ y), но эти две линии имеют разный наклон!Почему это не вызывает проблемы рассмотрения обеих линий на одном и том же наклоне?Или значение хеш-функции определяет только интервал, который должен быть хеширован, а сравнение эквивалентности фактического значения пары определяет, считать ли их равными?
2) Поскольку пары {5, 3} и {3, 5} будет хешироваться в тот же слот, и есть много других подобных коллизий, таких как {a, b} и {b, a}.Почему хэш-таблица столкновений все еще дает правильный конечный результат?
3) XOR для отрицательных целых чисел - это хорошо, верно?Есть ли лучшая хеш-функция, которую мы обычно используем здесь, чтобы избежать сильных коллизий?
struct hashfunc
{
//Method I:
size_t operator() (const pair<int,int>& l) const
{ return l.first ^ l.second; }
//Method II is WRONG: can NOT left shift negative int!!
size_t operator() (const pair<int, int>& l) const {
return l.first << 32 | l.second;
}
};
unordered_map< pair< int,int >, int, hashfunc> lines;