Хеш-множества в Java

Предположим, что вы решили сделать этот класс сериализуемым. Поскольку физическое представление объекта Period в точности отражает его логическое содержание, вполне можно воспользоваться сериализованной формой по умолчанию. Может показаться, что все, что вам нужно для того, чтобы сделать класс сериализуемым, — это добавить в его объявление слова implements Serializable. Однако если вы поступите таким образом, то класс больше не сможет гарантировать свои критически важные инварианты.

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

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

Предположим, что мы просто добавили implements Serializable в объявление класса Period. Приведенная далее уродливая программа генерирует такой экземпляр класса Period, в котором конец интервала предшествует его началу. Приведения значений типа byte с установленным старшим битом являются следствием отсутствия в Java литералов byte в сочетании с достойным сожаления решением сделать тип byte знаковым:

Если вы определяете собственные классы, то на вас ложится ответственность за самостоятельную реализацию метода hashCode (). Ваша реализация данного метода должна быть совместима с методом equals (). Так, если в результате вызова a. equals (b) возвращается логическое значение true, то объекты а и b должны иметь одинаковые хеш-коды. Но самое главное, чтобы хеш-ко­ды вычислялись быстро, а вычисление зависело только от состояния хешируемого объекта, а не от других объектов в хеш-таблице.

В языке Java хеш-таблицы реализованы в виде массивов связных списков, каждый из которых называется группой (рис. 9.10). Чтобы найти место объекта в таблице, вычисляется его хеш-код и уменьшается его модуль до общего количества групп. Полученное в итоге числовое значение и будет индексом группы, содержащей искомый элемент. Так, если хеш-код объекта равен 7 62 68, а всего имеется 128 групп, объект должен быть размещен в группе под номером 108 (поскольку остаток от целочисленного деления 76268 на 128 равен 108). Если повезет, то в этой группе не окажется других элементов и элемент просто вводится в группу. Безусловно, рано или поздно встретится непустая группа. Такое явление называется хеш-конфликтом. В таком случае новый объект сравнивается со всеми объектами в группе, чтобы проверить, находится ли он уже в группе. Если учесть сравнительно равномерное распределение хеш-кодов при достаточно большом количестве групп, то в конечном итоге потребуется лишь несколько сравнений.

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

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

Если приблизительно известно, сколько элементов в конечном итоге окажется в хеш-таблице, можно установить количество групп. Обычно это количество устанавливается в пределах от 75 до 150% от ожидаемого числа элементов. Некоторые исследователи полагают, что количество групп должно быть выражено простым числом, чтобы предотвратить группирование ключей. Но на этот счет нет общего мнения. В стандартной библиотеке используются количества групп, выражаемые числом, являющимся степенью 2, по умолчанию — 16. (Любое указываемое значение размеров хеш-таблицы автоматически округляется до следующей степени 2.)

Безусловно, далеко не всегда известно, сколько элементов придется хранить в хеш-таблице, а кроме того, первоначально предполагаемое их количество может оказаться заниженным. Если хеш-таблица становится чрезмерно заполненной, ее следует хешировать повторно. Для повторного хеширования создается новая хеш-табли­ца с большим количеством групп, все элементы старой таблицы вводятся в новую, а старая хеш-таблица отвергается. Коэффициент загрузки определяет момент повторного хеширования хеш-таблицы. Так, если коэффициент загрузки равен 0.7 5 (по умолчанию), а хеш-таблица заполнена более чем на 75%, она автоматически хешируется повторно с увеличенным вдвое количеством групп. Для большинства приложений целесообразно оставить коэффициент загрузки равным 0.75.

Хеш-таблицы можно использовать для реализации ряда важных структур данных. Простейшая из них относится к типу множества. Множество — это совокупность элементов, не содержащая дубликатов. Так, метод add () сначала пытается найти вводимый объект и вводит его только в том случае, если он отсутствует в множестве.

В библиотеке коллекций Java предоставляется класс HashSet, реализующий множество на основе хеш-таблицы. Элементы вводятся в такое множество методом add (). А метод contains () переопределяется, чтобы осуществлять быстрый поиск элементов в множестве. Он проверяет элементы только одной группы, а не все элементы коллекции.

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

В примере программы из листинга 9.2 отдельные слова текста вводятся из стандартного потока System, in в хеш-множество, а затем выводятся из него. Например, данной программе можно направить англоязычный текст книги «Алиса в стране чудес» (доступный по адресу www.gutenberg.net , запустив ее из командной строки следующим образом:
java SetTest < alice30.txt

Программа введет все слова из стандартного потока ввода в хеш-множество, а затем переберет все неповторяющиеся слова в хеш-множестве и выведет их количество. Так, текст книги «Алиса в стране чудес» содержит 5909 неповторяющихся слов, включая уведомление об авторском праве в самом начале. Слова извлекаются из хеш-множества в случайном порядке.

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

Программная часть – это конечно же хорошо, но без аппаратной – никуда не дется. На финальной стадии реализации вашего проекта вам потребуется сервер, и оптимальный вариант – это конечно же аренда vds сервера. Минимальный тарифный план составляет всего 169 рублей в месяц, и в зависимости от нагрузки и поставленных задач — вы сможете легко его расширить, получив в своё распоряжение больше ядер, памяти, и кончено же дискового пространства под свои нужды на SSD.