Список против карты / словаря

Question

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

Зачем вам когда-либо использовать Список, когда Карта предоставляет точно такую ​​же функциональность, то есть доступ по индексу (в данном случае целое число ...).

Разве карта не всегда должна быть предпочтительнее списка? Что мне здесь не хватает?

Answer 1

Дубликат этого вопроса .

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

Рассмотрим этот код:

public void add(Map map, Object o) {
    int index = map.size();
    map.put(index, o);
}

public static void add(List list, Object o) {
    list.add(o);
}

Теперь посмотрим, во что это превращает компилятор (используя javap или откройте файл класса в IDE, например, Eclipse):

public void add(java.util.Map map, java.lang.Object o);
     0  aload_1 [map]
     1  invokeinterface java.util.Map.size() : int [16] [nargs: 1]
     6  istore_3 [index]
     7  aload_1 [map]
     8  iload_3 [index]
     9  invokestatic java.lang.Integer.valueOf(int) : java.lang.Integer [22]
    12  aload_2 [o]
    13  invokeinterface java.util.Map.put(java.lang.Object, java.lang.Object) : java.lang.Object [28] [nargs: 3]
    18  pop
    19  return
      Line numbers:
        [pc: 0, line: 8]
        [pc: 7, line: 9]
        [pc: 19, line: 10]
      Local variable table:
        [pc: 0, pc: 20] local: this index: 0 type: MapListTest
        [pc: 0, pc: 20] local: map index: 1 type: java.util.Map
        [pc: 0, pc: 20] local: o index: 2 type: java.lang.Object
        [pc: 7, pc: 20] local: index index: 3 type: int

  // Method descriptor #38 (Ljava/util/List;Ljava/lang/Object;)V
  // Stack: 2, Locals: 2
  public static void add(java.util.List list, java.lang.Object o);
    0  aload_0 [list]
    1  aload_1 [o]
    2  invokeinterface java.util.List.add(java.lang.Object) : boolean [39] [nargs: 2]
    7  pop
    8  return
      Line numbers:
        [pc: 0, line: 13]
        [pc: 8, line: 14]
      Local variable table:
        [pc: 0, pc: 9] local: list index: 0 type: java.util.List
        [pc: 0, pc: 9] local: o index: 1 type: java.lang.Object

Работы по поддержанию коллекции в виде списка намного меньше, чем на карте.Таким образом, List - более эффективная структура данных для этой цели.

Answer 2

Различия между Map<Integer, E> и List<E> следующие с семантической точки зрения:

• Список содержит все индексы от 0 до list.size(), в то время как карта может содержать любыеиндексы (даже отрицательные) с большими дырами.
• При добавлении элементов в список без индекса вы автоматически получаете новый индекс.Для карт такой операции нет.(Вы можете легко реализовать это в SortedMaps.)
• При добавлении элементов с индексом или их удалении в списке последующие индексы сдвигаются на единицу.На карте такого смещения нет (и добавленные элементы могут заменить существующие).

Тем не менее, я однажды создал разреженный список (в основном содержащий null)поддержанный HashMap<Integer, E> - но там я отключил структурные модификации (аналогично Arrays.asList).

Answer 3

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

По моему мнению, если мне понадобится искать объект в структуре с использованием четко определенного ключа, я буду использовать карту.Если я, как правило, захочу перебрать коллекцию объектов, я буду использовать List.

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