Зависит от операции. Доступ к элементу Array по числовому индексу обычно O(1), поиск ключа Hash — ожидаемо O(1). Поиск произвольного значения в обеих коллекциях обычно требует O(n). Добавление в конец массива амортизированно O(1), вставка или удаление в середине — O(n). Хеш не обязан быть быстрее прямого доступа по индексу; учитывают размеры, ключи и расход памяти.
Что быстрее в Ruby: массив или хеш?
Сравнение Array и Hash для доступа, поиска и изменения данных: почему без указания операции нельзя выбрать победителя.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Сначала уточните, что сравнивается. Массив хранит последовательность, а хеш связывает ключ со значением; они решают разные задачи.
| Операция | Array | Hash |
|---|---|---|
| Получить элемент по индексу или ключу | Обычно O(1) по индексу | Ожидаемо O(1) по ключу |
| Найти произвольное значение | Обычно O(n) | Обычно O(n) |
| Добавить элемент | В конец — амортизированно O(1) | Ожидаемо O(1) |
| Удалить элемент | Из середины — O(n) из-за сдвига | По ключу — ожидаемо O(1) |
Оценки предполагают обычную реализацию и ограниченную стоимость операций над ключом. У Hash есть вычисление хеша и обработка коллизий; у сложного ключа само вычисление может быть дорогим. У массива при увеличении ёмкости иногда требуется копирование, поэтому говорят именно об амортизированной стоимости добавления.
names = ["Anna", "Boris"]
by_id = { 42 => "Anna", 73 => "Boris" }
names[1] # "Boris": позиция известна
by_id[73] # "Boris": известен идентификатор
names.include?("Boris") # поиск значения, а не доступ по индексу
Для частой проверки наличия идентификатора хеш обычно удобнее полного просмотра массива. Для последовательного обхода или доступа по позиции массив естественнее и может требовать меньше памяти. Утверждать, что хеш всегда быстрее, нельзя: на малых коллекциях константные расходы нередко важнее асимптотики. Сравнивайте одинаковые операции на характерных данных, учитывая также стоимость построения структуры. Семантика операций: Array и Hash.