Структура данных со временем вставки O (1) и поиском O (log m)?

Предыстория (перейдите к предпоследнему абзацу для части структуры данных): Я работаю над алгоритмом сжатия (разновидности LZ77). Алгоритм сводится к поиску самого длинного совпадения между заданной строкой и всеми строками, которые уже были просмотрены.

Чтобы сделать это быстро, я использовал хеш-таблицу (с отдельной цепочкой) , как рекомендовано в спецификации DEFLATE : я вставляю каждую строку, увиденную до сих пор, по одной (по одной на входной байт) с m слотов в цепочке для каждого хэш-кода. Вставки выполняются быстро (постоянное время без условной логики), но поиск выполняется медленно, потому что мне нужно смотреть на строки O ( m ), чтобы найти самое длинное совпадение.Поскольку в типичном примере я выполняю сотни тысяч вставок и десятки тысяч поисков, мне нужна высокоэффективная структура данных, если я хочу, чтобы мой алгоритм работал быстро (в настоящее время он слишком медленный для m > 4; Я бы хотел м ближе к 128).

Я реализовал особый случай, когда m равно 1, который выполняется очень быстро, но предлагает только среднее сжатие. Сейчас я работаю над алгоритмом для тех, кто предпочитает улучшенную степень сжатия скорости, где чем больше m , тем лучше сжатие (до определенной степени, очевидно). К сожалению, мои попытки пока слишком медленны для скромного увеличения степени сжатия при увеличении м .

Итак, я ищу структуру данных, которая допускает очень быструю вставку (поскольку я выполняю больше вставок, чем поисков), но все же достаточно быстрый поиск (лучше, чем O ( m )). Существует ли структура данных поиска O (1) и O (log m ))? В противном случае, какую структуру данных лучше всего использовать? Я готов пожертвовать памятью ради скорости. Я должен добавить, что на моей целевой платформе прыжки (ifs, циклы и вызовы функций) очень медленные, как и распределение кучи (я должен реализовать все сам, используя необработанный массив байтов, чтобы получить приемлемую производительность).

До сих пор я думал о хранении строк m в отсортированном порядке, что позволило бы выполнять поиск O (log m ) с использованием двоичного поиска, но затем и вставки становится O (log m ).

Спасибо!