Использование ArrayList или HashMap

Question

Привет У меня вопрос о том, следует ли использовать ArrayList или HashMap.

Я пытаюсь создать программу Paint. Каждому изображенному объекту присваивается уникальный объект ID.

Если я хочу быстро получить скорость при нажатии на объект, должен ли я использовать arraylist или hashmap?

В общем случае hashmap имеет O (1), в то время как у arraylist есть скорость вывода O (n).

Однако, я думаю, что для моего случая, поскольку, когда я нажимаю на объект, я получу идентификатор, следовательно, индекс массива, и я могу сделать что-то вроде ArraylistObject.get (ithElement); , поэтому в этом случае это также будет процесс поиска O (1)?

любые входы?

Спасибо!

Answer 1

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

Однако проблема будет в том, что происходит, когда вы удаляете объект. У вас останется отверстие в списке. При создании новых объектов вы можете продолжать добавлять в список и оставлять его более медленно фрагментированным или пытаться найти запасной слот, в этом случае вы будете выполнять поиск O (n) свободного места.

Короче говоря, хэш-карта, вероятно, более уместна.

Answer 2

С другой стороны, вы можете сжать немного дополнительную производительность, выполнив ArrayLists в самый раз. Но удаление объектов будет королевской болью, как сказал Паоло и Анураг, вам придется либо положить пустой заполнитель (нуль?), Либо перенумеровать другой другой объект, чтобы заполнить пробел. Это, вероятно, приведет к ошибкам производительности и простым старым ошибкам.

HashMaps, с другой стороны. Простой в использовании, достойная производительность гарантирована (если вы не наложите свои идентификаторы действительно плохо).

И извлечение объектов по идентификатору может не оказаться узким местом вашего приложения. Как говорится, преждевременная оптимизация - корень всего зла.

Answer 3

Если вы можете гарантировать, что идентификаторы будут находиться в относительно небольшого численного диапазона, то вы должны использовать простой массив (с размером preinitialized до максимального ID), а не ArrayList. Это гарантирует, что вы случайно не удаляете записи и не переносите все остальное, чтобы заполнить пробел, причем все заканчивается неправильным индексом. Простой массив также будет немного быстрее, чем ArrayList.

Если вы не можете сделать такую ​​гарантию, используйте HashMap. Очень маловероятно, что разница в скорости будет заметна, и ее будет легче поддерживать.