LinkedHashMap: примеры (JAVA)

Короткие примеры использования

Примеры ниже демонстрируют поведение вставки, доступа и переопределения removeEldestEntry.

// Пример 1: базовое поведение (порядок вставки)
import java.util.*;
public class Example1 {
  public static void main(String[] args) {
    LinkedHashMap<String,Integer> map = new LinkedHashMap<>();
    map.put("one", 1);
    map.put("two", 2);
    map.put("three", 3);
    for (String k : map.keySet()) System.out.print(k + " ");
  }
}

one two three 

// Пример 2: порядок доступа (accessOrder = true)
import java.util.*;
public class Example2 {
  public static void main(String[] args) {
    LinkedHashMap<String,Integer> map = new LinkedHashMap<>(16, 0.75f, true);
    map.put("a", 1);
    map.put("b", 2);
    map.put("c", 3);
    map.get("a"); // доступ обновит порядок
    for (String k : map.keySet()) System.out.print(k + " ");
  }
}

b c a 

// Пример 3: простая LRU-реализация через removeEldestEntry
import java.util.*;
public class LRUCache<K,V> extends LinkedHashMap<K,V> {
  private final int maxEntries;
  public LRUCache(int maxEntries) { super(16,0.75f,true); this.maxEntries = maxEntries; }
  protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return size() > maxEntries;
  }
  public static void main(String[] args) {
    LRUCache<Integer,String> cache = new LRUCache<>(2);
    cache.put(1, "one");
    cache.put(2, "two");
    cache.get(1);
    cache.put(3, "three");
    System.out.println(cache.keySet());
  }
}

[1, 3] 

// Пример 4: putIfAbsent и computeIfAbsent
import java.util.*;
public class Example4 {
  public static void main(String[] args) {
    LinkedHashMap<String,List<Integer>> map = new LinkedHashMap<>();
    map.computeIfAbsent("k", k -> new ArrayList<>()).add(1);
    map.computeIfAbsent("k", k -> new ArrayList<>()).add(2);
    System.out.println(map.get("k"));
  }
}

[1, 2] 

Альтернативы внутри Java

• HashMap - обычная хэш-таблица. Быстрее при операциях доступа, если порядок не важен. Предпочтительнее при максимальной производительности и экономии памяти.
• TreeMap - хранит элементы в отсортированном по ключам порядке (на основе Comparator или естественного порядка). Используется, когда нужен упорядоченный вывод по ключам; медленнее, чем HashMap/LinkedHashMap (log n для операций).
• ConcurrentHashMap - многопоточная карта с высокой производительностью для параллельных операций. Не гарантирует порядок обхода; подходит для конкурентных задач.
• IdentityHashMap - сравнивает ключи по ссылке (==), а не по equals. Применяется в специальных случаях, например, при реализации вспомогательных структур внутри сериализации.
• EnumMap - эффективная реализация для ключей типа enum. Быстрее и экономнее памяти, чем LinkedHashMap, при работе с перечислениями.

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

Аналоги в других языках и отличия

• JavaScript: Map сохраняет порядок вставки. Отличие: Map не имеет встроенного LRU; порядок доступа не изменяется при get. Пример:

  const m = new Map([["a",1],["b",2]]);
  m.get("a");
  console.log(Array.from(m.keys()));

  [ 'a', 'b' ]

• Python: с версии 3.7 встроенный dict сохраняет порядок вставки; collections.OrderedDict предоставляет методы move_to_end для управления порядком (может использоваться как LRU). Отличие: dict гарантирует порядок вставки, но OrderedDict удобнее для LRU.

  from collections import OrderedDict
  od = OrderedDict()
  od["a"] = 1
  od["b"] = 2
  od.move_to_end("a")
  print(list(od.keys()))

  ['b', 'a']

• PHP: ассоциативные массивы (array) сохраняют порядок вставки. Нет отдельной структуры LinkedHashMap; для LRU требуется собственная логика или расширение.

  $a = ["x" => 1, "y" => 2];
  // доступ не меняет порядок
  print_r(array_keys($a));

  Array ( [0] => x [1] => y )

• C# (.NET): есть OrderedDictionary (System.Collections.Specialized), который хранит порядок вставки. Dictionary<TKey,TValue> в новых реализациях сохраняет порядок вставки, но это не всегда гарантируется семантикой. Для LRU можно использовать LinkedList + Dictionary.

  using System.Collections.Specialized;
  var od = new OrderedDictionary();
  od.Add("a",1);
  Console.WriteLine(string.Join(", ", od.Keys.Cast<object>()));

  a

• Go: builtin map не гарантирует порядок. Для сохранения порядка используются дополнительно срез ключей или сторонние пакеты (orderedmap). Пример ручной поддержки:

  m := map[string]int{"a":1, "b":2}
  keys := []string{"a","b"}
  for _, k := range keys { fmt.Println(k) }

  a
  b

• Kotlin: есть java.util.LinkedHashMap и Kotlin-специализации. Поведение совпадает с Java-реализацией.
• Lua: таблицы не гарантируют порядок; для хранения порядка требуется список ключей.
• SQL: порядок определяется оператором ORDER BY, это не структура данных в ОЗУ, а способ выборки.

Общее отличие: во многих языках порядок вставки доступен в стандартных структурах, но поведение доступа (access-order) и встроенная поддержка LRU чаще отсутствуют и требуют дополнительной реализации.

Типичные ошибки и их примеры

• Изменение карты во время итерации без использования итератора - вызывает ConcurrentModificationException.

  import java.util.*;
  public class Err1 {
    public static void main(String[] args) {
      LinkedHashMap<String,Integer> m = new LinkedHashMap<>();
      m.put("a",1);
      m.put("b",2);
      for (String k : m.keySet()) {
        m.put("c",3); // модификация во время итерации
      }
    }
  }

  Exception in thread "main" java.util.ConcurrentModificationException
      at ...

• Ожидание изменения порядка при accessOrder=false. Чтение не изменяет порядок, поэтому неожиданные результаты при попытке реализовать LRU без параметра accessOrder.

  LinkedHashMap<String,Integer> m = new LinkedHashMap<>();
  m.put("x",1);
  m.put("y",2);
  m.get("x"); // порядок не изменится при accessOrder == false
  System.out.println(m.keySet());

  [x, y]

• Неправильное переопределение removeEldestEntry: метод должен возвращать boolean; если логика некорректна, возможна неправильная очистка.
• Использование LinkedHashMap в многопоточном окружении без синхронизации - приводит к состояниям гонок. Решения: Collections.synchronizedMap или использование ConcurrentHashMap (с потерей гарантированного порядка).

Изменения и эволюция LinkedHashMap

• Сам класс LinkedHashMap присутствует в JDK с версии 1.4; базовый контракт и поведение порядка сохранялись с момента введения.
• С появлением Java 8 были добавлены дефолтные методы в интерфейсе Map: compute, computeIfAbsent, merge, replaceAll и т. п. Эти методы доступны и в LinkedHashMap через реализацию Map и влияют на порядок при accessOrder=true, когда операции считаются доступом.
• В целевых версиях JDK оптимизировалось внутреннее представление HashMap/LinkedHashMap (результат улучшений в хеш-таблицах в Java 8 и далее), что повлияло на производительность, но не изменило видимого поведения API.

Расширенные и редкие примеры использования

Ниже - коллекция продвинутых сценариев: кэши, синхронизация, объединение с потоками и кастомная эвикция.

// 1) LRU-кэш с заданным максимальным числом элементов
import java.util.*;
public class LruExample extends LinkedHashMap<Integer,String> {
  private final int max;
  public LruExample(int max) { super(16,0.75f,true); this.max = max; }
  protected boolean removeEldestEntry(Map.Entry<Integer,String> eldest) {
    return size() > max;
  }
  public static void main(String[] args) {
    LruExample cache = new LruExample(3);
    cache.put(1,"a"); cache.put(2,"b"); cache.put(3,"c");
    cache.get(1); // 1 станет самым новым
    cache.put(4,"d"); // удалится 2
    System.out.println(cache.keySet());
  }
}

[3, 1, 4] 

// 2) Синхронизированная LinkedHashMap
import java.util.*;
public class SyncExample {
  public static void main(String[] args) {
    Map<String,Integer> map = Collections.synchronizedMap(new LinkedHashMap<>());
    map.put("a",1);
    // при итерации требуется внешний синхронизированный блок
    synchronized(map) {
      for (String k : map.keySet()) System.out.println(k);
    }
  }
}

a

// 3) Эвикция по весу: пример, где удаление зависит не от числа элементов, а от суммарного "веса"
import java.util.*;
public class WeightedCache<K,V> extends LinkedHashMap<K,V> {
  private int currentWeight = 0;
  private final int maxWeight;
  public WeightedCache(int maxWeight) { super(16,0.75f,true); this.maxWeight = maxWeight; }
  private int weightOf(Map.Entry<K,V> e) { return 1; /* здесь логика веса */ }
  protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    currentWeight -= weightOf(eldest);
    return currentWeight > maxWeight;
  }
  public V put(K k, V v) {
    V old = super.put(k,v);
    currentWeight += 1; // увеличение веса: пример
    return old;
  }
}

(нет печати; пример структурной идеи)

// 4) Поддержание порядка при сериализации/JSON: LinkedHashMap удобен для предсказуемого вывода
import com.fasterxml.jackson.databind.ObjectMapper;
import java.util.*;
public class JsonOrder {
  public static void main(String[] args) throws Exception {
    LinkedHashMap<String,Integer> map = new LinkedHashMap<>();
    map.put("first",1); map.put("second",2);
    System.out.println(new ObjectMapper().writeValueAsString(map));
  }
}

{"first":1,"second":2}

// 5) Использование computeIfAbsent для многозначной карты
import java.util.*;
public class MultiMapExample {
  public static void main(String[] args) {
    LinkedHashMap<String, List<Integer>> mm = new LinkedHashMap<>();
    mm.computeIfAbsent("k1", k -> new ArrayList<>()).add(10);
    mm.computeIfAbsent("k1", k -> new ArrayList<>()).add(20);
    System.out.println(mm);
  }
}

{k1=[10, 20]}

Эти приёмы демонстрируют сочетание детерминированного порядка и гибкости, доступной через Map API.