#java #oop #data-structures
#java #ооп #структуры данных
Вопрос:
В чем именно разница между индексированными и последовательными структурами данных? Например, HashSet является индексированной структурой данных, но TreeSet является последовательным.
Комментарии:
1. Логический порядок индексированной структуры данных не обязательно совпадает с физическим порядком. Я не думаю, что набор деревьев является последовательным.
2. Я думаю, что indexd означает, что реализация подчеркивания использует массив, а последовательное использование связанного списка.
Ответ №1:
В java эти термины не имеют установленных значений. Значения будут получены из повседневного использования английского языка и из изучения типов, которые вы перечислили.
«Индексированный» будет означать, что существует индекс, связанный со структурой данных и который может использоваться для ссылки на элементы структуры данных, причем самым простым примером является массив, который индексируется по целочисленному смещению или Map индексируется по значениям ключа. Обратите внимание, что при этом отсутствует представление о структуре данных, имеющей естественный порядок. Мы можем видеть, что массивы имеют естественный порядок, но Map не имеют.
«Последовательный» будет означать, что структура данных имеет порядок, который может использоваться для упорядочения операций над элементами структуры данных. Есть смысл, что это должен быть естественный порядок, но этот термин также может означать, что существует порядок, наложенный на структуру данных, который позволяет выполнять итеративные операции.
Ни в том, ни в другом случае значения не должны включать ссылку на конкретные операции. Структура данных может поддерживать чтение, запись или итерацию, но не обязательно поддерживать что-либо или все из них. Например, последовательная структура данных может поддерживать findFirst операцию, не разрешая итерацию как внешнюю операцию.
Для двух ссылочных типов HashSet и TreeMap , поскольку это типы реализации, термины могут использоваться для описания общих свойств структуры данных или могут использоваться для описания свойств реализации. Я не уверен, что это очень полезно, поскольку реализация может измениться.
Обратите внимание, что «индексированный» не подразумевает «последовательный», если только значения индекса сами по себе не являются последовательными.
Ответ №2:
При использовании индекса вы можете читать или записывать данные непосредственно в любую позицию в структуре данных. Если доступ является последовательным, вам нужно пройти через все элементы, пока не дойдете до нужного (например, повторяя next метод).
Это также означает, что время доступа является постоянным для индексированной структуры, независимо от ее размера, в то время как для последовательной структуры оно увеличивается с размером.
Это применимо, если предположить, что внутренняя реализация access для индексов (которые на самом деле являются просто операцией доступа, которая может быть реализована многими способами) основана на каком-то отображении, и что последовательная структура использует какие-то связанные списки. Это должно соответствовать духу сформулированного вопроса.
В качестве примера того, как это может отличаться в зависимости от реализации, списки в Python реализуют прямой доступ внутренне, по очевидным соображениям производительности, помимо того, что пользователь получает доступ с помощью индекса, а не с помощью методов next.
Ответ №3:
Давайте ответим на этот вопрос в более широкой области структур данных, вместо того, чтобы концентрироваться на Java или любой другой реализации как таковой.
Индексированные структуры данных
основаны на более общей концепции структур данных с произвольным / прямым доступом.
Основное преимущество использования этих структур данных заключается в том, что они имеют O (1) временную сложность как для операций чтения, так и для операций записи.
Например, когда вы определяете массив, в физической оперативной памяти выделяется непрерывная цепочка небольших фрагментов (блоков) памяти одинакового размера, и каждый из этих фрагментов имеет уникальный, но непрерывно связанный адрес памяти. Это означает, что если, например, array[0] хранится в 0100X001 , array[1] будет выделено в 0100X010 , если слот занимает 1 бит (если больше, соответственно, вам нужно будет добавить это количество битов в каждый слот);
Последовательная структура данных
с другой стороны, они четко не определены в области компьютерных наук, они, в зависимости от реализации, имеют разные временные сложности для операций чтения и записи, но в основном — это никогда не O (1) .
В большинстве случаев последовательные структуры данных реализуются таким образом, что:
- Каждый элемент, кроме первого, имеет ссылку на своего непосредственного предшественника;
- Каждый элемент, кроме последнего, имеет ссылку на его непосредственного преемника.