Что такое структура с произвольным доступом?

Массив и подобные.

Вот есть у тебя структура данных, захотел обратиться к элементу по какому-то адресу, и ХРЕНАК! - обратился. Например элемент в массиве ты можешь достать по номеру (считай, что по адресу). А если бы был последовательный доступ, то к этому элементу надо было бы обращаться, обратившись сперва к предыдущим. Например чтобы достать элемент в стеке, нужно сперва достать «лежащие сверху».

считай, что по адресу

Вот это ключевая фраза:). Спасибо, ясно.

произвольный доступ: массив. «непроизвольный» доступ: списки, деревья, хеши и пр.

хэши?

в чём вопрос?

наверное, анонимус граммар-наци

и это тоже но поскольку у большинства структур данных на основе хэшей амортизированное О(1) по времени, я бы счел нужным это отдельно уточнить.

кроме того, в треде не хватает объяснения на пальцах.

Это когда можно напрямую обратится к любому элементу структуры и любой элемент структуры может обратиться к любому другому элементу другой или этой же структуры.

Ну это как у тебя на полу коробочки в каждой что то есть берёшь любую коробочку и делаешь что тебе надо. И можно из одной коробочки вывалить содержимое в любую другую (если типы совпадают) если коробочки одинакового размера. Или как чемодан у которого всё в своих карманах 1 предмет один карман. То есть зная что где лежит ты получишь это за одно и тоже время.

А вот если коробочки стоят друг на друге и в строгой последовательности то тебе чтобы взять 10тую надо несколько снять сверху взять десятую что-то сделать и положить обратно и положить все что сверху обратно. Как чемодан набитый тряпками, а бритва зараза внизу лежит надо весь чемодан перелопатить пока достанешь бритву, достал побрился, а тут жена говорит «нам ехать пора складывай всё обратно» и суёт бритву опять в дно чемодана и всё сверху укладывает опять. То есть доступ к разным элементам будет занимать разное время.

у большинства структур данных на основе хэшей амортизированное О(1) по времени

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

что тебе неясно в слове «амортизированный»? простой графиков.

что тебе неясно в слове «амортизированный»? простой графиков.

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

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

http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.V...

It provides random access and updates in effectively constant time, as well as very fast append and prepend. [...] It is backed by a little endian bit-mapped vector trie with a branching factor of 32. [...]

Я не спорю, что оговорку «амортизированное/эффективное/whatever» следует опускать, но вот такое имеем.

жаль трудно идентифицировать анонимусов, не всегда знаешь стоит ли отвечать.

Я не спорю, что оговорку «амортизированное/эффективное/whatever» следует опускать, но вот такое имеем.

Это всё зависит от заполненности хеша элементами. Ясно же, что их может быть и много, сравнимо с размером массива корзин, или ты этот вектор, который, как я понял «массив с дырками», предлагаешь в качестве массива корзин?