Функция хэша беспорядка для конкретной структуры данных

Question

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

1. структура данных является INT [] [] []
2. Он не содержит дубликатов
3. Диапазон целых чисел, которые содержатся в нем определены. Предположим, что это 0..1000, максимальное целое число определенно не превышает 10000.

Большая проблема в том, что эта функция хэширования также должна быть очень быстрой. Есть ли способ создать такую ​​хэш-функцию? Может быть, во время выполнения в зависимости от целого диапазона?

ДОПОЛНЕНИЕ: Я должен сказать, что цель этой хеш-функции состоит в том, чтобы проверить, была ли обработана конкретная комбинация. Поэтому, когда обрабатывается некоторая комбинация чисел в структуре данных, я вычисляю значение хэша и сохраняю его. Затем при обработке другой комбинации чисел в структуре данных я буду сравнивать хэш-значения.

Answer 1

Я думаю, что вы хотите, это «идеальный хэш» или даже «минимальный совершенный хэш»:

http://en.wikipedia.org/wiki/Perfect_hash_function

Edit: Это говорит, если вы уверены, и уверены, что вы никогда не будете идти выше [0 ... 1000], и в зависимости от того, что вам нужно сделать, вы, вероятно, можете просто «выставить» ваши результаты непосредственно в массиве. Если у вас мало элементов, этот массив будет разрежен (и, следовательно, немного отходов), но не более 1001 элементов, идущих от [0 ... 1000] объекта [1001] (или int [1001] или что бы там ни было).

Answer 2

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

что-то вроде (с верхней части моей головы): hash = (a << 34) | (b << 17) | (c)

Answer 3

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

Работает ли вам bool[][][], где true означает, что определенная комбинация x, y, z была обработана? Ниже приведен прототип для трехмерного битового массива. Из-за пределов Int32 это будет работать только с максимальным индексом около 1024 (но будет соответствовать 128 МБ). Вы можете получить до 10 000, создав BitArray [] []. Однако это, вероятно, нецелесообразно при таком размере, поскольку он будет занимать более 116 ГБ ОЗУ.

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

public class ThreeDimensionalBitArray 
{ 
    // todo: consider making the size configurable 
    private const int MAX_INDEX = 1000; 

    private BitArray _bits = new BitArray(MAX_INDEX * MAX_INDEX * MAX_INDEX); 

    public bool this[int x, int y, int z] 
    { 
     get { return _bits[getBitIndex(x, y, z)]; } 
     set { _bits[getBitIndex(x, y, z)] = value; } 
    } 

    public ThreeDimensionalBitArray() 
    { 
    } 

    private static int getBitIndex(int x, int y, int z) 
    { 
     // todo: bounds check x, y, and z 

     return (x * MAX_INDEX * MAX_INDEX) + (y * MAX_INDEX) + z; 
    } 
} 


public class BitArrayExample 
{ 
    public static void Main() 
    { 
     ThreeDimensionalBitArray bitArray = new ThreeDimensionalBitArray(); 
     Console.WriteLine(bitArray[500, 600, 700]); // "false" 
     bitArray[500, 600, 700] = true; 
     Console.WriteLine(bitArray[500, 600, 700]); // "true" 
    } 
}