Использование ArrayList или HashMap
Привет я надел вопрос, использовать ли ArrayList или HashMap.
Я пытаюсь создать Программу для рисования. Каждому рисованному объекту присвоят уникальный объект ID.
Если я хочу быструю скорость извлечения, когда я нажимаю на объект, должен я использовать arraylist или hashmap?
В общем hashmap имеет O (1), в то время как arraylist имеет O (n) скорость извлечения.
Однако я думаю для своего случая, с тех пор когда я нажму на объект, я получу идентификатор, следовательно индекс массива, и я могу сделать что-то как ArraylistObject.get(ithElement); таким образом, в этом случае это также будет O (1) процесс извлечения?
какие-либо исходные данные?
Спасибо!
3 ответа
] Если объекты имеют ID, который может быть отображен 1 к 1 в массив, то это также будет доступ к O(1), и на практике будет немного быстрее, чем поиск хэшмапа (вам не нужно вычислять хэш). [
] [] Однако проблема будет заключаться в том, что произойдет, когда вы удалите объект. У вас останется дыра в списке. При создании новых объектов вы можете продолжать добавлять их в список и оставлять, чтобы они медленно становились более фрагментированными или пытаться найти свободный слот. В этом случае вы будете искать свободное место в O(n).[
]. [] Короче говоря - хэшмап, вероятно, более уместен. [
]Если вы можете гарантировать, что идентификаторы будут в относительно небольшом числовом диапазоне, то вы должны использовать обычный массив (с размером, преинициализированным до максимального ID), а не ArrayList. Это гарантирует, что вы не будете случайно удалять записи и смещать все остальное, чтобы заполнить пробел, при этом все окажется на неправильном индексе. Обычный массив также будет немного быстрее, чем ArrayList.
Если Вы не можете дать такую гарантию, используйте HashMap. Очень маловероятно, что разница в скорости будет заметна, и ее будет проще обслуживать.
.С другой стороны, вы могли бы выжать немного больше производительности, делая ArrayLists правильно. Но удаление объектов будет королевской болью - как говорили Паоло и Анураг, вам придется либо поставить пустое место (нулевое ?), либо перенумеровать какой-нибудь другой объект, чтобы заполнить пробел. Это, скорее всего, приведет к ошибкам в производительности и обычным старым ошибкам.
HashMaps, с другой стороны. Простые в использовании, достойная производительность гарантирована (если только вы не выделяете свои идентификаторы очень плохо).
И извлечение объектов по id может оказаться совсем не узким местом вашего приложения. Как говорится, преждевременная оптимизация является корнем всего зла .