Как бы вы разработали функцию для идеального хэша?

Question

Область интересов - сопоставление строк. Предположим, у меня есть такая структура.

typedef struct
{
    char *name,
    int (*function)();

} StringArray

StringArray s[] = 
{
    {"George", func1},
    {"Paul",   func2},
    {"Ringo",  func3},
    {"John",   func4},
    {"",       NULL}   /* End of list */ 
}

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

Я хочу применить хеш-функцию к строке, и если строка соответствует одной в массиве, затем вызовите функцию. Для этого нужна идеальная хеш-функция. Коллизии не допускаются. Цель хеширования - получить производительность O (1) при поиске.

Какие у вас есть идеи по разработке функции для этого?

Answer 1

См. Домашнюю страницу gperf .

Answer 2

В сводке перечислены как C, так и C ++. Кого из них ты ищешь? C и C ++ - это два разных языка, и они сильно различаются по обработке строк и структурам данных (и тот факт, что C работают в C ++, это не меняет).

Почему именно вам нужна идеальная хеш-функция? Вы хотите связать строку с функцией и подумали, что это будет хорошим способом сделать это? Это какое-то домашнее задание? У вас есть причина не использовать map <> в C ++? (Или unordered_map <>, если доступно?)

Если вам нужен идеальный хеш, каковы ограничения на строки? Будет ли определенный фиксированный набор, на который вы хотите отправить? Как насчет строк, которые не соответствуют одному из набора? Готовы ли вы принимать попадания из случайных строк или количество входящих строк ограничено?

Если бы вы могли отредактировать свой вопрос, включив в него такую ​​информацию, мы могли бы быть намного более полезными.

РЕДАКТИРОВАТЬ (в ответ на первые два комментария):

ОК, мы должны взглянуть на решения C, так как вы, вероятно, хотите, чтобы это работало как на C, так и на C ++. Вы, вероятно, хотите производительность, но вы проверяли? Если мы имеем дело со строками, поступающими в систему ввода / вывода, то время, которое там, вероятно, будет сокращать время отправки.

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

Рассматривали ли вы три ? Она может быть более эффективной, чем совершенная хеш-функция (или может не быть), ее должно быть довольно легко реализовать в C, и это позволит избежать проблем с повторением списка отправляемых строк или возможных коллизий.

Answer 3

См:

Что такое хорошая хэш-функция?

Лучший алгоритм хеширования с точки зрения коллизий хеша и производительности

Что такое эффективная функция хеширования строки, которая приводит к 32-разрядному целому числу с низкой частотой столкновений ?

Выбор множителя для хеш-функции (строки)

Хэш-функция очень низкой стоимости

Какой алгоритм хеширования лучше использовать для строки stl при использовании hash_map?

Answer 4

Окончательный результат этого упражнения был

• Похищение ряда строковых хеш-функций из сети.
• Создайте своего рода фабричный класс, который проверял каждую из функций по набору данных с диапазоном значений операторов мод, ища наименьший идеальный хеш, который работает с этой функцией.
• Этот конструктор класса фабрики по умолчанию возвращает строку, которая представляет набор аргументов, которые при использовании выбирают правильную хеш-функцию и размер мода, чтобы получить идеальный хеш, который требует наименьшего объема памяти.
• при обычном использовании вы просто создаете экземпляр класса с возвращенными аргументами, и класс переводит себя в рабочее состояние с нужными функциями.
• Этот конструктор проверяет отсутствие коллизий и прерывает их работу.
• В случае, когда идеальный хеш не найден, он превращается в бинарный поиск по отсортированной версии входной таблицы.

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

Спасибо всем, кто поделился идеями.

Evil

Answer 5

Используйте сбалансированное двоичное дерево. Тогда вы ЗНАЕТЕ поведение ВСЕГДА O (logn).

Мне сильно не нравятся хэши. Люди не осознают, насколько они рискуют своим алгоритмом. Они запускают некоторые тестовые данные и затем внедряются в полевых условиях. Я НИКОГДА не видел, чтобы развернутый алгоритм хеширования проверялся на поведение в поле.

O (log n) почти всегда приемлемо вместо O (1).

Answer 6

Ну, нет идеальной хэш-функции.

У вас есть несколько, которые минимизируют коллизии, но никто не устраняет их.

Не могу, однако, посоветовать: P

EDIT: Решением не может быть нахождение идеальной хеш-функции. Решение состоит в том, чтобы быть в курсе столкновений. Обычно хеш-функция имеет коллизии. Это, очевидно, зависит от набора данных и размера результирующего хеш-кода.

Answer 7

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

Я бы применил один из существующих распространенных алгоритмов сильного хеширования, например: MD5 или SHA. Вокруг множество образцов, вот, например, http://www.codeproject.com/KB/security/cryptest.aspx

Answer 8

Вы можете использовать карту

std::string foo() { return "Foo"; }
std::string bar() { return "Bar"; }

int main()
{
   std::map<std::string, std::string (*)()> m;
   m["foo"] = &foo;
   m["bar"] = &bar; 
}