Хеширование для равномерного распределения значения в большом диапазоне

Question

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

Какой алгоритм хеширования мне следует использовать для этого?Я пишу код на Java.

Answer 1

Если вы просто хешируете целые числа, вот один из способов.

public class Hasho {

    private static final Long LARGE_PRIME =  948701839L;
    private static final Long LARGE_PRIME2 = 6920451961L;

    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            System.out.println(i + " -> " + hash(i));
        }
    }

public static int hash(int i) {
    // Spread out values
    long scaled = (long) i * LARGE_PRIME;

    // Fill in the lower bits
    long shifted = scaled + LARGE_PRIME2;

    // Add to the lower 32 bits the upper bits which would be lost in
    // the conversion to an int.
    long filled = shifted + ((shifted & 0xFFFFFFFF00000000L) >> 32);

    // Pare it down to 31 bits in this case.  Replace 7 with F if you
    // want negative numbers or leave off the `& mask` part entirely.
    int masked = (int) (filled & 0x7FFFFFFF);
    return masked;
    }
}

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

Answer 2

Я уверен, что у этого есть имя, но это то, что мы привыкли делать с файлами ISAM в темные века

1. Увеличение числа, например, 16001
2. ОбратноеСтрока т.е.10061 и у вас есть хеш
3. Возможно, вы захотите перевернуть строку по битам

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