Почему dict в python реализован как хэш-таблица, а std::map - как дерево?

Почему один язык использует дерево, а другой - хэш-таблицу для, казалось бы, похожей структуры данных?

c++'s map vs python's dict

Смежный вопрос о производительности хэш-таблицы.
Пожалуйста, прокомментируйте мое понимание хэш-таблицы ниже.

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

Следовательно, хэш-таблица полезна только для определенного диапазона размеров задачи, и именно поэтому большинство БД используют дерево, а не хэш-таблицу.