Без коллизий хеш-функция для конкретной структуры данных - PullRequest
Новая
       7

Без коллизий хеш-функция для конкретной структуры данных

3 голосов
/ 22 апреля 2010

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

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

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

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

Ответы [ 3 ]

6 голосов
/ 22 апреля 2010

Я думаю, что вам нужен "идеальный хеш" или даже "минимальный идеальный хеш":

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

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

0 голосов
/ 15 мая 2016

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

Будет ли bool[][][] работать для вас, где true означает, что определенная комбинация x, y, z была обработана? Ниже представлен прототип для трехмерного битового массива. Из-за ограничений Int32, это будет работать только до максимального индекса около 1024 (но будет в пределах 128 МБ). Вы можете получить до 10000, создав 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"
    }
}
0 голосов
/ 22 апреля 2010

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

что-то вроде (от макушки): hash = (a << 34) | (b << 17) | (c)

...