Можно ли создать функцию Minimal Perfect Hash без отдельной таблицы поиска для небольшого (<64) набора ключей? - PullRequest
Новая
       46

Можно ли создать функцию Minimal Perfect Hash без отдельной таблицы поиска для небольшого (<64) набора ключей?

9 голосов
/ 24 апреля 2019

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

В статье предполагается, что вам нужна промежуточная таблица. Есть ли другой, более простой способ генерировать такую ​​функцию, если мы предположим, что набор ключей невелик (т. Е. <64). </p>

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

unsigned int thread_ids*;
unsigned int thread_count;
struct {
    /* Some thread specific data */
}* ThreadData;

int start_threads () {
    /* Code which starts the threads and allocates the threaddata. */
}

int f(thread_id) {
    /* return unique index into threadData */
}

int main() {
    thread_count = 64; /* This number will be small, e.g. < 64 */
    start_threads();
    ThreadData[f(thread_ids[0])]
}

Ответы [ 2 ]

1 голос
/ 24 апреля 2019

Да, вы можете создать минимальную идеальную хеш-функцию (MPHF) во время выполнения. Вы можете использовать несколько алгоритмов, но большинство из них немного сложны для реализации, поэтому я не могу дать вам рабочий пример кода. Многие из них реализованы в cmph проекте .

Самый простой, вероятно, BDZ. На высоком уровне поиск требует вычисления 3 хеш-функций и 3 обращений к памяти. Если память не проблема, вам нужно только 2. Она поддерживает миллионы ключей. Этот алгоритм требует таблицу поиска, которая примерно в 1,23 раза превышает количество записей.

Есть и другие алгоритмы, один из которых я сам изобрел, алгоритм RecSplit , но у меня нет реализации на C, только Java прямо сейчас. По сути, алгоритмы находят способ разбить набор на подмножества (рекурсивно), пока размер подмножества не станет равным 1. Вам нужно помнить, как вы разбиваете. На самом деле самое простое решение - это использовать справочную таблицу для «как вы разбиваете», но таблица действительно мала, возможно, всего 5 целых чисел для 64 ключей. Первый разделить на 4 подмножества по 16, и 4 для сопоставления каждого подмножества с числом 0..15.

(Я добавил второй ответ, если вам строго не нужна минимальная идеальная хеш-функция, просто идеальная хеш-функция. Построение проще и поиск выполняется намного быстрее, но требует большего массива.)

0 голосов
/ 25 апреля 2019

Вы можете создать хеш perfect следующим образом, используя поиск методом грубой силы.Для 64 записей размер целевого массива должен составлять не менее 512 записей, иначе поиск не найдет индекс в течение разумного времени.

Тогда идеальная хеш-функция равна murmur(x + perfectHashIndex) & (TARGET_SIZE - 1)

#include <stdio.h>
#include <stdint.h>
#include <string.h>

static uint64_t murmur64(uint64_t h) {
    h ^= h >> 33;
    h *= UINT64_C(0xff51afd7ed558ccd);
    h ^= h >> 33;
    h *= UINT64_C(0xc4ceb9fe1a85ec53);
    h ^= h >> 33;
    return h;
}

// must be a power of 2
#define TARGET_SIZE 512

static uint64_t findPerfectHashIndex(uint64_t *array, int size) {
    uint64_t used[TARGET_SIZE / 64];
    for (uint64_t index = 0; index < 1000;) {
        memset(used, 0, TARGET_SIZE / 64 * sizeof(uint64_t));
        for (size_t i = 0; i < size; i++) {
            uint64_t x = murmur64(array[i] + index) & (TARGET_SIZE - 1);
            if (((used[x >> 6] >> (x & 63)) & 1) != 0) {
                goto outer;
            }
            used[x >> 6] |= 1UL << (x & 63);
        }
        return index;
        outer:
        index++;
    }
    // not found
    return -1;
}

int main() {
    int size = 64;
    uint64_t ids[size];
    for(int i=0; i<size; i++) ids[i] = 10 * i;
    uint64_t perfectHashIndex = findPerfectHashIndex(ids, size);
    if (perfectHashIndex == -1) {
        printf("perfectHashIndex not found\n");
    } else {
        printf("perfectHashIndex = %lld\n", perfectHashIndex);
        for(int i=0; i<size; i++) {
            printf("  x[%d] = %lld, murmur(x + perfectHashIndex) & (TARGET_SIZE - 1) = %d\n", 
                i, ids[i], murmur64(ids[i] + perfectHashIndex) & (TARGET_SIZE - 1));
        }
    }
}
...