Определение идеальной таблицы поиска хеша для Pearson Hash

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

char* pearson(char* name, char* lookup)
{
    char index = '\0';
    while(*name)
    {
        index = lookup[index ^ *name];
        name++;
    }
    return index;
}

Мой вопрос заключается в том, что, учитывая фиксированную группу из менее чем 256 имен членов, как определить lookup стол такой, что pearson() вернет уникальные символы в непрерывном диапазоне, начиная с '\0', Другими словами, мне нужен алгоритм для создания таблицы поиска для идеального хэша. Это позволит мне иметь объекты, которые занимают не больше места, чем количество их членов. Это будет сделано во время компиляции, поэтому скорость не имеет большого значения, но быстрее будет лучше. Это было бы просто, но я думаю (надеюсь), что есть лучший способ.

Вот пример: учитывая переменные-члены 'foo', 'bar' и 'baz' в классе, я хочу определить lookup такой что:

pearson('foo',lookup) == (char) 0
pearson('bar',lookup) == (char) 1
pearson('baz',lookup) == (char) 2

Обратите внимание, что порядок не имеет значения, поэтому следующий результат также будет приемлемым:

pearson('foo',lookup) == (char) 2
pearson('bar',lookup) == (char) 0
pearson('baz',lookup) == (char) 1

В идеальном мире все имена, которых нет в таблице, возвращали бы значение больше 2, потому что это позволило бы мне избежать проверки и, возможно, даже избежать сохранения имен членов, но я не думаю, что это возможно, поэтому Я должен добавить дополнительную проверку, чтобы увидеть, если это в таблице. Учитывая это, это, вероятно, сэкономит время, чтобы не инициализировать значения в таблице поиска, которые не используются (коллизии не имеют значения, потому что, если он сталкивается и не проходит проверку, он вообще не находится в объекте, поэтому коллизия не должен быть решен, только ошибка должна быть обработана).

Источник

3 ответа

Решение

Взгляните на эту страницу о минимальных идеальных хешах - она ​​ссылается на несколько реализаций и имеет короткий раздел с некоторыми мыслями о минимальных идеальных хэшах Пирсона.

Источник

Я сильно сомневаюсь, что вы сможете найти решение с грубой силой, если число имен членов слишком велико. Благодаря парадоксу дня рождения вероятность отсутствия коллизий (т. Е. Два хэша одинаковы) составляет примерно 1:5000 для 64 и 1:850 000 000 для 96 имен членов. Исходя из структуры вашей хеш-функции (она получена из криптографической конструкции, которая предназначена для "хорошего" смешивания вещей), я не ожидаю, что существуют алгоритмы, которые решают вашу проблему (но я определенно был бы заинтересован в таком чудовище).

Ваш идеальный мир - иллюзия (как вы и ожидали): есть 256 символов, которые вы можете добавить к 'foo', ни один из них не может дать новое слово с таким же хешем. Поскольку существует только 256 возможностей для значений хеша, вы можете добавить символ к 'foo', чтобы его хеш был таким же, как любой из хешей 'foo', 'bar' или 'baz'.

Почему вы не используете существующую библиотеку, такую ​​как CMPH?

Источник

Если я вас правильно понимаю, вам нужен отсортированный массив без дублирующихся элементов, по которому можно выполнять бинарный поиск. Если ключ находится в массиве, индексом является "хэш". В противном случае вы получите размер массива. Это O(nlogn) сравнивает с таблицей поиска O(1), но этого достаточно для небольшого количества элементов - 256 в вашем случае.

Источник
Другие вопросы по тегам