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

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

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

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

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

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

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

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

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

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

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

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

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

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

См .:

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

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

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

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

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

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

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

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

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

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

Не могу посоветовать хотя бы одну: P

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