Коллекции

Коллекции


В главное меню

Собственных коллекций в Koltin нет, это лишь обёртки над коллекциями Java

Итератор - интерфейс, который позволяет пройтись по какой-либо коллекции

Для собеседования

List vs ArrayList vs Linked Lis

List - интерфейс, который позволяет работать с каким-то однотипными операциями и выполнять над ними какие-либо операции (добавление, вставка, изменение значения по индексу).

Описать иерархию

Описать реализации

Рассказываем о преимуществах и недостатках выбранной коллекции и в каком случае использовали какую либо коллекцию

Пример:

ArrayList

это реализация List которая под капотом использует в себе Array. Преимущества и недостатки идут из самой структуры данных которые используются под капотом.

Преимущества: Операции доступа по индексу осуществляются очень быстро потому что массив хранится в памяти одним блоком - мы всегда точно знаем где хранится наш объект

Недостатки: если это один кусок, то для того чтобы вставить дополнительный элемент в середину массива, тон нужно все элементы подвинуть на n+1 (сдвинуть все элементы вправо), сделать копию в новый массив и в эту ячейку вставить в новый массив. Такая операция достаточно затратная.


Для большинства бытовых задач ArrayList будет достаточно, даже если будем делать расширения, то есть оптимизации такие как SystemArrayCopy - то нативный метод в JAVA (написаны на другом языке П - оптимизация работы с памятью). В общем есть методы которые позволяют достаточно быстро производить операции вставки в середину массива

LinkedList

Это реализация List - использует совершенно иной подход. Использует связанные списки.

Преимущества: Каждый элемент хранит в себе ссылку на предыдущий элемент и на следующий. Если вставляем элементы в середину, то элементы остаются на тех же местах, меняется ссылка

Недостатки:

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


Вопрос: Есть ли у LinkedList какое-то иное предназначение помимо коллекции, которая может накапливать какие-то однотипные данные?

ArrayList покрывает огромное количество задач, которые покрывают работу с данными, а LinkedList особо вроде нет применения. Если открыть исходники - он имплементит интерфейс DeQ - двунаправленная очередь. Там уже есть альтернативное применение - стек, двунаправленная очередь, выбрать класс, а реализацию поставить линкед листа.

Очередь

Двунаправленная очередь

Стэк

Вопрос: Map и их Иерархия

Это интерфейс, который позволяет работать с данными типа - ключ значение. Можем складывать данные по какому-то ключу и затем по этому ключу запрашивать id.

Рассказать про имплементации. Хотя бы 3

AbstractMap

HashMap - работает на основе механизма хеширования которая позволяет вычислять хэш на основе ключа и эти значения складывать. Внутри механизм хеширования и благодаря нему работает очень быстро.

Подробнее: использует механизм хеширования. Внутри есть массив, содержит в каждом элементе LinkedList. Если размер превышает определенный порог, то HasMap перестраивается в TreeMap для оптимизации быстрого поиска.

Дополнительно видео https://vk.com/feed?z=video-111905078_456243272

Рассказать как работает под капотом

LinkedHashMap - также стоит в итерации ниже чем HashMap. Добавляет дополнительную функцию HashMape будем содержать элементы в порядке вставки. Если будем совершать итерации по ключам, то будем их видеть в хронологическом порядке.

TreeMap - основана на механизме красно черного дерева, позволяет хранить элементы в отсортированном порядке используя например Comeparable элементы или задавая собственный Copmorator.

SortedMap


Примеры работы HashMap LinkedHashMap TreeMap

        val map = HashMap<String, Array<String>>()

        map["Cadilac"] = arrayOf("Escalade", "STS", "CT6")
        map["Chevrolet"] = arrayOf("Tahoe", "Epica", "Suburban")
        map["ВАЗ"] = arrayOf("Калина", "Приора")
        map["Nissan"] = arrayOf("Teana","Qashqai", "Patrol", "Juke")
        map["Volkswagen"] = arrayOf("Polo", "EOS", "Jetta")

        println("-----")

        map.forEach{ (k, v) ->
            println("$k: ${v.contentToString()}")
        }

        println("-----")

        println(map["ВАЗ"].contentToString())

Результат:

-----
Cadilac: [Escalade, STS, CT6]
Volkswagen: [Polo, EOS, Jetta]
ВАЗ: [Калина, Приора]
Chevrolet: [Tahoe, Epica, Suburban]
Nissan: [Teana, Qashqai, Patrol, Juke]
-----
[Калина, Приора]
//LinkedHashMap
        val map = LinkedHashMap<String, Array<String>>()

        map["Cadilac"] = arrayOf("Escalade", "STS", "CT6")
        map["Chevrolet"] = arrayOf("Tahoe", "Epica", "Suburban")
        map["ВАЗ"] = arrayOf("Калина", "Приора")
        map["Nissan"] = arrayOf("Teana","Qashqai", "Patrol", "Juke")
        map["Volkswagen"] = arrayOf("Polo", "EOS", "Jetta")

        println("-----")

        map.forEach{ (k, v) ->
            println("$k: ${v.contentToString()}")
        }

        println("-----")

        println(map["ВАЗ"].contentToString())



        val map = LinkedHashMap<String, Array<String>>()

        map["Cadilac"] = arrayOf("Escalade", "STS", "CT6")
        map["Chevrolet"] = arrayOf("Tahoe", "Epica", "Suburban")
        map["ВАЗ"] = arrayOf("Калина", "Приора")
        map["Nissan"] = arrayOf("Teana","Qashqai", "Patrol", "Juke")
        map["Volkswagen"] = arrayOf("Polo", "EOS", "Jetta")

        println("-----")

        map.forEach{ (k, v) ->
            println("$k: ${v.contentToString()}")
        }

        println("-----")

        println(map["ВАЗ"].contentToString())

Результат:

-----
Cadilac: [Escalade, STS, CT6]
Chevrolet: [Tahoe, Epica, Suburban]
ВАЗ: [Калина, Приора]
Nissan: [Teana, Qashqai, Patrol, Juke]
Volkswagen: [Polo, EOS, Jetta]
-----
[Калина, Приора]

val map = TreeMap<String, Array<String>>()

map["Cadilac"] = arrayOf("Escalade", "STS", "CT6")
map["Chevrolet"] = arrayOf("Tahoe", "Epica", "Suburban")
map["ВАЗ"] = arrayOf("Калина", "Приора")
map["Nissan"] = arrayOf("Teana","Qashqai", "Patrol", "Juke")
map["Volkswagen"] = arrayOf("Polo", "EOS", "Jetta")

println("-----")

map.forEach{ (k, v) ->
    println("$k: ${v.contentToString()}")
}

println("-----")

println(map["ВАЗ"].contentToString())

Результат:

-----
Cadilac: [Escalade, STS, CT6]
Chevrolet: [Tahoe, Epica, Suburban]
Nissan: [Teana, Qashqai, Patrol, Juke]
Volkswagen: [Polo, EOS, Jetta]
ВАЗ: [Калина, Приора]
-----
[Калина, Приора]

Что в итоге?

  1. HashMap вывел элементы в рандомном порядке
  2. TreeMap вывел элементы в отсортированном по ключу порядке
  3. LinkedHashMap в порядке в котором мы их добавляли


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


HasMap как и LinkedHashMap использует для хранения Баккеты.

У каждого из объектов в JVM есть хэш-код. Когда мы что-то добавляем в HasMap или LinkedHashMap коллекция высчитывает этот хэш код и основываясь на нем кладет его в определенную структуру данных (например в массив). Когда добавляем новый объект, высчитывается новый хэш-код для этого объекта и он кладется в другое место массива, основываясь на хэш коде. Эти элементы массива называются Баккеты. КОгда будем искать значение по ключу, то для него сначала высчитается хэш код, по нему будет найдет баккет где лежит этот объект, предварительно сравнив с ключом который лежит там.


Примеры:

  1. Инициализация массива
fun main() {
  var array = arrayOf(1, 2, 5 ,10 ,69)
  array[4] = 5
  array[3] = null //нельзя, т.к. массив в Int = не может содержать null
}

2. Инициализация массива с null

fun main() {
  var array: Array<Int?> = arrayOf(1, 2, 5 ,10 ,69)
  array[3] = null 
}

3. Заполняем массив null

fun main() {
  var array: Array<Int?> = arrayOfNulls(10)
  array[3] = null 
}



Report content on this page

Report Page

Please submit your DMCA takedown request to dmca@telegram.org