Почему доступ по элементу в массиве происходит за O(1)?

Это вопрос буквально с последнего собеседования. Как я узнал позже, это вопрос задается для того, чтобы увидеть, как человек мыслит. Ясно, что практического смысла в этих знаниях немного: хватает только лишь знания этого факта.

Для начала нужно уточнить, что O(1) — это обозначение временной сложности алгоритма, когда операция проходит за константное время. То есть это обозначение самого быстрого выполнения.

Чтобы ответить на этот вопрос, нужно понять, что мы знаем о массивах?

Чтоб создать массив int, мы должны написать следующее:

int[] intArray = new int[100];

Из этой записи можно сделать несколько выводов:

При создании массива известен его тип.Если известен тип, то понятно, какого размера будет каждая ячейка массива.

Известно, какого размера будет массив.

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

Для машины это проще простого. У машины есть начало выделенной памяти, количество элементов и размер одной ячейки.

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

А как получается О(1) в доступе к объектам в ArrayList?

Это вопрос сразу же идет за предыдущим. Ведь правда, когда мы работаем с массивом и там примитивы, то нам известно заранее, какой размер этого типа, при его создании.

А что делать, если есть такая схема, как на картинке:

Топ-50 Java Core вопросов и ответов на собеседовании. Часть 1 - 8и мы хотим создать коллекцию с элементами, у которых тип A, и добавить разные реализации — B, C, D:

List list = new ArrayList();

list.add(new B());

list.add(new C());

list.add(new D());

list.add(new B());

Как в этой ситуации понять, какой будет размер у каждой ячейки, ведь каждый объект будет разным и может иметь разные дополнительные поля (или быть полностью различными). Что делать?

Здесь вопрос ставится так, чтобы запутать и сбить с толку.

Мы же знаем, что на самом деле в коллекции хранятся не объекты, а лишь ссылки на эти объекты. А у всех ссылок размер один и тот же, и он известен. Поэтому здесь работает подсчет места так же, как и в предыдущем вопросе.

Источник: vk.com

Комментарии: