Использование HashMap с целыми числами (индексами) в качестве ключей против использования ArrayList

#java #arraylist #data-structures #hashmap #indices

#java #arraylist #структуры данных #hashmap #индексы

Вопрос:

Итак, в настоящее время я создаю свою собственную версию Pokemon, реплицируемую на Java. Я совсем недавно познакомился с более продвинутыми структурами данных и все еще не уверен, когда одна из них должна быть более подходящей, чем другая.

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

Мой вопрос в том, имеет ли смысл использовать HashMap, когда ключи являются просто значениями индекса, или было бы разумнее хранить Pokedex в виде ArrayList (или даже массива), где каждый покемон хранится по соответствующему индексу?

Очевидно, что если я еще не создал определения для каждого Pokemon, то ArrayList будет неэффективно использовать память, поскольку нам придется резервировать место для каждого pokemon, но, насколько я понимаю, ключи в hashmaps должны использоваться для создания хэш-значений, а не быть прямыми индексами, верно? Или это было бы уместно независимо?

1. это был бы просто их соответствующий индекс — если это может измениться в будущем, используйте HashMap , иначе используйте ArrayList .

2. Если ключи всегда будут равны 0, 1, 2… используйте список. Однако, если ключи нерегулярны, используйте hashmap. Честно говоря, в большинстве случаев вы могли бы просто использовать hashmap и не столкнуться с какими-либо проблемами. Поиск выполняется довольно быстро, если у вас нет большого количества столкновений ключей.

Ответ №1:

Это действительно зависит. Карта дает вам более высокую степень свободы, тогда как списки / массивы могут привести вас к последствиям использования таких линейных / последовательных структур данных.

Тогда это зависит от того, насколько «разреженным» будет заполнен ваш массив. Если «ключи» выполняются от 0 до 1000, с небольшим количеством неиспользуемых слотов или вообще без них, список подойдет. Если ключей от 0 до 10 миллионов, а большинство слотов пусты: используйте карту. Или структуры данных, оптимизированной для разреженных матриц.

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

Ответ №2:

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