Простой LRU cache состоит из списка (O(1) на вставку и удаление элемента) и хэш-таблицы (O(n) но что важнее Θ(1) на поиск элемента) и из-за разницы Θ на поиск и используется хэш-таблица.
Поиск в хэш-таблице будет O(n) если все значения будут в коллизии (выродится в список), go реализация хэш-таблицы в таком случае перераспределяет значения, что формально дает O(1) на поиск, но по факту на вставке будут еще затраты на GC, перевыделение памяти и перераспределение ключей.
Для того чтобы получить гарантированно O(1) на поиске можнр использовать обычный массив так как он дает O(1) на доступ по индексу. Это может сработать для случая когда у нас небольшое непрерывное множесто ключей, которое мы может однозначно положить на индексы массива (например ASCII) и имеет смысл если затраты на извлечение значения значительны и вытеснения редки.
P.S. a) Реализация на типе int выбрана исходя из контекста задачи b) Реализация не thread-safe (может быть легко реализовано с помощью RWMutex)