Хэш-функция для 3 шорт - PullRequest
Новая
       49

Хэш-функция для 3 шорт

0 голосов
/ 22 марта 2012

Я должен создать хеш-функцию на основе 3 шорт. Каков наилучший способ сделать это?

Редактировать У меня есть объект под названием Point. Он состоит из трех шорт (х, у, г). Чтобы использовать этот объект в QSet, я должен заполнить тело следующей функции 

uint qHash(const Point &point) {
    // return something here that is a unique combination of x, y, z so that
    // it is very quick to calculate and has minimal (if any) hash collisions
}

Ответы [ 2 ]

2 голосов
/ 22 марта 2012

Это во многом зависит от того, что вам нужно от хэш-функции.

критична ли скорость?

Критически важно почти идеальное распределение хешей?

Насколько большим должен быть ваш хэш-ключ? 32 бита? 64-бит? Изображение большего размера?

Не зная каких-либо других особенностей, вы можете рассмотреть что-то вроде этого: 

uint hash = (31 * 31 * 31 * (uint)short1) ^ (31 * 31 * (uint)short2) ^ (31 * short3);

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

UPDATE

Изменен пример кода для ввода uint. Мой вариант должен хорошо работать, если ввод находится в диапазоне от 0 до 512.

Если вам интересно понять, почему я умножаю каждый вход на степень 31, см.

Почему Java hashCode () в String использует 31 в качестве множителя?

1 голос
/ 22 марта 2012

Если три шорта распределены относительно равномерно, вы можете просто использовать что-то вроде: 

hashVal = (short1 xor short2 xor short3) modulo numBuckets

, что даст вам короткий, уменьшенный до определенного диапазона от 0 до numBuckets - 1.

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

На основании вашего вопроса редактирования, заявив, что хеш должен входить вunsigned int и предполагая 16-битное короткое и 32-битное unsigned int, невозможно полностью избежать коллизий (для этого вам понадобится 48 бит).Одна возможность состоит в том, чтобы использовать: 

hashVal = (x leftshift 16) logical-or (y leftshift 8) logical-or (z)

Это объединит (с логическим или) ваши значения таким образом: 

xxxxxxxxxxxxxxxx0000000000000000
        yyyyyyyyyyyyyyyy00000000
                zzzzzzzzzzzzzzzz

и, по крайней мере, минимизирует возможность одновременных значений x/y/z, влияющих надруг друга.

И, в дополнение к вашему комментарию:

Я ожидаю, что мои входные значения будут в диапазоне от 0 до 512. Как это повлияет на мое решение?

Если ваши входные значения ограничены диапазоном от 0 до 512 (включительно), вам потребуется только десять бит для каждого (что даст вам значения от 0 до 1023).В этом случае три из них легко поместятся в 32-разрядное целое число без знака, поэтому вы можете использовать: 

hashVal = (x leftshift 20) logical-or (y leftshift 10) logical-or (z)

Это дает идеальный хэш, абсолютно без шансов на столкновение.

...