Какая структура данных будет иметь самое быстрое время для поиска и вставки функций? - PullRequest
2 голосов
/ 22 февраля 2010

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

Ответы [ 3 ]

2 голосов
/ 22 февраля 2010

Хеш-таблицы очень часто используются для этого. Простая реализация с N корзинами и хэш-функцией, которая принимает сумму букв в каждом символе (мод N), должна быть очень близка к O (1) при вставке и поиске.

2 голосов
/ 22 февраля 2010

Словарь / Hashtable имеет скорость поиска O (1), если я не ошибаюсь.

1 голос
/ 07 ноября 2010

О поиске по хеш-таблице - это O (1), только если не происходит ни одного или нескольких коллизий - поэтому при условии, что у вас есть соответствующая хеширующая функция, обычно это O (1), но в худших случаях это может привести к O (N) , Хорошая оценка размера данных имеет решающее значение.

И вы также должны учитывать временную сложность функции хеширования, которую вы намереваетесь использовать

...