Информатику действительно следует называть искусством компромисса. Для любой задачи всегда есть множество решений, и каждое из них может быть «правильным» в зависимости от данного контекста. Этот контекст поможет определить, какие компромиссы предпочтительнее, а от каких лучше держаться подальше.

Хранение пар ключ / значение - это обычная задача программирования, а это, конечно же, требует компромиссов. Ваш инстинкт может побудить вас выбрать ту структуру данных, которая обеспечивает наилучшую производительность с точки зрения временной сложности, но это всего лишь одна часть уравнения. Вам нужно, чтобы ваши данные были отсортированы? Будет ли коллекция постоянно увеличиваться и уменьшаться? А как насчет уникальных значений или повторяющихся ключей? Насколько это возможно, постарайтесь наметить, как вы собираетесь взаимодействовать с данными, которые вы будете хранить, и выберите структуру данных, которая наилучшим образом соответствует вашим потребностям.

Чтобы проиллюстрировать эти различия, давайте рассмотрим три тесно связанных структуры Java для хранения пар ключ / значение: HashMap, Linked HashMap и TreeMap.

Состав

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

TreeMaps в Java также сортируются автоматически. По умолчанию он будет сортировать себя на основе естественного порядка ключей, но у вас также есть возможность использовать собственный компаратор при первом создании TreeMap.

HashMap, с другой стороны, хранит пары ключ / значение в хеш-таблице, и элементы никак не упорядочиваются. Так что сразу же, если порядок важен для вас, выбирайте TreeMap вместо HashMap. Однако HashMap обычно предлагает постоянную производительность для основных операций, тогда как TreeMaps может гарантировать только логарифмическую производительность для таких операций.

Третья структура, Linked HashMap, добавляет двусвязный список к структуре HashMap. Это означает, что мы получаем преимущества производительности HashMap, а также некоторый порядок (в том порядке, в котором были вставлены элементы).

Представление

HashMap имеет преимущества с точки зрения производительности, поскольку он предлагает производительность в постоянном времени (O (1)) для таких операций, как get и put, но под капотом все сложнее, и вам нужно учитывать, как структура может разрастаться. время.

На производительность HashMap могут влиять два фактора: нагрузка и емкость. Емкость относится к количеству «корзин», созданных функцией хеширования HashMap, а под нагрузкой понимается заполненность каждой из этих корзин. По мере роста количества элементов в структуре, в конечном итоге, необходимо будет изменить хеширование для создания большего количества сегментов, что может оказаться дорогостоящей операцией в зависимости от количества записей.

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

  • Вам нужна эта приятная производительность в постоянном времени (при условии правильной функции хеширования)
  • Вы представляете, насколько большой будет коллекция
  • Вы не будете регулярно добавлять или удалять тонны элементов.

С другой стороны, TreeMap может гарантировать только логарифмическую стоимость времени (0 (log (n)) для таких методов, как contains, get или put. Это связано с тем, что производительность красно-черного дерева напрямую зависит от высоты дерева.

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

Выводы

Итак, какой из них вы должны использовать? Это зависит! Как и любое другое решение в программировании, выбор заключается в тщательном рассмотрении плюсов и минусов.

Используйте TreeMap, если вы не знаете, сколько элементов у вас будет в вашей коллекции (и это может быть большая коллекция), и вы можете выжить с более медленной логарифмической (n) временной сложностью. Используйте HashMap, если вам нужна действительно быстрая постоянная сложность и вы знаете, что общий размер коллекции не будет сильно меняться (и не будет слишком большим). Используйте Linked HashMap, если HashMap работает с вашими ограничениями, и вы хотите получить дополнительный бонус от сортировки. Удачного картирования!