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

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. Вы можете полностью изменить строку побитового

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