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

Ответ 1

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

Ответ 2

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

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

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

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

EDIT (в ответ на первые два комментария):

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

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

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

Ответ 3

См:

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

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

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

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

Очень низкая хэш-функция

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

Ответ 4

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

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; 
}

Ответ 5

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

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

Ответ 6

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

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

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

Ответ 7

Конечным результатом этого упражнения было

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

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

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

Зло

Ответ 8

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

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

Невозможно сообщить, хотя: P

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