Как получить самый старый ключ из Map за константное время?

Первый сохранившийся ключ по порядку вставки получают через map.keys().next(). Однако стандарт не обещает строгую O(1) для этого действия во всех реализациях.

Проверяйте done, поскольку undefined может быть допустимым ключом:

const first = map.keys().next();
if (!first.done) console.log(first.value);

Обновление значения ключа не меняет его место; удаление и повторная вставка меняет. Это не «самый давно использованный» ключ для LRU, если порядок не поддерживается явно. Строгие гарантии сложности требуют выбранной структуры данных.