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

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

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

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

Answer 3

См:

What is a good Hash Function?

Best hashing algorithm in terms of hash collisions and performance

What is a performant string hashing function that results in a 32 bit integer with low collision rates?

Choosing a multiplier for a (string) hash function

Very low cost hash function

What’s the best hashing algorithm to use on a stl string when using hash_map?

Answer 4

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

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

Answer 5

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

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

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

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

Answer 6

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

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

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

Answer 7

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

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

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

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

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

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

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

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

Answer 8

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

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

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

Благодарю всех, кто внес идеи.

Зла