Ответ 1
Смотрите домашнюю страницу gperf.
Область интересов - соответствие строк. Предположим, у меня есть такая структура.
typedef struct
{
char *name,
int (*function)();
} StringArray
StringArray s[] =
{
{"George", func1},
{"Paul", func2},
{"Ringo", func3},
{"John", func4},
{"", NULL} /* End of list */
}
В массиве фиксированное количество строк. Они жестко закодированы, как в примере. Если таблица изменится, возникнет необходимость переоценить качество хеш-функции.
Я хочу применить хеш-функцию к строке, и если строка соответствует одному в массиве, затем вызовите функцию. Для этого нужна идеальная хеш-функция. Не допускается коллизий. Целью хэширования является получение производительности O (1) при поиске.
Какие у вас идеи по созданию функции для этого?
Смотрите домашнюю страницу gperf.
В сводке перечислены как C, так и С++. Какие из них вы ищете? C и С++ - это два разных языка и сильно различаются в строковой обработке и структурах данных (и тот факт, что C-те, которые работают на С++, не меняют это).
Почему, в частности, вы хотите идеальную хэш-функцию? Это то, что вы хотите связать строку с функцией, и подумал, что это будет хороший способ сделать это? Это какое-то домашнее задание? У вас есть причина не использовать map < > в С++? (Или unordered_map < > если доступно?)
Если вам нужен идеальный хеш, каковы ограничения на строки? Будет ли определенный фиксированный набор, на который вы хотите отправить? Что относительно строк, которые не соответствуют одному из наборов? Готовы ли вы принимать удары из случайных строк или количество входящих строк ограничено?
Если бы вы могли отредактировать свой вопрос, чтобы включить такую информацию, мы могли бы быть намного полезнее.
EDIT (в ответ на первые два комментария):
ОК, мы должны рассмотреть решения C, так как вы, по-видимому, хотите этого для работы на C и С++. Вы, по-видимому, хотите исполнения, но вы протестировали? Если мы имеем дело со строками, входящими в систему ввода-вывода, время, которое, вероятно, затмит время отправки.
Вы ожидаете произвольные строки. Это немного, чтобы ожидать идеальной хэш-функции, которая позволит избежать всех столкновений от случайных данных, поэтому вам нужно это учитывать.
Считаете ли вы trie? Он может быть более эффективным, чем идеальная хэш-функция (или может и не быть), ее следует довольно легко реализовать на C, и это позволит избежать проблем с переделкой списка строк отправки или возможных столкновений.
См:
Что такое хорошая функция хэша?
Лучший алгоритм хэширования с точки зрения хэш-коллизий и производительности
Вы можете использовать карту
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;
}
Если коллизии абсолютно не разрешены, единственным вариантом является отслеживание каждой строки в базе данных, что, вероятно, не лучший способ.
Я бы применил один из существующих общих сильных алгоритмов хеширования, таких как: MD5 или SHA. Там мириады образцов все вокруг, вот один пример: http://www.codeproject.com/KB/security/cryptest.aspx
Используйте сбалансированное двоичное дерево. Тогда вы ЗНАТЬ поведение ВСЕГДА O (logn).
Я сильно не люблю хеши. Люди не понимают, сколько рисков они берут с помощью своего алгоритма. Они запускают некоторые тестовые данные, а затем развертывают их в полевых условиях. Я НИКОГДА не видел, чтобы развернутый хэш-алгоритм проверялся на поведение в поле.
O (log n) почти всегда приемлемо вместо O (1).
Конечным результатом этого упражнения было
Для набора массивов, которые у меня есть в моем домене, это работает очень хорошо. Возможной будущей оптимизацией было бы проведение такого же тестирования, как и подстроки ввода. В случае примера первая буква каждого имени музыкантов достаточно, чтобы рассказать им обособленно. Тогда нужно будет уравновесить стоимость фактической хэш-функции против используемая память.
Спасибо всем, кто внес идеи.
Зло
Ну, нет идеальной хэш-функции.
У вас есть несколько, которые сводят к минимуму столкновения, но никто не устраняет их.
Невозможно сообщить, хотя: P
EDIT: Решение не может найти идеальную хэш-функцию. Решение должно быть известно о столкновениях. В общем случае хэш-функция имеет коллизии. Это, очевидно, зависит от набора данных и размера полученного хеш-кода.