Давайте Лисп вспомним. (С) Оффтоп

# /bin/time perl -le 'for my $j (1e9..1e9+10000) { my %h; for(my $i = 0;$i < 1000; ++$i) { $h{rand()*1e6} = $i } }'
17.65user 0.00system 0:17.65elapsed

# /bin/time perl -le 'for my $j (1e9..1e9+10000) { my %h; for(my $i = 0;$i < 1000; ++$i) { $a[rand()*1e6] = $i } }'
3.64user 0.03system 0:03.67elapsed

в двоичной системе - да, примерно 101 раз

проверил на побыстрее машинке
# /bin/time perl -le 'for my $j (1e9..1e9+10000) { my %h; for(my $i = 0;$i < 1000; ++$i) { $h{rand()*1e6} = $i } }'
8.01user 0.00system 0:08.01elapsed

/bin/time perl -le 'for my $j (1e9..1e9+10000) { my %h; for(my $i = 0;$i < 1000; ++$i) { $a[rand()*1e6] = $i } }'
1.63user 0.01system 0:01.64elapsed

да, с my промахнулся с массивами

my %h; for(my $i = 0;$i < 1000; ++$i) { $h{$i} = $i }

my @a; for(my $i = 0;$i < 1000; ++$i) { $a[$i] = $i }

Скобочки принципиально рпзные

@atemik, а зачем в примерах используется %h ?

у тебя во втором примере какой-то массив @a появляется

Да там my вообще не нужен. либо %h либо @a используется

а какой смысл назначать случайный индекс для массива? )

что ты проверял этим тестом?

Что, сеньору западло ответить? Это ж просто, ты демонстрируешь имеющиеся навыки/знания, это не должно быть особо напряжно. Обычно, сеньоры имеют уже опыт по обучению более младших товарищей или приобретут его, так что им не должно быть западло ответить на простой вопрос. В твоих же ответах я видел скорее неуверенность. О(1) можно говорить про сами хеши и то с оговорками, но ключ ещё посчитать надо и его алгоритм линеен от длины ключа в символах.

Ну и так далее: вопрос был именно про разницу, её и надо подчеркнуть и описать, это покажет фундаментальные знания. Если же претендент пытается сказать "да пофиг, тут не существенно", то это может быть попыткой скрыть недостаток фундаментальных знаний.

Да я просто не понимаю, какой ответ ты хочешь услышать. В твоем примере, и на твоем вопросе "в чем принципиальная разница" - я могу только спросить, а где тут _принципиальная_ разница?

если ты о том, что в некоторых языках, типа awk, js, php и, видимо, lua, нет отдельно хешей, а массивы называют ассоциативными и просто в некоторых случаях в качестве ключа выступает целочисленный индекс, то мне это известно. и, буквально, каждый раз затем авторы и пользователи языков открывали для себя чудодейственные "нормальные" массивы, которые внезапно работают заметно быстрее и требуют меньше памяти

алгоритм, как правило, имеет два типа стоимости: скорость выполнения и требования к ресурсам. вот по этим показателям и надо сравнить, они принципиальные. то что ты написал "_принципиальная_", ты имел в виду "большая" или "значимая". ну так вот, на коротких тестах/микробенчмарках у меня современный перл требовал для хешей в два раза больше памяти и в два раза медленнее, чем для массивов. если для тебя в два раза это "не существенно", ну я не знаю. когда, к примеру, большая часть памяти занята данными из таблиц, а строки лежат в хешах, а не массивах, то это прямой перерасход ресурсов в два раза.

Для меня "в два" раза - это не существенно, по сравнению с O(1) или O(n), это уже решается, если критично, другими методами.

Микробенчи я нарисовал, там разница в 5 раз, если это критично, то профайлим и смотрим

я уже несколько раз рассказывал, как один миддл у меня написал сравнение первого символа в строке: он разбил строку сплитом посимвольно и сравнил первый элемент. в сравнении с субстр или регексп это медленнее в 20 раз, я забенчмаркал. но если считать разницу в 20 раз константой, то у него, по мнению Артёма, был нормальны алгоритм — О то не изменилось

Гуд

А сколько общего времени выполнения этот regexp/substr занимал?

не важно. программа складывается из множества мелких деталей. нет смысла отдельные делать плохо, когда это не так уж трудоёмко