Хэш-функция для целых чисел ниже 5000? - PullRequest
Новая
       6

Хэш-функция для целых чисел ниже 5000?

0 голосов
/ 16 ноября 2011

Какая самая лучшая и самая простая хеш-функция, которая генерирует уникальные хеш-значения для целых чисел ниже 5000?

Фактическая проблема заключается в том, что у меня есть целочисленный массив размером около 50, содержащий значения от 1 до 5000. Теперь мне нужно сделать обратное отображение, т.е. получить значение, и мне нужно выяснить индекс, в котором оно хранится. Я знаю, что это можно сделать с помощью бинарного поиска, поскольку мой массив отсортирован.

Пожалуйста, не предлагайте никаких хеш-библиотек для C.

1 Ответ

5 голосов
/ 16 ноября 2011

Если 5 КБ пространства массива для 8-битных (char) значений не слишком велики, не беспокойтесь о хэше - используйте числа в качестве индексов в массиве символов, сохраняя 1, чтобы указать, что число является используется и 0, чтобы указать, что это не используется. Вы можете уменьшить это еще больше, используя массив в качестве битовой карты (поэтому вам нужно около 625 байтов для хранения 5000 битов) для хранения, плюс небольшой код для вычисления правильной позиции бита для просмотра.

Или, учитывая, что вам нужно найти индекс в массиве из 50 целых чисел, используйте 5 КБ пространства для хранения индексов в массиве из 50 целых чисел, причем, возможно, -1 означает, что число не используется. 

int main_array[50];
signed char aux_array[5000];

// initialize aux_array to all -1
for (int i = 0; i < sizeof(aux_array); i++)
    aux_array[i] = -1;
// for each value `v` in main_array, store its index `i` in `aux_array[v]`
for (int i = 0; i < num_values; i++)
{
    int v = main_array[i];
    if (aux_array[v] != -1)
        ...non-unique data in main_array...
    aux_array[v] = i;
}

Обратный поиск проверяет в aux_array, чтобы увидеть, является ли индекс -1 (не присутствует) или неотрицательным, чтобы указать, где он найден. Это перевернутый индекс. Если вам понадобится более 127 значений, вы можете переключиться на unsigned char или short вместо signed char (с соответствующими настройками значения маркера, -1 в моем примере).

Хеширование, вероятно, неэффективно.

...