Хорошая хеш-функция для 2-го индекса
У меня есть структура под названием Точка. Точка довольно проста:
struct Point
{
Row row;
Column column;
// some other code for addition and subtraction of points is there too
}
Row и Column в основном прославлены ints, но я устал от случайного перемещения входных параметров к функциям и дал им каждого класс обертки.
Прямо сейчас я использую a set из точек, но повторенных поисков действительно замедляют вещи. Я хочу переключиться на unordered_set.
Так, я хочу иметь unordered_set из Points. Обычно этот набор мог бы содержать, например, каждую точку на 80x24 терминал = 1 920 точек. Мне нужна хорошая хеш-функция. Я просто придумал следующее:
struct PointHash : public std::unary_function<Point, std::size_t>
{
result_type operator()(const argument_type& val) const
{
return val.row.value() * 1000 + val.col.value();
}
};
Однако я не уверен, что это - действительно хорошая хеш-функция. Я хотел что-то быстро, так как я должен сделать много поисков очень быстро. Существует ли лучшая хеш-функция, которую я могу использовать или это в порядке?
3 ответа
Методика описана в Эффективная Java (2-е издание) и процитирована оттуда в Программирование в Scala . Имейте простую константу (мы скажем 53, но вы можете найти здесь что-то большее, что даст более равномерное распределение) и выполните умножение и сложение следующим образом:
(53 + int_hash(row)) * 53 + int_hash(col)
Для получения дополнительных значений (скажем, вы добавляете координату z) просто продолжайте вложение, например
((53 + int_hash(row)) * 53 + int_hash(col)) * 53 + int_hash(z)
Где int_hash - функция для хеширования одного целого числа. Вы можете посетить эту страницу, чтобы найти набор хороших хеш-функций для отдельных целых чисел.
Имея достаточно небольшой домен, вы можете создать идеальную хеш-функцию. Или, возможно, просто используйте двумерный массив. Для больших объемов данных используйте умножение на основе простых чисел и модифицируйте размер вашей таблицы (и если ваша таблица имеет размер с основанием 2). Это устраняет разделение / модификацию, которое может быть дорогостоящим в небольших системах встроенного типа.
Или найдите любое количество уже существующих целочисленных хеш-функций. Убедитесь, что вы измеряете любую созданную вами хеш-функцию на предмет коллизий. Достаточное количество столкновений устранит любые преимущества по сравнению с методами O (n log n), такими как карты / деревья.
Думаю, сдвиг битов на 10 будет более эффективным, чем умножение на 1000.
return (val.row.value()<<10) + val.col.value();