Использование класса LinkedHashMap

Содержание

1 Введение
2 Сортировка хэш-таблицы
3 Копирование таблицы
4 Сохранение порядка доступа к элементам
5 Ссылки

Введение

Предположим, что вы пишете Java-приложение, использующее словарь слов, например, при подсчете частоты имеющихся в тексте слов. В самом начале программы производится вставка слов в хэш-таблицу. Затем, при обнаружении каждого слова, приложение находит слово в таблице и увеличивает его частоту на единицу.

Вот код, использующий этот подход:

import javax.net.ssl.*;
import javax.net.*;
import java.io.*;
import java.net.*;

public class EchoServer {
  private static final int PORT_NUM = 6789;

  public static void main(String args[]) {
    ServerSocketFactory serverSocketFactory = SSLServerSocketFactory
        .getDefault();
    ServerSocket serverSocket = null;
    try {
      serverSocket = serverSocketFactory.createServerSocket(PORT_NUM);
    } catch (IOException ignored) {
      System.err.println("Unable to create server");
      System.exit(-1);
    }
    while (true) {
      Socket socket = null;
      try {
        socket = serverSocket.accept();
        InputStream is = socket.getInputStream();
        BufferedReader br = new BufferedReader(new InputStreamReader(
            is, "US-ASCII"));
        OutputStream os = socket.getOutputStream();
        Writer writer = new OutputStreamWriter(os, "US-ASCII");
        PrintWriter out = new PrintWriter(writer, true);
        String line = null;
        while ((line = br.readLine()) != null) {
          out.println(line);
        }
      } catch (IOException exception) {
        exception.printStackTrace();
      } finally {
        if (socket != null) {
          try {
            socket.close();
          } catch (IOException ignored) {
          }
        }
      }
    }
  }
}

После выполнения этой программы вы получите следующий результат: 

computer 1
able 1
baker 2

То есть, "computer" использовался один раз, а "baker" два.

Эти результаты верны, но существует потенциальная проблема: слова отображаются не в том порядке, в котором первоначально были вставлены в хэш-таблицу. Эта проблема связана с внутренней работой хэш-таблиц. Сортировка в такой таблице случайна.

Сортировка хэш-таблицы

Вы можете не беспокоиться о смешанной сортировке, поскольку выполнение главной функции хэш-таблицы не зависит от порядка пар ключ/значение. Но если для вас это важно, существует ли решение? Одним из ответов на этот вопрос является использование LinkedHashMap вместо HashMap. Вы можете сделать это, поменяв одну строку в приведенной выше программе, а именно строку, в которой создается объект HashMap в начале определения класса MapDemo1. Другими словами, закомментируйте строку:

static Map map = new HashMap();

Затем раскомментируйте строку:

static Map map = new LinkedHashMap();

LinkedHashMap аналогичен HashMap, за исключением того, что он налагает структуру связного списка на верхнюю часть хэш-таблицы. Этот список хранит порядок вставки элементов таблицы. Затем он используется для итерации по таблице.

После изменения одной строки в MapDemo1, результат работы программы будет следующим: 

able 1
baker 2
computer 1

Элементы сейчас отображаются в алфавитном порядке, поскольку именно в этом порядке они были вставлены в хэш-таблицу. LinkedHashMap не сортирует свои элементы. Он просто сохраняет порядок их вставки.

Копирование таблицы

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

import java.util.*;

public class MapDemo2 {

  // скопировать таблицу
  static Map copyMap(Map map) {
    return new HashMap(map);
    //return new LinkedHashMap(map);
  }

  public static void main(String args[]) {

    // создать TreeMap и
    // добавить несколько пар ключ/значение

    Map map_tree = new TreeMap();
    map_tree.put("able", "value1");
    map_tree.put("baker", "value2");
    map_tree.put("computer", "value3");

    // скопировать таблицу

    Map map_copy = copyMap(map_tree);

    // отобразить содержимое таблицы

    Iterator iter = map_copy.keySet().iterator();
    while (iter.hasNext()) {
      System.out.println(iter.next());
    }
  }
}

Этот пример опять использует словарь. В этой программе слова словаря добавляются в TreeMap - класс, гарантирующий, что его элементы будут отсортированы в порядке возрастания ключа.

Предположим, что вы хотите скопировать TreeMap, и сохранить порядок сортировки. Но вы не нуждаетесь в полной структуре TreeMap, реализованной в J2SE(tm) v 1.4 с использованием "красно-черных деревьев". (Если вы не знакомы с красно-черными деревьями, обратитесь к книге "Введение в алгоритмы" Cormen, Leiserson и Rivest.) Как сделать такую копию?

Первый подход в MapDemo2 использует HashMap, то есть:

static Map copyMap(Map map) {
   return new HashMap(map);          
}
Вот результат: 
computer
able
baker

Проблема здесь аналогична продемонстрированной ранее - хэш-таблица хранит свои элементы в произвольном порядке. Элементы в TreeMap отсортированы, но после копирования их в HashMap порядок нарушается.

Если программу MapDemo2 изменить на использование LinkedHashMap, например:

static Map copyMap(Map map) {
  return new LinkedHashMap(map);          
}

то результат будет следующим: 

able
baker
computer

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

Сохранение порядка доступа к элементам

Существует еще один способ использования LinkedHashMap. Если вы создадите таблицу с помощью значения "true", переданного в качестве третьего аргумента в конструктор, например:

Map map = new LinkedHashMap(16, 0.75f, true);

то будет сохраняться не порядок вставки, а порядок доступа к элементам. Каждый вызов get или put представляет собой доступ к элементу. Порядок итерации - от самого старого к самому новому. Рассмотрим пример:

import java.util.*;

public class MapDemo3 {
  public static void main(String args[]) {

    // создать map и
    // добавить несколько пар ключ/значение

    Map map = new LinkedHashMap(16, 0.75f, true);
    map.put("able", "value1");
    map.put("baker", "value2");
    map.put("computer", "value3");

    // отобразить содержимое таблицы

    Iterator iter1 = map.keySet().iterator();
    while (iter1.hasNext()) {
      System.out.println(iter1.next());
    }

    // использовать элементы таблицы

    map.get("baker");
    map.get("able");
    map.get("computer");

    // опять отобразить содержимое таблицы

    System.out.println();
    Iterator iter2 = map.keySet().iterator();
    while (iter2.hasNext()) {
      System.out.println(iter2.next());
    }
  }
}

После выполнения этой программы вы получите следующий результат: 

able
baker
computer

baker
able
computer

Первая часть результата отображает последовательность вызовов put. Вызов put для "able" старше, чем вызов put для "computer". Затем выполняются вызовы get. Первый вызов get делается для "baker", затем для "able" и "computer".

Извлечение элементов таблицы в порядке доступа к ним очень полезен в некоторых приложениях, например, если вы работаете с кэшем и хотите освободить старые элементы. Если вы поместите элементы кэша в LinkedHashMap, каждое обращение к элементу автоматически будет обновлять порядок. То есть, в любое время вы можете определить, какие элементы являются самыми старыми и при желании удалить их. Такая схема работы часто называется кешем LRU или "least recently used" (кэш с замещением элементов с наиболее давним использованием).

Ссылки

Дополнительная информация о LinkedHashMap находится в описании класса.

Теги: HashMap LinkedHashMap