HashMap

Особенности HashMap:

  1. Пары ключ-значение: HashMap представляет собой коллекцию, в которой каждый элемент представлен в виде пары "ключ-значение".
  2. Быстрый доступ к элементам по ключу: Время доступа к элементу в HashMap практически постоянное (O(1)), что делает его очень эффективным для операций поиска и доступа.
  3. Уникальные ключи: Каждый ключ в HashMap должен быть уникальным. Если ключ уже существует в HashMap, его значение перезаписывается новым значением.
  4. Нет гарантии порядка элементов: Порядок элементов в HashMap не гарантирован и может изменяться в зависимости от реализации и операций над ним.

Когда лучше использовать HashMap в Android:

  1. Когда требуется быстрый доступ к данным по ключу: Если вам нужно быстро получать доступ к данным по их уникальному идентификатору (ключу), то HashMap будет хорошим выбором.
  2. Когда нужно хранить данные в виде пар "ключ-значение": Когда вам нужно хранить данные в виде связей между уникальными ключами и соответствующими значениями, HashMap обеспечивает удобную структуру для этого.

Как работает под капотом:

HashMap использует хеш-таблицу для хранения данных. Когда вы добавляете элемент в HashMap, он вычисляет хеш-код ключа и использует его для определения индекса внутреннего массива, где будет храниться значение. Если несколько ключей имеют один и тот же хеш-код, они хранятся в связанном списке (или в более эффективной структуре данных в более новых версиях Java) для разрешения коллизий.

Сходство и отличие от других видов коллекций:

  • Подобие с другими коллекциями: Как и другие коллекции в Java, HashMap предоставляет методы для добавления, удаления и получения элементов. Он также реализует интерфейс Map, что позволяет использовать его в качестве словаря или ассоциативного массива.
  • Отличие от других коллекций: Основное отличие HashMap от других коллекций заключается в его структуре данных, а именно в использовании хеш-таблицы для хранения данных в виде пар "ключ-значение". Это делает его эффективным для операций поиска и доступа по ключу, но может не подходить для сценариев, где требуется сохранение порядка элементов или где элементы не уникальны.

Вычисление ключа и возможные коллизии

Ключ

При добавлении элемента в HashMap, используется метод hashCode() ключа, чтобы вычислить его хеш-код. Хеш-код — это целочисленное значение, которое служит индексом внутреннего массива HashMap. Затем происходит определение индекса в массиве путем взятия остатка от деления хеш-кода на размер массива.

val map = HashMap<String, Int>()
map["apple"] = 5
map["banana"] = 10
map["orange"] = 7

Коллизии

Коллизия возникает, когда два или более ключа имеют одинаковый хеш-код. В HashMap коллизии обрабатываются с помощью цепочек. Если два ключа имеют одинаковый хеш-код, они помещаются в один и тот же индекс массива, и их значения хранятся в связанном списке (LinkedList) или другой структуре данных.

Когда происходит поиск элемента по ключу, HashMap сначала вычисляет хеш-код ключа и определяет индекс массива. Затем он просматривает связанный список (или другую структуру данных) в этом индексе, чтобы найти элемент с нужным ключом.

val map = HashMap<String, Int>()
map["apple"] = 5
map["apricot"] = 7 // Коллизия с "apple"
map["banana"] = 10
map["orange"] = 7 // Коллизия с "apricot"

println(map["apple"]) // Выведет: 5
println(map["apricot"]) // Выведет: 7
println(map["orange"]) // Выведет: 7