Хорошая хеш-функция для списка 2-х позиций?

Question

У меня есть ряд объектов, чье единственное внутреннее состояние - это список фиксированной длины (или любой другой) из 2-х позиций (2 целых числа).То есть все они имеют одинаковое количество элементов с (потенциально) разными значениями 2-го уровня.

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

Как бы вы посоветовали мне их хешировать?

Answer 1

точка выбора 31 в качестве вашего простого умножения - умножение с использованием сдвига битов и вычитания.

Скажем, это класс Point:

class Point {
    public final int x;
    public final int y;

    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    @Override
    public int hashCode()
    {
        int hash = 17;
        hash = ((hash + x) << 5) - (hash + x);
        hash = ((hash + y) << 5) - (hash + y);
        return hash;
    }
}

Точкавыбрав 31 в качестве основного числа, можно умножить, используя сдвиг битов и одну операцию вычитания.Обратите внимание, что сдвиг битов на 5 эквивалентен умножению на 32, а вычитание делает это эквивалентным умножению на 31. Эти две операции намного эффективнее, чем одно, истинное умножение.

И тогда ваш объект:

class TheObject
{
    private final java.util.List<Point> points;

    public TheObject(List<Point> points)
    {
        this.points = points;
    }

    @Override
    public int hashCode()
    {
        int hash = 17;int tmp = 0;
        for (Point p : points)
        {
            tmp = (hash + p.hashCode());
            hash = (tmp << 5) - tmp;
        }
        return hash;
    }
}

Answer 2

Хм, а как насчет чего-то вроде бинарного дерева поиска?

Для сравнения в псевдокоде:

position1 > position2 := 
   (position1.x > position2.x) || 
   ((position1.x == position2.x) && (position1.y > position2.y))

list1.x > list2.x := {
    for (i in 0...n) 
        if (list1[i] > list2[i]) return true;
        else if (list1[i] > list2[i]) return false;
    return false;
}

, где n, конечно, длина списков.

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

Таким образом, вы получаете идентификатор (вместо хеша), в котором нет коллизий. В худшем случае сравнение 2 списков - O(n), таким образом, поиск / вставка - O(n) * O(log(m)) (при условии, что дерево сбалансировано), где m - общее количество всех списков.

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

Я мало что могу сказать о среднем, так как вы не даете цифр. На самом деле, я удивлен, что вы не хотите проводить прямое сравнение, поскольку я ожидаю, что вероятность того, что две позиции будут равны, составляет менее 1%, поэтому сравнение по списку составляет около O (1), поскольку вероятность, которая вам нужна для сравнения 5 записей действительно мало.

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

Answer 3

Ну, в зависимости от размера ваших целых чисел, вы можете умножить первую координату на максимально возможную координату и добавить вторую. Например, если X и Y положительны и имеют ограничение 256, вы можете попробовать X * 256 + Y для вашей хэш-функции. Если X и Y также могут быть отрицательными, вы можете сначала сместить их, чтобы сделать их неотрицательными. Кроме того, при умножении X на max переполняется целое число, возможно, вы захотите хеш-значение multi-int или, возможно, mod или побитовый результат, и результат с UINT_MAX.