8.4 Типы коллекций

If you simply create a `CrashJava` object and print it out, you will get an infinite series of exceptions. However, if you place a `CrashJava` object into a `Vector` and print the `Vector`, as shown above, no error messages are printed, not even exceptions occur. In this case, Java just stops working (although it at least did not destroy my operating system). This was tested on Java 1.1.

What happens here is automatic type conversion for the string. When we use the following line:

```java
"Address of CrashJava: " + this
```Компилятор видит знак `+` после строки и пытается преобразовать `this` в строку. При преобразовании вызывается метод `toString()`, который вызывает рекурсивный вызов. Если это происходит внутри `Vector`, кажется, что стек переполняется, а механизмы управления исключениями вообще не имеют возможности отреагировать. Если действительно хотите распечатать адрес объекта в данной ситуации, решение заключается в вызове метода `toString()` класса `Object`. В этом случае нет необходимости использовать ключевое слово `this`, достаточно будет вызвать `super.toString()`. Однако стоит отметить, что это возможно при условии прямого наследования от класса `Object` либо отсутствия переопределения метода `toString` в родительском классе.## 8.4.2 `BitSet`

`BitSet` представляет собой вектор битовых значений. Если вам требуется эффективное хранение большого количества информации типа «вкл/выкл», то использование `BitSet` является хорошей идеей. Однако его применение имеет смысл с точки зрения размера данных; если вы стремитесь к высокой скорости доступа к данным, то использование массива примитивных типов может оказаться быстрее.

Кроме того, минимальной длиной `BitSet` является длина одного значения типа `long`: 64 бита. Это значит, что если вы планируете хранить меньшее количество данных, например, 8 бит, использование `BitSet` будет избыточным. Поэтому лучше всего создать свой класс для хранения своих флагов.

В обычном `Vector` при добавлении все больше элементов коллекция автоматически увеличивает свое внутреннее хранилище. Аналогично, `BitSet` также может увеличиваться в зависимости от потребностей. Однако версия Java 1.0 делала это менее эффективно, чем последующие версии (например, Java 1.1 исправила эту проблему). Ниже представлен пример работы `BitSet` и демонстрация ошибки в версии 1.0:

```java
//: Bits.java
// Демонстрация использования BitSet
import java.util.*;

public class Bits {
  public static void main(String[] args) {
    Random rand = new Random();
    // Берём младший значащий бит из следующего случайного числа:
    byte bt = (byte)rand.nextInt();
    BitSet bb = new BitSet();
    for(int i = 7; i >= 0; i--) {
      if (((1 << i) & bt) != 0)
        bb.set(i);
      else
        bb.clear(i);
    }
    System.out.println("Значение байта: " + bt);
    printBitSet(bb);
  }

  private static void printBitSet(BitSet bitset) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < bitset.size(); i++) {
      if (bitset.get(i))
        sb.append('1');
      else
        sb.append('0');
    }
    System.out.println(sb.toString());
  }
}
``````markdown
```java
short st = (short)rand.nextInt();
BitSet bs = new BitSet();
for(int i = 15; i >= 0; i--) {
  if (((1 << i) & st) != 0)
    bs.set(i);
  else
    bs.clear(i);
}
System.out.println("Значение короткого целого: " + st);
printBitSet(bs);

int it = rand.nextInt();
BitSet bi = new BitSet();
for(int i = 31; i >= 0; i--) {
  if (((1 << i) & it) != 0)
    bi.set(i);
  else
    bi.clear(i);
}
System.out.println("Значение целого: " + it);
printBitSet(bi);
}

private static void printBitSet(BitSet bitset) {
StringBuilder sb = new StringBuilder(bitset.size());
for (int i = 0; i < bitset.size(); i++) {
sb.append(bitset.get(i) ? '1' : '0');
}
System.out.println(sb.toString());
}

// Тестирование битовых наборов >= 64 бит:
BitSet b127 = new BitSet();
b127.set(127);
System.out.println("Бит 127 установлен: " + b127);
BitSet b255 = new BitSet(65);
b255.set(255);
System.out.println("Бит 255 установлен: " + b255);
BitSet b1023 = new BitSet(512);
// Без следующей строки возникает исключение
// в реализации BitSet в Java 1.0:
//    b1023.set(1023);
b1023.set(1024);
System.out.println("Бит 1023 установлен: " + b1023);
static void printBitSet(BitSet b) {
System.out.println("Биты: " + b);
String bbits = new String();
for(int j = 0; j < b.size(); j++)
bbits += (b.get(j) ? "1" : "0");
System.out.println("Паттерн битов: " + bbits);
}

//: Stacks.java
// Простой пример использования стека,
// который читает каждую строку массива
// и помещает её как строку в стек.
import java.util.*;

public class Stacks {
  static String[] months = {
    "Январь", "Февраль", "Март", "Апрель",
    "Май", "Июнь", "Июль", "Август", "Сентябрь",
    "Октябрь", "Ноябрь", "Декабрь"
  };
  public static void main(String[] args) {
    Stack<String> stk = new Stack<>();
    for(int i = 0; i < months.length; i++)
      stk.push(months[i] + " ");
    System.out.println("stk = " + stk);
    // Обработка стека как объекта типа Vector:
    stk.add("Последняя строка");
    System.out.println(
      "элемент  Yöntem 5 = " + stk.get(5));
    System.out.println("выталкивание элементов:");
    while (!stk.isEmpty()) {
      System.out.println(stk.pop());
    }
  }
}
///:~
```
```Каждая строка массива `месяцы` добавляется в стек методом `push()`, а затем извлекается из вершины стека методом `pop()`. Важно отметить, что операции, доступные для объектов типа `Vector`, также применимы к объектам типа `Stack`. Это связано с тем, что класс `Stack` является подклассом `Vector`.

## 8.4.4 Hashtable

Класс `Vector` позволяет выбирать объекты по номеру, таким образом связывая число с объектом. Но что если нам нужно выбрать объекты по другому критерию? Например, стек выбирает объекты по принципу "последний вошёл — первый вышел". Такое "связывание" объектов может называться "отображением", "словарём" или "ассоциативным массивом". Концептуально это похоже на `Vector`, но вместо выбора объекта по номеру мы выбираем его по значению ключа!В Java эта концепция реализуется через абстрактный класс `Dictionary`. Интерфейс этого класса очень прост: метод `size()` сообщает количество элементов; метод `isEmpty()` проверяет, пуст ли словарь; метод `put(Object key, Object value)` добавляет значение и связывает его с ключом; метод `get(Object key)` получает значение по ключу; метод `remove(Object key)` удаляет пару "ключ-значение". Также можно использовать методы перечисления: метод `keys()` создаёт перечисление ключей (`Enumeration`); метод `elements()` создаёт перечисление всех значений. Вот и всё, что делает класс `Dictionary`.

Реализация `Dictionary` не представляет особой сложности. Ниже приведён простой пример, использующий два `Vector`: один для хранения ключей, а другой — для значений:```java
//: AssocArray.java
// Простая версия Dictionary
import java.util.*;

public class AssocArray extends Dictionary {
  private Vector keys = new Vector();
  private Vector values = new Vector();
  public int size() { return keys.size(); }
  public boolean isEmpty() {
    return keys.isEmpty();
  }
  public Object put(Object key, Object value) {
    keys.addElement(key);
    values.addElement(value);
    return key;
  }
  public Object get(Object key) {
    int index = keys.indexOf(key);
    // indexOf() возвращает -1, если ключ не найден:
    if(index == -1) return null;
    return values.elementAt(index);
  }
  public Object remove(Object key) {
    int index = keys.indexOf(key);
    if(index == -1) return null;
    keys.removeElementAt(index);
    Object returnval = values.elementAt(index);
    values.removeElementAt(index);
    return returnval;
  }
  public Enumeration keys() {
    return keys.elements();
  }
  public Enumeration elements() {
    return values.elements();
  }
  // Проверка:
  public static void main(String[] args) {
    AssocArray aa = new AssocArray();
    for(char c = 'a'; c <= 'z'; c++)
      aa.put(String.valueOf(c),
             String.valueOf(c).toUpperCase());
    char[] ca = { 'a', 'e', 'i', 'o', 'u' };
    for(int i = 0; i < ca.length; i++)
      System.out.println("Заглавные буквы: " + 
             aa.get(String.valueOf(ca[i])));
  }
} ///:~
```При определении `AssocArray`, первым делом мы замечаем, что он «расширяет» `Dictionary`. Это означает, что `AssocArray` является производным от типа `Dictionary`, поэтому его можно использовать таким же образом, как и `Dictionary`. Если вы хотите создать свой собственный `Dictionary`, вам потребуется реализовать все методы, находящиеся внутри `Dictionary` (и эти методы должны быть переопределены, поскольку они являются абстрактными, за исключением конструктора).

Ключи типа `Vector key` и значения типа `value` связываются через стандартный индексный номер. То есть, если мы вызываем `put()` с ключом `roof` и значением `blue`, предположим, что нам нужно связать части дома с их цветами краски, а в `AssocArray` уже  Yöntem 100 элементов, то `roof` будет иметь индекс 101, а `blue` — значение 101. Также обратите внимание на `get()`: если мы передаем ключ `roof`, он вернет индексный номер, который затем используется для получения значения из связанного значения вектора.

Тесты, выполняемые в `main()`, очень просты; они просто преобразуют строчные буквы в прописные, что, конечно, можно сделать более эффективно. Однако это демонстрирует мощь `AssocArray`.Стандартная библиотека Java содержит лишь один вариант `Dictionary`, называемый `Hashtable` (хэш-таблица, примечание ③). Хэш-таблица Java имеет тот же интерфейс, что и `AssocArray` (поскольку оба они наследуются от `Dictionary`). Но есть одна особенность, которая демонстрирует различие: производительность. Если внимательно рассмотреть то, что требуется выполнить при вызове `get()`, становится очевидно, что поиск ключа в `Vector` происходит значительно медленнее. Однако использование хэш-таблицы позволяет существенно увеличить скорость. Вместо того чтобы выполнять длинный линейный поиск ключа, используется специальное значение, известное как "хэш-код". Хэш-код получает информацию из объекта и преобразует её в целое число (`int`), которое является относительно уникальным для этого объекта. У всех объектов есть хэш-код, а метод `hashCode()` является частью базового класса `Object`. `Hashtable` использует `hashCode()` объекта для быстрого поиска ключа. Это позволяет значительно повысить производительность (④). Конкретные механизмы работы хэш-таблицы выходят за рамки данного учебника (⑤) — достаточно знать, что хэш-таблица представляет собой быстрый "словарь" (`Dictionary`), который является очень полезным инструментом.Примечание ③: При планировании использования RMI (подробно рассматривается в главе 15), следует помнить, что может возникнуть проблема с помещением удалённых объектов в хэш-таблицу (см. "Core Java", авторы Cornell и Horstmann, Prentice-Hall, 1997).Примечание ④: Если даже такой значительный прирост скорости всё ещё недостаточен для удовлетворения ваших требований к производительности, вы можете написать свой собственный алгоритм хэш-таблицы, что позволит ещё больше ускорить процесс поиска. Это поможет избежать временных затрат на преобразование между `Object` и также минимизирует влияние встроенной синхронизации в реализациях хэш-таблиц стандартной библиотеки Java.

Примечание ⑤: Лучшим источником информации являются "Practical Algorithms for Programmers", авторы Andrew Binstock и John Rex, издательство Addison-Wesley, 1995 год.

Как пример применения хэш-таблицы, можно рассмотреть программу, проверяющую случайность метода `Math.random()` в Java. В идеальном случае он должен генерировать последовательность абсолютно случайных чисел. Однако для проверки этой случайности нам потребуется создать множество случайных чисел и затем подсчитать количество чисел, попавших в различные диапазоны. Хэш-таблица может существенно упростить эту задачу, поскольку она связывает объекты друг с другом (в данном случае связывает значения, сгенерированные `Math.random()`, с количеством их появлений). Пример представлен ниже:

```java
//: Statistics.java
// Простой демонстрационный пример использования Hashtable
import java.util.*;

class Counter {
  int i = 1;
  public String toString() {
    return Integer.toString(i);
  }
}
``````java
class Statistics {
  public static void main(String[] args) {
    Hashtable ht = new Hashtable();
    for (int i = 0; i < 10000; i++) {
      // Генерируем число от 0 до 20:
      Integer r = 
          new Integer((int)(Math.random() * 20));
      if (ht.containsKey(r)) 
          ((Counter)ht.get(r)).i++;
      else 
          ht.put(r, new Counter());
    }
    System.out.println(ht);
  }
}
```
///:

В методе `main()`, каждый раз когда генерируется случайное число, оно оборачивается в объект типа `Integer`, чтобы использовать его как ссылку вместе с хэш-таблицей (нельзя использовать базовый тип данных для коллекций, можно использовать только ссылки на объекты). Метод `containsKey()` проверяет, содержится ли этот ключ уже в коллекции (то есть, было ли это число найдено ранее?). Если ключ уже существует, то метод `get()` получает значение, связанное с этим ключом, которое является объектом типа `Counter`. Затем увеличивается значение поля `i` этого объекта `Counter` на единицу, что указывает на повторное появление данного случайного числа.

Если ключ еще не был найден, метод `put()` все равно помещает новую пару "ключ-значение" в хэш-таблицу. При создании нового объекта `Counter`, поле `i` автоматически инициализируется значением 1, что указывает на первое появление данного случайного числа.Для вывода содержимого хэш-таблицы достаточно просто вывести её. Метод `toString()` хэш-таблицы проходит через все пары "ключ-значение" и вызывает метод `toString()` для каждой пары. Метод `toString()` для типа `Integer` заранее определён, поэтому используется реализация `toString()` для объекта `Counter`. Результат одного запуска программы (с добавленными переносами строки) может выглядеть следующим образом:```
{19=526, 18=533, 17=460, 16=513, 15=521, 14=495,
 13=512, 12=483, 11=488, 10=487, 9=514, 8=523,
 7=497, 6=487, 5=480, 4=489, 3=509, 2=503, 1=475,
 0=505}
```

Некоторые могут сомневаться в необходимости класса `Counter`, так как он кажется не предоставляющим никаких преимуществ перед примитивным типом `int` или его упакованной версией `Integer`. Почему бы просто не использовать `int` или `Integer`? На самом деле, поскольку все коллекции могут содержать только объекты-ссылки, использование примитивных типов данных, таких как целое число (`int`), невозможно. После изучения коллекций концепция упакованных классов становится более понятной, так как любые базовые данные не могут быть помещены непосредственно в коллекцию.

Однако единственное, что мы можем сделать с упаковщиками Java, это создать их со значением по умолчанию и затем считывать это значение. То есть, после создания объекта-упаковщика нет способа изменить его значение. Это делает упаковщик `Integer` бесполезным для решения нашей задачи, поэтому нам пришлось создать новый класс, чтобы удовлетворить наши требования. Создание «ключевого» классаВ предыдущих примерах мы использовали стандартный класс библиотеки (`Integer`) в качестве ключа для `Hashtable`. Этот подход хорошо работает, так как этот класс уже имеет всё необходимое для корректной работы. Однако при создании своего класса для использования его в качестве ключа в `Hashtable`, возникают некоторые проблемы. Например, представьте систему прогнозирования погоды, которая связывает объекты типа `Groundhog` с объектами типа `Prediction`. Это может выглядеть логичным: создаём два класса и используем `Groundhog` в качестве ключа, а `Prediction` — в качестве значения. Пример кода:```java
//: SpringDetector.java
// Appears plausible, but does not work correctly.
import java.util.*;

class Groundhog {
  int ghNumber;
  Groundhog(int n) { ghNumber = n; }
}

class Prediction {
  boolean shadow = Math.random() > 0.5;
  public String toString() {
    if(shadow)
      return "Еще шесть недель зимы!";
    else
      return "Ранняя весна!";
  }
}

public class SpringDetector {
  public static void main(String[] args) {
    Hashtable ht = new Hashtable();
    for(int i = 0; i < 10; i++)
      ht.put(new Groundhog(i), new Prediction());
    System.out.println("ht = " + ht + "\n");
    System.out.println(
      "Поиск прогноза для Groundhog номер 3:");
    Groundhog gh = new Groundhog(3);
    if(ht.containsKey(gh))
      System.out.println((Prediction)ht.get(gh));
  }
} ///:~
```

Каждый объект `Groundhog` имеет уникальный номер, поэтому можно было бы использовать этот номер для поиска связанного с ним `Prediction`. Класс `Prediction` содержит логическое значение, которое инициализируется методом `Math.random()`, а также метод `toString()` для вывода результата. В методе `main()` создаются объекты `Groundhog` и связанные с ними `Prediction`, которые затем помещаются в `Hashtable`. Эта таблица печатается, чтобы показать, что она была заполнена. Затем производится поиск прогноза для объекта `Groundhog` с номером 3.Это выглядит простым решением, но на самом деле это не работает. Проблема заключается в том, что класс `Groundhog` наследуется от общего базового класса `Object` (если не указано иное, то все классы конечного времени наследуются от `Object`). На самом деле, каждый объект получает свой хэш-код через метод `hashCode()` класса `Object`, который по умолчанию использует адрес объекта. Поэтому первый экземпляр `Groundhog(3)` не будет иметь тот же хэш-код, что и второй экземпляр `Groundhog(3)`, и поиск второго экземпляра не приведёт к успешному результату. Может показаться, что единственной задачей в данной ситуации является правильная реализация метода `hashCode()`. Однако этого недостаточно, если не будет выполнено ещё одно условие: переопределение метода `equals()`, который также является частью класса `Object`. Этот метод используется, когда таблица рассеивания пытается определить, равен ли наш ключ какому-либо ключу внутри таблицы. По умолчанию метод `Object.equals()` просто сравнивает адреса объектов, поэтому один экземпляр `Groundhog(3)` не будет считаться равным другому экземпляру `Groundhog(3)`.Поэтому, чтобы использовать свой класс в качестве ключа в таблице рассеивания, необходимо переопределить как `hashCode()`, так и `equals()`, как это показано ниже:

```java
//: SpringDetector2.java
// Если вы создаете класс, используемый в качестве ключа в
// Hashtable, вам следует переопределить методы hashCode()
// и equals().
import java.util.*;

class Groundhog2 {
  int ghNumber;
  Groundhog2(int n) { ghNumber = n; }
  public int hashCode() { return ghNumber; }
  public boolean equals(Object o) {
    return (o instanceof Groundhog2)
      && (ghNumber == ((Groundhog2)o).ghNumber);
  }
}

public class SpringDetector2 {
  public static void main(String[] args) {
    Hashtable ht = new Hashtable();
    for(int i = 0; i < 10; i++)
      ht.put(new Groundhog2(i),new Prediction());
    System.out.println("ht = " + ht + "\n");
    System.out.println(
      "Ищем прогноз для зверька с номером 3:");
    Groundhog2 gh = new Groundhog2(3);
    if(ht.containsKey(gh))
      System.out.println((Prediction)ht.get(gh));
  }
} ///:~
```

Обратите внимание, что этот код использует класс `Prediction` из предыдущего примера, поэтому `SpringDetector.java` должен быть скомпилирован первым, иначе при попытке компиляции `SpringDetector2.java` возникнет ошибка компиляции.

Метод `Groundhog2.hashCode()` возвращает номер зверька как уникальный идентификатор (в данном случае программист должен гарантировать, что два зверька не имеют одного и того же номера одновременно). Для получения уникального идентификатора метод `hashCode()` не обязательно должен быть уникален, но метод `equals()` должен строго проверять равенство двух объектов.Метод `equals()` выполняет две проверки: проверяет, является ли объект `null`; если нет, то продолжает проверять, является ли он экземпляром класса `Groundhog2` (используется ключевое слово `instanceof`, подробнее об этом в главе 11). Даже если объект является экземпляром `Groundhog2`, сравнение основывается на фактическом значении `ghNumber`. В этот раз, когда мы запустим программу, она наконец выведет правильный результат (многие классы библиотек Java переопределяют методы `hashCode()` и `equals()` для обеспечения корректной работы со своими данными).

### Атрибуты: тип `Hashtable`

В первом примере этой книги мы использовали тип `Hashtable`, названный `Properties` (атрибуты). В этом примере следующие строки программы:

```java
Properties p = System.getProperties();
p.list(System.out);
```

вызывают статический метод `getProperties()`, который возвращает специальный объект `Properties`, описывающий некоторые характеристики системы. Метод `list()` является частью класса `Properties` и позволяет выводить содержимое в любой поток вывода, выбранный нами. Также существует метод `save()`, с помощью которого можно записывать список атрибутов в файл для последующего чтения с помощью метода `load()`.

Хотя класс `Properties` наследуется от `Hashtable`, он также содержит внутреннюю хэш-таблицу для хранения списка "по умолчанию" атрибутов. Таким образом, если атрибут не найден в основной таблице, будет автоматически выполнен поиск среди атрибутов по умолчанию.Класс `Properties` также может использоваться в наших программах (например, в файле `ClassScanner.java` главы 17). Дополнительные и более подробные объяснения можно найти в документации Java библиотек.

#### 8.4.5 Ещё раз о перечислителях

Теперь мы можем продемонстрировать истинную мощь перечислителей: разделение операций над последовательностью данных от её базовой структуры. В следующем примере класс `PrintData` использует перечислитель для перемещения по последовательности и вызова метода `toString()` для каждого объекта. В данном случае создаются две различных коллекции типа: `Vector` и `Hashtable`. Они заполняются объектами `Mouse` и `Hamster` соответственно (классы были определены ранее в этой главе; обратите внимание, что необходимо скомпилировать `HamsterMaze.java` и `WorksAnyway.java`, чтобы данный пример компилировался). Поскольку перечислитель скрывает базовую структуру коллекций, то `PrintData` не знает или не заботится о том, какой именно тип коллекции используется:

```java
//: Enumerators2.java
// Обзор перечислителей
import java.util.*;

class PrintData {
  static void print(Enumeration e) {
    while(e.hasMoreElements())
      System.out.println(
        e.nextElement().toString());
  }
}

class Enumerators2 {
  public static void main(String[] args) {
    Vector v = new Vector();
    for(int i = 0; i < 5; i++)
      v.addElement(new Mouse(i));

    Hashtable h = new Hashtable();
    for(int i = 0; i < 5; i++)
      h.put(new Integer(i), new Hamster(i));
```    System.out.println("Vector");
    PrintData.print(v.elements());
    System.out.println("Hashtable");
    PrintData.print(h.elements());
  }
} ///:~

Обратите внимание, что `PrintData.print()` использует тот факт, что объекты в этих коллекциях являются экземплярами класса `Object`, поэтому вызывается метод `toString()`. Однако при решении своих собственных задач часто требуется гарантировать, что ваша `Enumeration` проходит через некоторый конкретный тип коллекции. Например, может потребоваться, чтобы все элементы коллекции были объектами типа `Shape` с методом `draw()`. В этом случае вам необходимо выполнить приведение типа из возвращаемого объекта `Object` методом `Enumeration.nextElement()`, чтобы получить объект типа `Shape`.