Иерархия коллекций в Java часть 2.

Продолжение статьи https://telegra.ph/Ierarhiya-kollekcij-v-Java-05-08

Тут я, кратко, опишу иерархию Map:

1) Map - рутовый интерфейс для key-value таблиц/словарей/hash таблиц. Содержит объявления методов: put(K v, V v), get(K k), containsKey(K k), containsValue(V v), remove(K k) и других для работы с мапами. Также содержит статические методы для создания неизменяемых таблиц: Map.of(...). При попытке вызвать метод, который модифицирует такую таблицу вывалиться exception: UnsupportedOperationException

2) HashMap - хэш-таблица. Операции put(K k, Vv), get(K k), containsKey(K k) работают за O(1) при хорошей hashcode функции. В худшем случае get(K k) будет работать за O(log(N)), если все элементы попадают в один и тот же bucket из-за плохой hashcode() функции. Детальное устройство HashMap буду разбирать отдельно.

3) LinkedHashMap - хэш-таблица, которая позволяет итерироваться по элементам в порядке добавления. Это достигается путем того, что элементы помещаются еще и в связный список. Есть опция другого порядка элементов - accessOrder (в порядке доступа, а не в порядке добавления).

4) TreeMap - красно-чёрное дерево. Операции put(K v, V v), get(K k), containsKey(K k), remove(K k) работают за O(log(n)). Элементы хранятся в упорядоченном виде. При итерировании элементы будут упорядоченными. В силу того, что это дерево, TreeMap имеет множество методов для работы с деревом: TreeMap.