О структуре таблиц Ассемблера
Структура таблиц Ассемблера выбирается таким образом, чтобы обеспечить максимальную скорость поиска в них.
Таблицы команд и директив являются постоянной базой данных. Они заполняются один раз - при разработке Ассемблера, а затем остаются неизменными. Эти таблицы целесоообразно строить как таблицы прямого доступа с функцией хеширования, осуществляющей преобразование мнемоники в адрес записи в таблице. Имеет смысл постараться и подобрать функцию хеширования такой, чтобы в таблице не было коллизий. Поскольку заполнение таблицы происходит один раз, а доступ к ней производится многократно, эти затраты окупаются.
Таблица символов формируется динамически - в процессе работы 1-го прохода. Поиск же в этой таблице осуществляется как в 1-ом проходе (перед занесением в таблицу нового имени, проверяется, нет ли его уже в таблице). Построение этой таблицы как таблицы прямого доступа не очень целесообразно, так как неизбежно возникновение коллизий. Поэтому поиск в таблице символов может быть дихотомическим, но для этого таблица должна быть упорядочена. Поскольку новые имена добавляются в таблицу "по одному", и после каждого добавления упорядоченность таблицы должна восстанавливаться, целесообразно применять алгоритму сортировки, чувствительные к исходной упорядоченности данных.
Эти же соображения относятся и к другим таблицам, формируемым Ассемблером в процессе работы. При больших размерах таблиц и размещении их на внешней памяти могут применяться и более сложные (но и более эффективные) методы их организации, например - B+-деревья.
