> Если хеш автоматически не меняет свой размер, то с ростом количества записей скорость доступа будет уменьшаться как O(количества ключей / количество ячеек в хеш-таблице), что по сути есть O(n).

скорость доступа всегда O(1), даже если при возникновении коллизии мы проведем повторную операцию хеширования получим O(2) = O(1). есть методы заполнения позволяющие иметь кпд хеша 95% при максимум 3х вычеслениях хеша на операцию записи/чтения, что O(3) = O(1).

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

> Хеш-таблица подходит для случаев, когда количество ключей сравнимо с размером таблицы, т.е. максимум в несколько раз больше.

Читайте выше и дальше - это тоже самое начало любого учебника, есть методы быстрого заполнения хеша на 95%.