Быстрый диктонар в С без линейного поиска

Question

Как я могу сделать быстрый диктонар (String => Pointer и Int => Pointer) в C без линейного поиска? Мне нужно несколько (или более) строк кода, а не библиотека, и должна быть возможность использовать его в программном обеспечении с закрытым исходным кодом (LGPL, ...).

Answer 1

Использование хеш-таблицы . Хэш-таблица будет иметь поиск в постоянном времени. Вот некоторые выдержки из C и реализации в C (и португальском:) .

Answer 2

Вам необходимо реализовать Хеш-таблицу , в которой объекты хранятся с использованием хеш-кода. Время поиска постоянно.

A Двоичное дерево может проходить и искать элемент в log (n) времени.

Answer 3

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

если вы хотите использовать хеширование, посмотрите на karp-rabin. если вы хотите, чтобы алгоритм зависел ТОЛЬКО от размера искомого слова, пожалуйста, посмотрите на aho-corasick.

Answer 4

Троичное дерево поиска было рождено для этой миссии.