8.7 Новый набор коллекций

List x = new LinkedList();

List x = new ArrayList();  

//: SimpleCollection.java
// Пример использования новых коллекций
package c08.newcollections;
import java.util.*;

public class SimpleCollection {
  public static void main(String[] args) {
    Collection c = new ArrayList();
    for(int i = 0; i < 10; i++)
      c.add(Integer.toString(i));
    Iterator it = c.iterator();
    while(it.hasNext())
      System.out.println(it.next());
  }
} ///:~

java c08.newcollections.SimpleCollection

**boolean add(Object)**

Добавляет аргумент в коллекцию. Возвращает `false`, если аргумент не был добавлен.

**boolean addAll(Collection)**

Добавляет все элементы из переданной коллекции. Возвращает `true`, если были добавлены какие-либо элементы.

**void clear()**

Удаляет все элементы из коллекции.

**boolean contains(Object)**

Возвращает `true`, если коллекция содержит указанный аргумент.

**boolean containsAll(Collection)**

Возвращает `true`, если коллекция содержит все элементы из переданной коллекции.

**boolean isEmpty()**

Возвращает `true`, если коллекция пустая.

**Iterator iterator()**

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

**boolean remove(Object)**

Если аргумент содержится в коллекции, удаляет один экземпляр этого элемента. Возвращает `true`, если удаление произошло.

**boolean removeAll(Collection)**

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

**boolean retainAll(Collection)**

Оставляет только те элементы, которые содержатся в переданной коллекции (пересечение из теории множеств). Возвращает `true`, если были сделаны изменения.
```**int size()**

Возвращает количество элементов в коллекции.

**Object[] toArray()**

Возвращает массив, содержащий все элементы коллекции.

**Object[] toArray(Object[] a)**

Возвращает массив, содержащий все элементы коллекции, типа которого совпадает с типом массива `a` (необходимо привести массив к правильному типу).

```*Это "опциональный" метод, то есть он может отсутствовать в реализации конкретной коллекции. Если так, данный метод выбрасывает исключение `UnsupportedOperationException`. Исключения будут рассмотрены в главе 9.*``````java
//: Collection1.java
// Все, что можно сделать со всеми коллекциями
package c08.newcollections;
import java.util.*;

public class Collection1 {
    // Заполнение коллекцией 'size' элементами, начиная с 'start':
    public static Collection заполнить(Collection c, int start, int size) {
        for(int i = start; i < start + size; i++)
            c.add(Integer.toString(i));
        return c;
    }

    // По умолчанию начинается с 'start' равным OnClickListener:
    public static Collection заполнить(Collection c, int size) {
        return заполнить(c, 0, size);
    }

    // По умолчанию заполняется 10 элементами:
    public static Collection заполнить(Collection c) {
        return заполнить(c, 0, 10);
    }

    // Создание и преобразование в Collection:
    public static Collection новаяКоллекция() {
        return заполнить(new ArrayList());
        // ArrayList используется для простоты, но он видится как общая Collection
        // во всех остальных местах программы.
    }

    // Создание Collection с диапазоном значений:
    public static Collection новаяКоллекция(int start, int size) {
        return заполнить(new ArrayList(), start, size);
    }

    // Вывод содержимого Collection:
    public static void вывод(Collection c) {
        for(Iterator x = c.iterator(); x.hasNext(); ) {
            System.out.print(x.next() + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Collection c = новаяКоллекция();
        c.```java
добавить("десять");
c. добавить("одиннадцать");
вывод(c);
// Создание массива из списка:
Объект[] массив = c.кАмассиву();
// Создание массива строк из списка:
Строки[] строки = 
    (Строки[])c.кАмассиву(новый Строки[1]);
// Нахождение максимального и минимального элементов; это значит
// разные вещи в зависимости от реализации интерфейса Comparable:
System.out.println("Collections.макс(c) = " +
    Collections.макс(c));
System.out.println("Collections.мин(c) = " +
    Collections.мин(c));
// Добавление одной коллекции в другую:
c.добавитьВсе(новаяКоллекция());
вывод(c);
c.удалить("3"); // Удаление первого элемента
вывод(c);
c.удалить("3"); // Удаление второго элемента
вывод(c);
// Удаление всех компонентов, которые есть в аргументной коллекции:
c.удалитьВсе(новаяКоллекция());
вывод(c);
c.добавитьВсе(новаяКоллекция());
вывод(c);
// Есть ли элемент в этой коллекции?
System.out.println(
    "c.содержит(\"4\") = " + c.содержит("4"));
// Есть ли коллекция в этой коллекции?
System.out.println(
    "c.содержитВсе(новаяКоллекция()) = " +
    c.содержитВсе(новаяКоллекция()));
Коллекция c2 = новаяКоллекция(5,  Yöntem);

// Сохраните все элементы, которые присутствуют в обоих
// c и c2 (пересечение множеств):
c.,retainAll(c2);
print(c);
// Удалите все элементы из c, которые также присутствуют в c2:
c. ,removeAll(c2);
System.out.println("c.");
``````java
isEmpty() = " + c.isEmpty());
      c = newCollection();
      print(c);
      c.clear(); // Удаление всех элементов
      System.out.println("после c.clear():");
      print(c);
    }
  } ///:~

List (интерфейс)
```Порядок является наиболее важной характеристикой списка; он гарантирует сохранение элементов в определённом порядке. Интерфейс `List` добавляет множество методов к интерфейсу `Collection`, позволяющих вставлять и удалять элементы посередине списка. (Это рекомендовано только для `LinkedList`). Список создаёт `ListIterator`, и с его помощью можно пройти по всему списку в обоих направлениях, а также вставлять и удалять элементы посередине списка (ещё раз, это рекомендовано только для `LinkedList`).```markdown
### ArrayList*

**Описание:** Список, основанный на массиве. Используйте вместо `Vector` как универсальный контейнер для объектов. Он позволяет быстрый случайный доступ к элементам, но медленен при вставлении и удалении элементов посередине списка. `ListIterator` следует использовать только для перемещения по `ArrayList` вперед и назад, но не для вставки и удаления элементов, так как это дороже, чем использование `LinkedList`.

### LinkedList

**Описание:** Обеспечивает оптимальный последовательный доступ, с недорогими операциями вставки и удаления посередине списка. Недостаточно быстро для случайного доступа. (Используйте `ArrayList` вместо этого). Также имеет методы `addFirst()`, `addLast()`, `getFirst()`, `getLast()`, `removeFirst()` и `removeLast()` (которые не определены ни в одном интерфейсе или базовом классе), чтобы позволить использовать его как стек, очередь и двустороннюю очередь.

---

#### Интерфейс List

**Порядок** — это самое важное свойство `Списка`. Он гарантирует, что элементы будут расположены в соответствии с указанным порядком. `Список` добавляет множество методов к `Коллекции`, чтобы мы могли вставлять и удалять элементы посередине `Списка` (рекомендовано только для `LinkedList`). `Список` также генерирует `ИтераторСписка` (итератор списка), который позволяет нам перемещаться в обоих направлениях внутри списка и вставлять/удалять элементы посередине (также рекомендовано только для `LinkedList`).
```+ `ArrayList` — список, полученный путём расширения массива. Используется как универсальный контейнер объектов, заменяющий `Vector`. Он позволяет быстрый доступ к элементам, но медленнее при вставке и удалении элементов посередине списка. Общепринято использовать `Iterator` для прямого и обратного прохода по `ArrayList`, но не для вставки и удаления элементов; его эффективность значительно ниже по сравнению с `LinkedList`.

+ `LinkedList` обеспечивает оптимальное выполнение последовательного доступа, а также высокую производительность при вставке и удалении элементов посередине списка. Однако случайный доступ осуществляется гораздо медленнее, поэтому следует использовать `ArrayList`. Также предоставляются методы `addFirst()`, `addLast()`, `getFirst()`, `getLast()`, `removeFirst()` и `removeLast()` (не определённые ни в одном интерфейсе или базовом классе), чтобы использовать его как очередь, односвязный список и двусвязный список.```java
//: List1.java
// Взаимодействие со списками
package c08.newcollections;
import java.util.*;

public class List1 {
    // Обертка Collection1.fill() для удобства:
    public static List fill(List a) {
        return (List)Collection1.fill(a);
    }
    
    // Можно использовать итератор, как с коллекцией,
    // но также можно использовать случайный доступ с помощью get():
    public static void print(List a) {
        for (int i = 0; i < a.size(); i++)
            System.out.print(a.get(i) + " ");
        System.out.println();
    }

    static boolean b;
    static Object o;
    static int i;
    static Iterator it;
    static ListIterator lit;

    public static void basicTest(List a) {
        a.add(1, "x"); // Добавление в позицию 1
        a.add("x"); // Добавление в конец
        // Добавление коллекции:
        a.addAll(fill(new ArrayList()));
        // Добавление коллекции начиная с позиции 3:
        a.addAll(3, fill(new ArrayList()));
        b = a.contains("1"); // Есть ли это внутри?
        // Входит ли вся коллекция внутрь?
        b = a.containsAll(fill(new ArrayList()));
        // Списки позволяют случайный доступ, что дешевле для ArrayList,
        // дороже для LinkedList:
        o = a.get(1); // Получение объекта в позиции 1
        i = a.indexOf(o); // Индекс объекта o
        it = a.iterator(); // Получение итератора
        lit = a.listIterator(); // Получение списка итератора
    }
}
``````markdown
indexOf("1"); // Индекс объекта
// `indexOf`, начиная поиск с позиции 2:
i = a.indexOf("1", 2);
b = a.isEmpty(); // Есть ли какие-либо элементы внутри?
it = a.iterator(); // Обычный итератор
lit = a.listIterator(); // Списковый итератор
lit = a.listIterator(3); // Начало с позиции 3
i = a.lastIndexOf("1"); // Последнее совпадение
i = a.lastIndexOf("1", 2); // ... после позиции 2
a.remove(1); // Удаление позиции 1
a.remove("3"); // Удаление этого объекта
a.set(1, "y"); // Установка позиции 1 на "y"
// Оставить все, что есть в аргументе
// (пересечение двух множеств):
a.retainAll(fill(new ArrayList()));
// Удалить элементы в этом диапазоне:
a.removeRange(0, 2);
// Удалить всё, что есть в аргументе:
a.removeAll(fill(new ArrayList()));
i = a.size(); // Какова его размерность?
a.clear(); // Удаление всех элементов
}
public static void iterMotion(List a) {
	ListIterator it = a.listIterator();
	b = it.hasNext();
	b = it.hasPrevious();
	o = it.next();
	i = it.nextIndex();
	o = it.previous();
	i = it.previousIndex();
}
public static void iterManipulation(List a) {
	ListIterator it = a.listIterator();
	it.add("47");
	// Необходимо переместиться к элементу после добавления():
	it.next();
	// Удаление элемента, который был только создан:
	it.remove();
}

     // Обрабатывать как очередь, удаляя элементы
      // с конца:
      System.out.println(ll.removeLast());
      // С этими операциями это дек!
      print(ll);
    }
    public static void main(String[] args) {
      // Создаем и заполняем новый список каждый раз:
      basicTest(fill(new LinkedList()));
      basicTest(fill(new ArrayList()));
      iterMotion(fill(new LinkedList()));
      iterMotion(fill(new ArrayList()));
      iterManipulation(fill(new LinkedList()));
      iterManipulation(fill(new ArrayList()));
      testVisual(fill(new LinkedList()));
      testLinkedList();
    }
  } ///:~

### Set (интерфейс)
Каждый элемент, который вы добавляете в `Set`, должен быть уникальным; в противном случае `Set` не добавит повторяющийся элемент. Объекты, добавляемые в `Set`, должны определять метод `equals()`, чтобы установить уникальность объекта. Интерфейс `Set` полностью совпадает с интерфейсом `Collection`. Интерфейс `Set` не гарантирует, что его элементы будут сохранены в каком-либо конкретном порядке.

#### HashSet
Для `Set`, где важна скорость поиска. Объекты также должны определять метод `hashCode()`.

#### TreeSet
Упорядоченный `Set`, поддерживающий красно-черное дерево. Таким образом, можно извлечь упорядоченную последовательность из `Set`.

//: Set1.java
// Действия, которые можно выполнить с использованием Set
package c08.newcollections;
import java.util.*;

public class Set1 {
  public static void testVisual(Set a) {
    Collection1.fill(a);
    Collection1.fill(a);
    Collection1.fill(a);
    Collection1.print(a); // Отсутствие повторяющихся значений!
    // Добавление другого набора в этот:
    a.addAll(a);
    a.add("one");
    a.add("one");
    a.add("one");
    Collection1.print(a);
    // Поиск значения:
    System.out.println("a.contains(\"one\"): " +
      a.contains("one"));
  }
  public static void main(String[] args) {
    testVisual(new HashSet());
    testVisual(new TreeSet());
  }
} ///:~

public class Set2 {
  public static Set fill(Set a, int size) {
    for(int i = 0; i < size; i++)
      a.add(new MyType(i));
    return a;
  }
  
  public static Set fill(Set a) {
    return fill(a, 10);
  }

  public static void test(Set a) {
    fill(a);
    fill(a); // try to add duplicate values
    fill(a);
    a.addAll(fill(new TreeSet()));
    System.out.println(a);
  }

  public static void main(String[] args) {
    test(new HashSet());
    test(new TreeSet());
  }
}
///:~

Примечание: Исходный текст был Java кодом, поэтому он представлен как текстовый блок с использованием обратных тильдов (`~`).

Определение методов `equals()` и `hashCode()` в соответствии с примером "groundhog" уже дано. В обоих случаях необходимо определить метод `equals()`. Однако метод `hashCode()` требуется только тогда, когда класс используется как ключ в контейнере типа `HashSet` — это вполне возможно, так как обычно следует выбирать реализацию `Set`.
```## 8.7.4 Использование `Maps`

```
Map (интерфейс)

Поддерживает ассоциации «ключ-значение» (пары), позволяя находить значение по ключу.

HashMap*

Реализация на основе хэш-таблицы. (Используйте этот класс вместо `Hashtable`). Обеспечивает постоянное время выполнения для вставки и поиска пар. Вы можете настроить производительность через конструкторы, которые позволяют установить емкость и коэффициент заполнения хэш-таблицы.

TreeMap

Реализация на основе красно-черного бинарного дерева. При просмотре ключей или пар они будут отсортированы (в зависимости от `Comparable` или `Comparator`, который будет рассмотрен позже). Главное преимущество `TreeMap` заключается в том, что он обеспечивает отсортированные результаты. `TreeMap` является единственным типом `Map`, содержащим метод `subMap()`, который позволяет вернуть часть дерева.
```+ `Map` (интерфейс) Поддерживает ассоциации «ключ-значение», позволяя находить значение по ключу.
+ `HashMap`* Реализация на основе хэш-таблицы. (Используйте этот класс вместо `Hashtable`). Обеспечивает постоянное время выполнения для вставки и поиска пар. Вы можете настроить производительность через конструкторы, которые позволяют установить емкость и коэффициент заполнения хэш-таблицы.
+ `ArrayMap` Полученный из `ArrayList` `Map`. Предоставляет точный контроль над порядком итерации. Направлен на использование очень маленьких `Map`, особенно тех, которые часто создаются и удаляются. Для очень маленьких `Map` затраты на создание и итерацию значительно ниже, чем для `HashMap`. Но при увеличении размера `Map` производительность значительно снижается.
+ `TreeMap` Реализация на основе красно-черного бинарного дерева. При просмотре ключей или пар они будут отсортированы (в зависимости от `Comparable` или `Comparator`, который будет рассмотрен позже). Главное преимущество `TreeMap` заключается в том, что он обеспечивает отсортированные результаты. `TreeMap` является единственным типом `Map`, содержащим метод `subMap()`, который позволяет вернуть часть дерева.```markdown
//: Map1.java
// Действия, которые можно выполнять с помощью карт
пакет c08.newcollections;
import java.util.*;

публичный класс Map1 {
  публичный константный статический строковый[][] testData1 = {
    { "Счастливый", "Часто весёлый" },
    { "Засонха", "Любит темноту и тишину" },
    { "Грубиян", "Нуждается в корректировке поведения" },
    { "Док", "Мечтает о высшем образовании" },
    { "Ленивый", "Прилагает усилия" },
    { "Кашляющий", "Страдает аллергией" },
    { "Робкий", "Нуждается в тренировках по самооценке" },
  };
  публичный константный статический строковый[][] testData2 = {
    { "Буйный", "Дестабилизирующее влияние" },
    { "Лентяй", "Проблемы с мотивацией" },
    { "Бессознательный", "Отличное поведение" }
  };
  публичный статический метод Map fill(словарь m, объект[][] o) {
    для(инт i = 0; i < o.length; i++)
      m.put(o[i][0], o[i][1]);
    вернуть m;
  }
  // Производство набора ключей:
  публичный статический метод void printKeys(словарь m) {
    вывод.print("Размер = " + m.size() + ", ");
    вывод.print("Ключи: ");
    Collection1.print(m.keySet());
  }
  // Производство коллекции значений:
  публичный статический метод void printValues(словарь m) {
    вывод.print("Значения: ");
    Collection1.print(m.values());
  }
  // Обход через объекты Map.Entry (пары):
}
``````java
public static void print(словарь m) {
    коллекция entries = m.entries();
    итератор it = entries.iterator();
    пока(it.hasNext()) {
        Map.Entry e = (Map.Entry)it.next();
        вывод.println("Ключ = " + e.getKey() +
            ", Значение = " + e.getValue());
    }
}
public static void test(словарь m) {
    fill(m, testData1);
    // Словарь имеет поведение 'Set' для ключей:
    fill(m, testData1);
    printKeys(m);
    printValues(m);
    print(m);
    строковый ключ = testData1[4][0];
    строковый значение = testData1[4][1];
    вывод.println("m.containsKey(\"" + ключ +
        "\"): " + m.containsKey(ключ));
    вывод.println("m.get(\"" + ключ + "\"): "
        + m.get(ключ));
    вывод.println("m.containsValue(\""
        + значение + "\"): " +
        m.containsValue(значение));
    словарь m2 = fill(new TreeMap(), testData2);
    m.putAll(m2);
    printKeys(m);
    m.remove(testData2[0][0]);
    printKeys(m);
    m.clear();
    вывод.println("m.isEmpty(): "
        + m.isEmpty());
    fill(m, testData1);
    // Операции над Set меняют словарь:
    m.keySet().removeAll(m.keySet());
    вывод.println("m.isEmpty(): "
        + m.isEmpty());
}
public static void main(строка[] args) {
    вывод.println("Тестирование HashMap");
    test(new HashMap());
    вывод.println("Тестирование TreeMap");
    test(new TreeMap());
}
```
```Методы `printKeys()`, `printValues()` и `print()` являются не только полезными инструментами, но также четко демонстрируют процесс генерации "картинки" коллекций в контексте `Map`. Метод `keySet()` создает `Set`, который состоит из ключей, получаемых из `Map`. В данном случае он рассматривается как простая коллекция. Метод `values()` аналогичен, он создает список, содержащий все значения из `Map` (учтите, что ключи должны быть уникальными, а значения могут повторяться). Поскольку эти коллекции производятся из `Map`, любое изменение в одной из этих коллекций будет отражено в соответствующей `Map`.

Метод `print()` предназначен для сбора итератора, созданного методом `entries`, и использования его для одновременного вывода каждого ключа и значения пары "ключ-значение". Оставшаяся часть программы предоставляет простые примеры различных операций с `Map` и проверяет каждую из типов `Map`.

При создании своего класса для использования его в качестве ключа в `Map`, следует обратить внимание на те же проблемы, что и при использовании его в `Set`.

##  Yöntem Seçimi

İlk diyagramdan görüldüğü gibi, aslında üç koleksiyon bileşeni var: `Map`, `List` ve `Set`. Bu her iki arayüz de sadece iki veya üç uygulaması vardır. Belirli bir arayüze ait işlevselliği kullanmak için belirli bir uygulamayı nasıl seçeceğinizi nasıl belirleyebilirsiniz?Чтобы понять этот вопрос, важно осознавать, что каждая реализация имеет свои особенности, преимущества и недостатки. Например, на диаграмме показано, что `Hashtable`, `Vector` и `Stack` имеют "особенности", так как они относятся к "традиционным" классам и поэтому не будут мешать существующему коду. Однако следует избегать использования их для нового (Java 1.2) кода.```Различия между другими коллекциями обычно сводятся к тому, что именно «поддерживают» каждую из них. Другими словами, это зависит от того, какой конкретный тип данных используется для реализации интерфейса. Например, `ArrayList`, `LinkedList` и `Vector` (приблизительно эквивалентен `ArrayList`) все реализуют интерфейс `List`, поэтому выбор любого из них приведёт к схожему поведению программы. Однако `ArrayList` (и `Vector`) поддерживаются массивом; в то время как `LinkedList` реализуется в виде обычной двусвязного списка, где каждый объект содержит данные и ссылки на предыдущий и следующий элементы списка. Именно поэтому при необходимости выполнять большое количество операций вставки и удаления в середине списка, `LinkedList` является наиболее подходящим выбором (у `LinkedList` есть ещё несколько дополнительных методов, наследуемых от `AbstractSequentialList`). В противном случае лучше выбрать `ArrayList`, который может работать быстрее. В качестве другого примера, `Set` может быть реализован как `ArraySet`, а также как `HashSet`. `ArraySet` представляет собой адаптацию `ArrayList` и предназначена для работы с небольшим количеством элементов, что делает её особенно подходящей для ситуаций, где требуется создание и удаление большого числа объектов типа `Set`. Однако, когда в `Set` содержится большое количество элементов, производительность `ArraySet` значительно снижается.```

Пожалуйста, обратите внимание, что я сохранил структуру и форматирование исходного текста, включая использование кодовых блоков для указания на специальные классы и интерфейсы.При написании программы, которая использует `Set`, следует предпочесть использование `HashSet`. Только при наличии особых условий (когда есть настоятельная необходимость повысить производительность), стоит переходить на использование `ArraySet`.(1) Выбор типа `List`

Чтобы оценить различия между различными реализациями `List`, самым простым способом является проведение тестирования производительности. Ниже приведён код, который создаёт базовый внутренний класс, используемый в качестве платформы для тестирования. Затем для каждого теста создаётся анонимный внутренний класс. Каждый такой внутренний класс вызывает метод `test()`. Такой подход позволяет легко добавлять и удалять тестовые случаи.```java
//: ListPerformance.java
// Demonstration of performance differences between various Lists
package c08.newcollections;
import java.util.*;
``````markdown
публичный класс ListPerformance {
  приватная статическая константа int REPS = 100;
  приватный абстрактный статический вложенный класс Tester {
    строка имя;
    int размер; // количество тестов
    Tester(строка имя, int размер) {
      это. имя = имя;
      это. размер = размер;
    }
    абстрактный void test(List а);
  }
  приватная статическая массив Tester[] tests = {
    новый Tester("получение", 300) {
      void test(List а) {
        для(int i = 0; i < REPS; i++) {
          для(int j = 0; j < а.size(); j++)
            а.get(j);
        }
      }
    },
    новый Tester("итерация", 300) {
      void test(List а) {
        для(int i = 0; i < REPS; i++) {
          Iterator it = а.iterator();
          пока(it.hasNext())
            it.next();
        }
      }
    },
    новый Tester("вставка", 1000) {
      void test(List а) {
        int половина = а.size() / 2;
        строка s = "тест";
        ListIterator it = а.listIterator(половина);
        для(int i = 0; i < размер * 10; i++)
          it.add(s);
      }
    },
    новый Tester("удаление", 5000) {
      void test(List а) {
        ListIterator it = а.listIterator(3);
        пока(it.hasNext()) {
          it.next();
          it.remove();
        }
      }
    },
  };
  публичная статическая void test(List а) {
    // Trick to output the class name:
    System.out.println("Testing " +
      а.getClass().getName());
    для(int i = 0; i < tests.length; i++) {
      Collection1.fill(а, tests[i].размер);
      System.out.print(tests[i].имя);
      длинное t1 = System.currentTimeMillis();
      tests[i].test(а);
      длинное t2 = System.currentTimeMillis();
      System.out.println(": " + (t2 - t1));
    }
  }
}
``````markdown
публичная статическая void основной(строка[] аргументы) {
    test(новый ArrayList());
    test(новый LinkedList());
}
}

///:~

```markdown
```Внутренний класс `Tester` является абстрактным классом, который служит базовым классом для различных тестов. Он включает строку для вывода перед началом теста, параметр `size`, используемый для вычисления количества тестов или элементов, конструктор для инициализации полей и абстрактный метод `test()`. Метод `test()` выполняет основную работу тестирования. Различные типы тестов сосредоточены в массиве `tests`. Мы используем различные анонимные внутренние классы, расширяющие `Tester`, чтобы инициализировать этот массив. Для добавления или удаления тестового элемента достаточно просто добавить или удалить определение внутреннего класса в массиве.```
```Сначала заполняется список, передаваемый в метод `test()`, затем производится замер времени выполнения тестов в массиве `tests`. Из-за различий в оборудовании результаты могут отличаться. Цель этой программы — показать относительные характеристики производительности различных коллекций. Ниже приведены результаты одного из испытаний:

| Тип          | Получение   | Итерация    | Вставка     | Удаление    |
| ------------- | ------------ | ------------ | ------------ | ------------ |
| `ArrayList`  | 110          | 270          | 1920         | 4780         |
| `LinkedList` | 1870         | 7580         | 170          | 110          |

Как видно, случайный доступ (`get()`) и итерация в `ArrayList` являются наиболее эффективными; однако для `LinkedList` они представляют значительный расход. Однако с другой стороны, вставка и удаление элементов посередине списка для `LinkedList` оказываются значительно более выгодными по сравнению с `ArrayList`. Лучшим подходом может быть использование `ArrayList` как базовой точки отсчета. Если позднее будет обнаружено снижение производительности из-за большого количества операций вставки и удаления, можно рассмотреть возможность перехода на `LinkedList`.

(2) Выбор типа `Set`

Можно выбрать между `ArraySet` и `HashSet`, в зависимости от размера `Set` (если требуется получить последовательный список из `Set`, используйте `TreeSet`; примечание ⑧). Этот тестовый скрипт поможет сделать выбор:```java
//: SetPerformance.java
package c08.newcollections;
import java.util.*;

public class SetPerformance {
    private static final int REPS = 200;
    private static abstract class Tester {
        String name;
        Tester(String name) { this.name = name; }
        abstract void test(Set s, int size);
    }
    private static Tester[] tests = {
        new Tester("addition") {
            void test(Set s, int size) {
                for (int i = 0; i < REPS; i++) {
                    s.clear();
                    Collection1.fill(s, size);
                }
            }
        },
        new Tester("contains") {
            void test(Set s, int size) {
                for (int i = 0; i < REPS; i++)
                    for (int j = 0; j < size; j++)
                        s.contains(Integer.toString(j));
            }
        },
        new Tester("iteration") {
            void test(Set s, int size) {
                for (int i = 0; i < REPS * 10; i++) {
                    Iterator it = s.iterator();
                    while (it.hasNext()) 
                        it.next();
                }
            }
        },
    };
    public static void test(Set s, int size) {
        // Trick to output the set's class name:
        System.out.println("Testing " + s.getClass().getName() + " size " + size);
        Collection1.fill(s, size);
        for (int i = 0; i < tests.length; i++) {
            System.out.print(tests[i].name);
            long t1 = System.currentTimeMillis();
            tests[i].test(s, size);
            long t2 = System.currentTimeMillis();
            System.out.println(": " + ((double)(t2 - t1)) / (double)size);
        }
    }
    public static void main(String[] args) {
        // Small:
        test(new TreeSet(), 10);
        test(new HashSet(), 10);
        // Medium:
        test(new TreeSet(), 100);
        test(new HashSet(), 100);
        // Large:
        test(new HashSet(), 1000);
        test(new TreeSet(), 1000);
    }
}
///:~
``````### Окончательные тесты `ArraySet` содержали только 500 элементов вместо 1000, так как они были слишком慢。```## Класс MapPerformance

| Тип      | Размер теста | Добавление | Содержание | Итерация |
| --------- | -------------- | ----------- | ---------- | -------- |
| TreeSet  | 10             | 22.0        | 11.0       | 16.0     |
|          | 100            | 22.5        | 13.2       | 12.1     |
|          | 1000           | 31.1        | 18.7       | 11.8     |
| HashSet  | 10             | 5.0         | 6.0        | 27.0     |
|          | 100            | 6.6         | 6.6        | 10.9     |
|          | 1000           | 7.4         | 6.6        | 9.5      |

При выполнении операций `add()` и `contains()`, `HashSet` значительно превосходит `TreeSet`. Кроме того, производительность практически не зависит от количества элементов. В общем случае при программировании использование `TreeSet` почти никогда не требуется.

(3) Выбор типа `Map`

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

```java
//: MapPerformance.java
// Показывает различия в производительности различных реализаций Map
package c08.newcollections;
import java.util.*;
``````java
public class MapPerformance {
    private static final int REPS = 200;

    public static Map fill(Map m, int size) {
        for (int i = 0; i < size; i++) {
            String x = Integer.toString(i);
            m.put(x, x);
        }
        return m;
    }

    private abstract static class Tester {
        String name;

        Tester(String name) {
            this.name = name;
        }

        abstract void test(Map m, int size);
    }

    private static Tester[] tests = {
            new Tester("put") {
                @Override
                void test(Map m, int size) {
                    for (int i = 0; i < REPS; i++) {
                        m.clear();
                        fill(m, size);
                    }
                }
            },
            new Tester("get") {
                @Override
                void test(Map m, int size) {
                    for (int i = 0; i < REPS; i++)
                        for (int j = 0; j < size; j++)
                            m.get(Integer.toString(j));
                }
            },
            new Tester("iteration") {
                @Override
                void test(Map m, int size) {
                    for (int i = 0; i < REPS * 10; i++) {
                        Iterator it = m.entries().iterator();
                        while (it.hasNext()) {
                            it.next();
                        }
                    }
                }
            }
    };

    public static void test(Map m, int size) {
        // Хит для вывода имени класса:
        System.out.println("Testing " + m.getClass().getName() + " size " + size);
        fill(m, size);
        for (int i = 0; i < tests.length; i++) {
            System.out.print(tests[i].name);
            long t1 = System.currentTimeMillis();
            tests[i].test(m, size);
            long t2 = System.currentTimeMillis();
            System.out.println(": " + ((double) (t2 - t1) / (double) size));
        }
    }

    public static void main(String[] args) {
        // Малый размер:
        test(new Hashtable(), 10);
        test(new HashMap(), 10);
        test(new TreeMap(), 10);

        // Средний размер:
        test(new Hashtable(), 100);
        test(new HashMap(), 100);
        test(new TreeMap(), 100);

        // Большой размер:
        test(new HashMap(), 1000);
        test(new Hashtable(), 1000);
        test(new TreeMap(), 1000);
    }
}
```
```markdown
Из-за размера `Map`, который является наиболее серьезной проблемой, тестирование производительности программы разделено на части в зависимости от размера `Map` (или его емкости) для получения убедительных результатов тестирования.
```Ниже представлены некоторые результаты (они могут различаться на вашей машине):| Тип          | Размер теста | Вставка | Получение | Итерация |
| ------------- | ------------- | ------- | --------- | -------- |
| Hashtable    | 10           | 11.0   | 5.0      | 44.0    |
|              | 100          | 7.7    | 7.7      | 16.5    |
|              | 1000         | 8.0    | 8.0      | 14.4    |
| TreeMap      | 10           | 16.0   | 11.0     | 22.0    |
|              | 100          | 25.8   | 15.4     | 13.2    |
|              | 1000         | 33.8   | 20.9     | 13.6    |
| HashMap      | 10           | 11.0   | 6.0      | 33.0    |
|              | 100          | 8.2    | 7.7      | 13.7    |
|              | 1000         | 8.0    | 7.8      | 11.9    |Даже при размере 10, производительность `ArrayMap` хуже, чем у `HashMap` — за исключением цикла итерации. Однако при использовании `Map`, действие итерации обычно не играет большой роли (`get()` обычно является местом, где мы тратим больше всего времени). `TreeMap` обеспечивает отличную производительность для `put()` и итерации, но `get()` работает медленнее. Тем не менее, почему нам всё ещё нужна `TreeMap`? Это позволяет использовать её не как `Map`, а как способ создания последовательного списка. Основное свойство дерева заключается в том, что оно всегда упорядочено, поэтому нет необходимости специально сортировать его (его метод сортировки будет рассмотрен ниже). После заполнения `TreeMap` можно вызвать `keySet()`, чтобы получить набор ключей "картинки". Затем используйте `toArray()` для создания массива, содержащего эти ключи. Затем можно использовать статический метод `Arrays.binarySearch()` для быстрого поиска в упорядоченном массиве. Конечно, это может потребоваться только тогда, когда поведение `HashMap` недопустимо. Поскольку основная цель дизайна `HashMap` — это быстрый поиск. Наконец, при использовании `Map` первым выбором должно быть `HashMap`. Только в очень редких случаях следует рассматривать другие варианты.Кроме того, в таблице выше есть ещё одна проблема производительности, которая не была показана. Ниже представлен программный код для тестирования скорости создания различных типов `Map`:

```java
//: MapCreation.java
// Демонстрация временных различий при создании Map
package c08.newcollections;
import java.util.*;

public class MapCreation {
  public static void main(String[] args) {
    final long REPS = 100000;
    long t1 = System.currentTimeMillis();
    System.out.print("Hashtable");
    for(long i = 0; i < REPS; i++)
      new Hashtable();
    long t2 = System.currentTimeMillis();
    System.out.println(": " + (t2 - t1));
    t1 = System.currentTimeMillis();
    System.out.print("TreeMap");
    for(long i = 0; i < REPS; i++)
      new TreeMap();
    t2 = System.currentTimeMillis();
    System.out.println(": " + (t2 - t1));
    t1 = System.currentTimeMillis();
    System.out.print("HashMap");
    for(long i = 0; i < REPS; i++)
      new HashMap();
    t2 = System.currentTimeMillis();
    System.out.println(": " + (t2 - t1));
  }
}
///:~
```

Пожалуйста, обратите внимание, что имена классов, методов и переменных остались без изменения в соответствии с правилами перевода.```При написании этого программного кода создание `TreeMap` было значительно быстрее других двух типов (хотя рекомендуется проверить это самостоятельно, так как в новых версиях могут быть улучшены показатели производительности для `ArrayMap`). Учитывая этот аспект, а также отличную производительность метода `put()` у `TreeMap`, лучшим подходом будет следующий: если требуется создать большое количество `Map`, но основной акцент делается на последующих операциях поиска, то следует начать с создания и заполнения `TreeMap`. Когда объём запросов увеличивается, можно преобразовать важный `TreeMap` в `HashMap` — используя конструктор `HashMap(Map)`. Аналогично, следует обращать внимание на эти вопросы только после того, как фактические проблемы производительности будут выявлены — начните работу, а затем оптимизируйте её по мере необходимости.## 8.7.6 Несоответствующие операции

Используя статический метод `Arrays.asList()`, можно преобразовать массив в `List`, как показано ниже:

```java
//: Unsupported.java
// Иногда методы, определённые в интерфейсах коллекций,
// работают некорректно!
package c08.newcollections;
import java.util.*;
``````java
public class Unsupported {
   private static String[] s = {
     "один", "два", "три", "четыре", "пять",
     "шесть", "семь", "восемь", "девять", "десять",
   };
   static List a = Arrays.asList(s);
   static List a2 = Arrays.asList(
     new String[] { s[3], s[4], s[5] });
   public static void main(String[] args) {
     Collection1.print(a); // Обход
     System.out.println(
       "a.contains(" + s[0] + ") = " +
       a.contains(s[0]));
     System.out.println(
       "a.containsAll(a2) = " +
       a.containsAll(a2));
     System.out.println("a.isEmpty() = " +
       a.isEmpty());
     System.out.println(
       "a.indexOf(" + s[5] + ") = " +
       a.indexOf(s[5]));
     // Обход назад:
     ListIterator lit = a.listIterator(a.size());
     while(lit.hasPrevious())
       System.out.print(lit.previous());
     System.out.println();
     // Изменение значений элементов:
     for(int i = 0; i < a.size(); i++)
       a.set(i, "47");
     Collection1.print(a);
     // Компиляция проходит успешно, но выполнение невозможно:
     lit.add("X"); // Несоответствующая операция
     a.clear(); // Несоответствующая операция
     a.add("одиннадцать"); // Несоответствующая операция
     a.addAll(a2); // Несоответствующая операция
     a.retainAll(a2); // Несоответствующая операция
     a.remove(s[0]); // Несоответствующая операция
     a.removeAll(a2); // Несоответствующая операция
   }
} ///:~
```

Из этого можно заключить, что были реализованы лишь некоторые части интерфейсов `Collection` и `List`. Оставшиеся методы приводят к нежелательной ситуации, известной как `UnsupportedOperationException`. В следующей главе мы подробнее рассмотрим исключения, но здесь стоит сделать небольшое упоминание.Ключевой момент в том, что "коллекционные интерфейсы" и некоторые другие интерфейсы внутри нового коллекционного пакета содержат "опциональные" методы. В классах, реализующих эти интерфейсы, либо предоставляется, либо не предоставляется поддержка этих методов. При вызове недоступного метода возникает исключение `UnsupportedOperationException` (исключение "не поддерживаемое действие"), что указывает на программную ошибку. Может показаться странным, но ведь "интерфейсы" и базовые классы привлекательны именно тем, что они обещают реализацию методов с полезным поведением? Однако указанные исключения нарушают это обещание — некоторые вызываемые методы не только не выполняют полезных действий, но и могут привести к завершению программы. В таких случаях гарантии безопасности типа кажутся бесполезными! Но всё не так плохо. Благодаря `Collection`, `List`, `Set` или `Map` компилятор все еще ограничивает нас в вызовах только методов этого интерфейса, поэтому он отличается от Smalltalk (где любой метод может быть вызван для любого объекта, и только во время выполнения программы можно узнать, будет ли этот вызов успешным). Кроме того, большинство методов, использующих `Collection` как аргумент, могут только читать данные из коллекции — все «чтение» методы `Collection` обязательны.Таким образом, система избегает конфликтов интерфейсов на этапе проектирования. В других паттернах дизайна библиотеки коллекций часто заканчиваются множеством интерфейсов, каждый из которых описывает каждую возможную вариацию основной схемы, что делает их сложными для изучения и использования. Иногда даже трудно захватить все специальные случаи интерфейсов, поскольку новые интерфейсы могут быть созданы для любых новых ситуаций. Но методы "неподдерживаемого действия" в Java достигают одной из ключевых целей нового набора коллекций: легкость обучения и использования. Для эффективности этого подхода требуется выполнение следующих условий:

(1) `UnsupportedOperationException` должен быть "очень" редким событием. То есть, для большинства классов все операции должны быть доступны. Только в особых случаях одна или две операции могут оказаться недоступными. Новый набор коллекций удовлетворяет этому требованию, потому что большинство используемых классов — `ArrayList`, `LinkedList`, `HashSet` и `HashMap`, а также другие схемы коллекций — поддерживают все операции. Однако если вы хотите создать новый тип коллекции, который не предоставляет значимую реализацию для всех методов интерфейса, то этот подход действительно предлагает возможность сделать это через "черный список".

---

Исправлено:
- "черный вход" заменено на "черный список", так как более точно передает смысл оригинального английского термина "blacklist".
- Удалены лишние кавычки вокруг "очень" и "черный список".(2) Если операция недоступна, то `UnsupportedOperationException` (исключение неподдерживаемого действия) должно возникнуть при реализации, а не после того, как продукт был передан клиенту. Это, конечно, указывает на ошибку программирования — некорректное использование класса. Это нельзя считать полностью уверенностью, но и эта схема имеет "экспериментальный" характер — только после нескольких попыток можно найти оптимальное решение. В примере выше `Arrays.asList()` создаёт список (`List`), который основан на массиве с фиксированной длиной. Поэтому поддерживаются только те операции, которые не меняют длину массива. С другой стороны, если требуется новый интерфейс для представления различных поведений (например, называемый `FixedSizeList` — фиксированный список), существует риск столкнуться с большей сложностью. В результате при попытке использования библиотеки в будущем, вы быстро можете запутаться.

Документация методов, принимающих параметры типа `Collection`, `List`, `Set` или `Map`, должна указывать, какие обязательные методы должны быть реализованы. Например, сортировка требует реализации методов `set()` и `Iterator.set()`, но не включает `add()` и `remove()`.

## 8.7.7 Сортировка и поискJava 1.2 добавила свой набор полезных инструментов для сортировки и поиска массивов или списков. Эти инструменты являются "статическими" методами двух новых классов: `Arrays` для сортировки и поиска массивов, а также `Collections` для сортировки и поиска списков.### (1) Массивы

Класс `Arrays` предоставляет перегруженные методы `sort()` и `binarySearch()` для всех массивов базовых типов данных, что также применимо к `String` и `Object`. Ниже приведен пример того, как можно отсортировать и выполнить двоичный поиск в массиве байтов (другие все базовые типы данных аналогичны) и массиве `String`:

```java
//: Array1.java
// Проверка сортировки и поиска в Arrays
package c08.newcollections;
import java.util.*;

public class Array1 {
  static Random r = new Random();
  static String ssource =
    "ABCDEFGHIJKLMNOPQRSTUVWXYZ" +
    "abcdefghijklmnopqrstuvwxyz";
  static char[] src = ssource.toCharArray();

  // Создание случайной строки
  public static String randString(int length) {
    char[] buf = new char[length];
    int rnd;
    for(int i = 0; i < length; i++) {
      rnd = Math.abs(r.nextInt()) % src.length;
      buf[i] = src[rnd];
    }
    return new String(buf);
  }

  // Создание массива случайных строк
  public static String[] randStrings(int length, int size) {
    String[] s = new String[size];
    for(int i = 0; i < size; i++)
      s[i] = randString(length);
    return s;
  }

  public static void print(byte[] b) {
    for(int i = 0; i < b.length; i++)
      System.out.print(b[i] + " ");
    System.out.println();
  }

  public static void print(String[] s) {
    for(int i = 0; i < s.length; i++)
      System.out.print(s[i] + " ");
    System.out.println();
  }

  public static void main(String[] args) {
    byte[] b = new byte[15];
    r.nextBytes(b); // Заполнение случайными байтами
    print(b);
    Arrays.sort(b);
    print(b);
    int loc = Arrays.binarySearch(b, b[10]);
    System.out.println("Положение " + b[10] +
      " равно " + loc);
  }
}
``````java
    // Тест сортировки и поиска строк
    String[] s = randStrings(4, 10);
    print(s);
    Arrays.sort(s);
    print(s);
    int loc = Arrays.binarySearch(s, s[4]);
    System.out.println("Положение " + s[4] +
      " = " + loc);
  }
}
///:~
```
Первая часть класса включает полезные инструменты для создания объектов со случайными строками; выбранные случайные буквы хранятся в массиве символов. Метод `randString()` возвращает строку произвольной длины, а метод `readStrings()` создаёт массив случайных строк с указанием длины каждой строки и желаемого размера массива. Два метода `print()` упрощают вывод демонстрационного массива. В методе `main()`, `Random.nextBytes()` заполняет массив случайными байтами (нет аналогичного метода для создания массивов других примитивных типов данных). После получения массива можно заметить, что выполнение `sort()` или `binarySearch()` требует всего одного вызова метода. Также стоит отметить важное предупреждение относительно `binarySearch()`: если `sort()` не был вызван до `binarySearch()`, поведение может быть непредсказуемым, вплоть до возможного бесконечного цикла.
```Сортировка и поиск строк имеют схожие характеристики, но при выполнении программы можно заметить интересное явление: сортировка происходит в алфавитном порядке, то есть большие буквы располагаются перед маленькими буквами в таблице символов. Таким образом, все большие буквы находятся в начале списка, за которыми следуют маленькие — Z оказывается перед a. Похоже, даже телефонные книги используют такую последовательность.

(2) Сравнение и компаратор

Но что делать, если такой способ сортировки нас не устраивает? Например, в конце этой книги мы будем иметь дело с индексом, где нам потребуется отдельно искать слова, начинающиеся с A или a, что будет крайне раздражать читателя.Чтобы отсортировать массив объектов, возникает вопрос: как сравнивать два объекта друг с другом? К сожалению, первоначальные дизайнеры Java не считали это важным вопросом, иначе он бы уже был решён в базовом классе Object. Одним из последствий этого является необходимость внешней сортировки объектов, а новые коллекции предоставляют стандартные способы реализации этой операции (хотя идеальным было бы решение внутри самого класса Object).

Для массива `Object` (а также для `String`, который является типом `Object`) можно использовать метод `sort()`, передав ему ещё один параметр — объект, реализующий интерфейс `Comparator` (то есть "интерфейс сравнения", часть нового коллекционного пакета). Этот объект использует свой единственный метод `compare()`, чтобы сравнивать два объекта. В этом методе первый аргумент сравнивается со вторым: если он меньше, возвращается отрицательное число; если они равны, возвращается ноль; если он больше, возвращается положительное число. На основе этого правила пример с `String` может быть переписан так, чтобы действительно сортировать строки в алфавитном порядке:

```java
Arrays.sort(strings, new Comparator<String>() {
    public int compare(String s1, String s2) {
        return s1.compareTo(s2);
    }
});
```

Этот код создает компаратор для сортировки строк в алфавитном порядке.```java
Arrays.sort(strings, new Comparator<String>() {
    @Override
    public int compare(String s1, String s2) {
        return s1.compareTo(s2);
    }
});
```

Этот подход позволяет выполнять более сложные операции сортировки, чем просто использование стандартного поведения `sort()`.

```markdown
//: AlphaComp.java
// Использование Comparator для алфавитной сортировки
package c08.newcollections;
import java.util.*;

public class AlphaComp implements Comparator {
  public int compare(Object o1, Object o2) {
    // Предполагается, что используется только для строк...
    String s1 = ((String)o1).toLowerCase();
    String s2 = ((String)o2).toLowerCase();
    return s1.compareTo(s2);
  }
  public static void main(String[] args) {
    String[] s = Array1.randStrings(4, 10);
    Array1.print(s);
    AlphaComp ac = new AlphaComp();
    Arrays.sort(s, ac);
    Array1.print(s);
    // Для поиска также следует использовать тот же Comparator:
    int loc = Arrays.binarySearch(s, s[3], ac);
    System.out.println("Положение " + s[3] + " = " + loc);
  }
} ///:~
```

Метод `compare()` преобразует переданные объекты в строки, чтобы обеспечить алфавитную сортировку. Это гарантирует, что метод работает только со строками — система выполнения будет поймать любую ошибку во время выполнения. Оба входных значения преобразуются в нижний регистр, а затем сравниваются с помощью метода `String.compareTo()`.

Если вы используете свой собственный `Comparator` для вызова метода `sort()`, то при использовании метода `binarySearch()` вам потребуется использовать тот же самый `Comparator`.
```Класс `Arrays` также предоставляет метод `sort()`, который принимает всего один параметр: массив объектов. Этот метод `sort()` не требует `Comparator`. Вместо этого он использует "естественнный" способ сравнения, реализуемый через интерфейс `Comparable`. Интерфейс `Comparable` содержит только одно метод — `compareTo()`, который возвращает отрицательное значение, если текущий объект меньше указанного объекта, ноль, если они равны, и положительное значение, если текущий объект больше указанного объекта.Пример ниже демонстрирует это:

```
//: CompClass.java
// Класс, реализующий интерфейс Comparable
package c08.newcollections;
import java.util.*;
```

```markdown
## Класс `CompClass`, реализующий интерфейс `Comparable`

### Описание

Класс `CompClass` реализует интерфейс `Comparable`. Он содержит метод `compareTo`, который позволяет сравнивать объекты этого типа.

### Код

```java
public class CompClass implements Comparable<CompClass> {
  private int i;

  public CompClass(int ii) {
    i = ii;
  }

  @Override
  public int compareTo(CompClass o) {
    // Неявно проверяет правильность типа:
    int argi = o.i;
    if (i == argi) return 0;
    if (i < argi) return -1;
    return 1;
  }

  public static void print(Object[] a) {
    for (int i = 0; i < a.length; i++) {
      System.out.print(a[i] + " ");
    }
    System.out.println();
  }

  @Override
  public String toString() {
    return i + "";
  }

  public static void main(String[] args) {
    CompClass[] a = new CompClass[20];
    for (int i = 0; i < a.length; i++) {
      a[i] = new CompClass((int)(Math.random() * 100));
    }
    print(a);
    Arrays.sort(a);
    print(a);
    int loc = Arrays.binarySearch(a, a[3]);
    System.out.println("Location of " + a[3] + " = " + loc);
  }
}
```
///
```Конечно, наш метод `compareTo()` также может усложняться в зависимости от ситуации.

(3) Списки```Сортировка и поиск списка (класс `List`) можно выполнить с использованием того же подхода, что и для массива. Статические методы для работы со списками содержатся в классе `Collections`. Они имеют аналогичные сигнатуры, как и в классе `Arrays`: метод `sort(List)` используется для сортировки списка объектов, реализующих интерфейс `Comparable`; метод `binarySearch(List, Object)` позволяет найти конкретный объект в списке; метод `sort(List, Comparator)` сортирует список с помощью компаратора; а метод `binarySearch(List, Object, Comparator)` используется для поиска объекта в списке с применением компаратора (примечание ⑨).Пример ниже демонстрирует использование заранее определённых классов `CompClass` и `AlphaComp` для различных методов сортировки из класса `Collections`:

```java
//: ListSort.java
// Сортировка и поиск списков с помощью 'Collections'
package c08.newcollections;
import java.util.*;

public class ListSort {
  public static void main(String[] args) {
    final int SZ = 20;
    // Используем "естественный способ сравнения":
    List a = new ArrayList();
    for(int i = 0; i < SZ; i++)
      a.add(new CompClass((int)(Math.random() * 100)));
    Collection1.print(a);
    Collections.sort(a);
    Collection1.print(a);
    Object find = a.get(SZ / 2);
    int loc = Collections.binarySearch(a, find);
    System.out.println("Положение " + find + " = " + loc);
    // Используем компаратор:
    List b = new ArrayList();
    for(int i = 0; i < SZ; i++)
      b.add(Array1.randString(4));
    Collection1.print(b);
    AlphaComp ac = new AlphaComp();
    Collections.sort(b, ac);
    Collection1.print(b);
    find = b.get(SZ / 2);
    // При поиске также следует использовать компаратор:
    loc = Collections.binarySearch(b, find, ac);
    System.out.println("Положение " + find + " = " + loc);
  }
} ///:~
```

Примечание ⑨: На момент написания книги было объявлено о новом методе `Collections.stableSort()`, который позволит выполнять сортировку слиянием, но тестовая версия ещё не была выпущена.

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

Класс `TreeMap` также требует, чтобы его объекты были отсортированы согласно интерфейсу `Comparable` или через компаратор.

## 8.7.8 Полезные утилиты

Класс `Collections` содержит множество полезных утилит:```
enumeration(Collection)
```
Производит старый стиль перечисления (`Enumeration`) для аргумента.

`max(Collection)`

`min(Collection)`

Используют метод естественного сравнения объектов в коллекции для получения максимального или минимального элемента в аргументе.

`max(Collection, Comparator)`

`min(Collection, Comparator)`

Используют компаратор для получения максимального или минимального элемента в коллекции.

`nCopies(int n, Object o)`

Возвращает незменяемый список размером `n`, все ссылки которого указывают на `o`.

`subList(List, int min, int max)`

Возвращает новый список, который является представлением указанного аргумента списка с индексами, начинающимися с `min` и заканчивающимися сразу перед `max`.

---

Обратите внимание, что `min()` и `max()` работают с объектами типа `Collection`, а не `List`. Поэтому нет необходимости беспокоиться о том, отсортирована ли коллекция (как было отмечено ранее, перед выполнением операции `binarySearch()`, необходимо отсортировать список или массив).

### Создание незменяемой коллекции или карты

Часто полезнее создать "только для чтения" версию коллекции или карты. Класс `Collections` позволяет нам достичь этой цели, передавая исходный контейнер в метод, который возвращает незменяемую версию. Всего существует четыре варианта этого метода для типов `Collection` (если вы не хотите рассматривать коллекцию как более специализированный тип), `List`, `Set` и `Map`. Ниже приведён пример правильного создания "только для чтения" версий этих типов:```java
//: ReadOnly.java
// Использование методов Collections.unmodifiable
package c08.newcollections;
import java.util.*;

public class ReadOnly {
  public static void main(String[] args) {
    Collection c = new ArrayList();
    Collection1.fill(c); // Вставка полезных данных
    c = Collections.unmodifiableCollection(c);
    Collection1.print(c); // Чтение допустимо
    //! c.add("one"); // Изменять его нельзя
  }
}
```

---

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

```markdown
Список a = new ArrayList<>();
Collection1.fill(a);
a = Collections.unmodifiableList(a);
ListIterator lit = a.listIterator();
System.out.println(lit.next()); // Чтение успешно
//! lit.add("one"); // Нельзя изменять его

Множество s = new HashSet<>();
Collection1.fill(s);
s = Collections.unmodifiableSet(s);
Collection1.print(s); // Чтение успешно
//! s.add("one"); // Нельзя изменять его

Карта m = new HashMap<>();
Map1.fill(m, Map1.testData1);
m = Collections.unmodifiableMap(m);
Map1.print(m); // Чтение успешно
//! m.put("Ralph", "Howdy!");
}
} ///:~
```

Для каждой ситуации требуется заполнить контейнер действительными данными до того, как сделать его доступным только для чтения. После успешной загрузки следует заменить текущую ссылку на ссылку, полученную с помощью метода `unmodifiable`. Это позволяет эффективно предотвратить случайное изменение содержимого после того, как он был сделан недопустимым для изменения. С другой стороны, этот подход также позволяет нам хранить модифицируемые контейнеры в виде приватных полей внутри класса и возвращать ссылку на неподвижный контейнер из метода. Таким образом, хотя мы можем изменять его внутри класса, никто больше не сможет этого делать.
```Вызов метода `unmodifiable` для конкретного типа не вызывает проверки компилятором, но любая попытка изменения такого контейнера приведёт к выбрасыванию исключения `UnsupportedOperationException`.

(2) Синхронизация коллекций или карт

Ключевое слово `synchronized` является важной частью механизма многопоточности. Мы подробнее рассмотрим эту тему в главе 14. В данном случае важно отметить, что класс `Collections` предоставляет способ автоматической синхронизации всего контейнера. Его синтаксис аналогичен методам `unmodifiable`:

```java
//: Synchronization.java
// Использование методов synchronized из Collections
package c08.newcollections;
import java.util.*;

public class Synchronization {
  public static void main(String[] args) {
    Collection c =
      Collections.synchronizedCollection(new ArrayList());
    List list = Collections.synchronizedList(new ArrayList());
    Set s = Collections.synchronizedSet(new HashSet());
    Map m = Collections.synchronizedMap(new HashMap());
  }
}
///:~
```В этом случае мы передаем новые контейнеры через соответствующие методы синхронизации; это позволяет избежать случайного раскрытия невалидированной версии. Новый набор коллекций также предоставляет механизм защиты от одновременного изменения одного контейнера несколькими процессами. При итерации по контейнеру, если другие процессы вмешиваются и вставляют, удаляют или модифицируют объект внутри этого контейнера, возникает риск столкнуться с конфликтами. Мы можем передать этот объект, он может находиться перед нами, размер контейнера может уменьшиться после вызова `size()`. Мы сталкиваемся со множеством возможных опасностей. Для решения этой проблемы новый набор коллекций включает механизмы, позволяющие выявлять любые изменения контейнера, кроме тех, которые мы сами производим. В случае обнаружения попыток других процессов изменять контейнер немедленно выбрасывается исключение `ConcurrentModificationException` (исключение при параллельной модификации). Этот механизм называют "немедленным завершением" — вместо использования более сложных алгоритмов для обнаружения проблем позже, он сразу генерирует исключение.