HashMap против производительности ArrayList Я прав

Question

В настоящее время я верю, что:

• Когда вам нужна структура, из которой вы будете извлекать предметы случайным образом - используйте HashMap
• Когда вы будете получать элементы по порядку (например, используя цикл for) - используйте ArrayList

Я в целом прав? Есть ситуации, когда это не правильно?

Answer 1

Карта - это карта или «ассоциативный массив» . Имеет раскладку key-> value. Список, с другой стороны, представляет собой список , который представляет собой упорядоченную коллекцию элементов.

Более прямое сравнение, возможно, будет между Set и List: оба эти значения хранят, где список явно упорядочен (вы можете получить элемент # x), а набор (как правило) не упорядочен (хорошо, если только это не SortedSet , в этом случае порядок итераций будет упорядочен компаратором).

Двумя наиболее распространенными реализациями для Set и List являются HashSet и ArrayList . Чтобы проверить, принадлежит ли элемент в массив (содержит (элемент)), реализация выполняет итерацию по всем его элементам, проверяя, нашел ли элемент элемент с помощью метода equals (). Чтобы проверить, принадлежит ли элемент в хэш-набор, сначала вычисляется hashCode () элемента, затем он «прямо» попадает в позицию, в которой должен находиться этот элемент, и проверяет, есть ли он там.

Таким образом, существенной разницей между ArrayList и HashSet является скорость в игре () .

В списке вы можете запросить элемент # x, в дополнение к тому, что вы можете сделать в наборе, а именно: добавить, удалить, спросить-присутствует (содержит) и выполнить итерацию по всем элементам.

На карте вы можете запросить элемент по его ключу, а не по индексу, как в случае со списком.

HashSet в настоящее время реализуется просто с помощью HashMap, где часть значения отношения ключ-> значение не используется. Это абсолютно абсурдно и не имеет никакого смысла, кроме как тратить как минимум 4 байта, что может привести к 12 для всех без исключения элементов, вставленных в HashSet.

Answer 2

В общем, да, вы правы. Существует также комбинированная структура данных, LinkedHashMap , которая обеспечивает быстрый доступ к произвольным элементам и предсказуемое упорядочение.

Однако, стоит отметить, что ArrayList и HashMap являются только двумя реализациями интерфейсов List и Map соответственно. Существуют другие реализации каждой из них, которые могут быть более подходящими для более конкретных требований. Например, LinkedList может обеспечить более высокую производительность, чем ArrayList, для определенных требований организации очередей / удаления очереди.

Answer 3

Я бы сказал, что вы в целом правы, но не совсем точны. Вы используете HashMap для извлечения данных, но не всегда случайным образом. Вы используете ArrayList для итерации, но вы также можете использовать его для поиска по индексу.

В более общем случае вы используете реализацию Map, когда вам необходимо эффективно извлекать элементы с помощью поиска, то есть извлекать что-то по ключу, например словари, кеши, репозитории и т. Д.

Вы используете реализацию List, когда вам просто нужна структура данных, где вы можете перебирать свои данные, обычно, когда вы хотите, чтобы они были в предопределенном и / или предсказуемом порядке.

Другими словами, вы используете Map s в качестве структуры данных индексации, и вы используете List s, как вы обычно используете массивы.

Answer 4

Не забывайте, что гораздо быстрее добраться до одного конкретного элемента с картой (если у вас есть ключ), чем из массива (если у вас нет индекса, но ключ всегда даст вам правильное значение тогда как наличие индекса может не сработать, если будут вставлены новые элементы или удалены более старые).

Answer 5

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

Answer 6

Я бы немного не согласился. Для меня это зависит больше от того, как я хочу получить предметы. Если я хочу сделать это на основе чего-то вроде их порядка (точнее, по индексу), я бы предпочел использовать линейную структуру, такую ​​как ArrayList (или даже массив). Если бы мне нужно было искать элементы, я бы использовал структуру карты, такую ​​как HashMap.

Другой усложняющий фактор связан со вставками и порядком, как указал дан.