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

Question

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

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

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

В общем случае хэш-карта имеет O (1), а массив имеет O (n) скорость извлечения.

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

какие-либо входы?

Спасибо!

Answer 1

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

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

Вкратце - хеш-карта, вероятно, более уместна.

Answer 2

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

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

Answer 3

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

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

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