HashSet в Java
Класс HashSet реализует интерфейс Set , основан на хэш-таблице, а также поддерживается с помощью экземпляра HashMap . В HashSet элементы не упорядочены, нет никаких гарантий, что элементы будут в том же порядке спустя какое-то время. Операции добавления, удаления и поиска будут выполняться за константное время при условии, что хэш-функция правильно распределяет элементы по «корзинам», о чем будет рассказано далее. Несколько важных пунктов о HashSet :
- Т.к. класс реализует интерфейс Set , он может хранить только уникальные значения;
- Может хранить NULL – значения;
- Порядок добавления элементов вычисляется с помощью хэш-кода;
- HashSet также реализует интерфейсы Serializable и Cloneable .
Для поддержания постоянного времени выполнения операций время, затрачиваемое на действия с HashSet , должно быть прямо пропорционально количеству элементов в HashSet + «емкость» встроенного экземпляра HashMap (количество «корзин»). Поэтому для поддержания производительности очень важно не устанавливать слишком высокую начальную ёмкость (или слишком низкий коэффициент загрузки). Начальная емкость – изначальное количество ячеек («корзин») в хэш-таблице. Если все ячейки будут заполнены, их количество увеличится автоматически. Коэффициент загрузки – показатель того, насколько заполненным может быть HashSet до того момента, когда его емкость автоматически увеличится. Когда количество элементов в HashSet становится больше, чем произведение начальной емкости и коэффициента загрузки, хэш-таблица ре-хэшируется (заново вычисляются хэшкоды элементов, и таблица перестраивается согласно полученным значениям) и количество ячеек в ней увеличивается в 2 раза. Коэффициент загрузки = Количество хранимых элементов в таблице / размер хэш-таблицы Например, если изначальное количество ячеек в таблице равно 16, и коэффициент загрузки равен 0,75, то из этого следует, что когда количество заполненных ячеек достигнет 12, их количество автоматически увеличится. Коэффициент загрузки и начальная емкость – два главных фактора, от которых зависит производительность операций с HashSet . Коэффициент загрузки, равный 0,75, в среднем обеспечивает хорошую производительность. Если этот параметр увеличить, тогда уменьшится нагрузка на память (так как это уменьшит количество операций ре-хэширования и перестраивания), но это повлияет на операции добавления и поиска. Чтобы минимизировать время, затрачиваемое на ре-хэширование, нужно правильно подобрать параметр начальной емкости. Если начальная емкость больше, чем максимальное количество элементов, поделенное на коэффициент загрузки, то никакой операции ре-хэширования не произойдет в принципе. Важно : HashSet не является структурой данных с встроенной синхронизацией, поэтому если с ним работают одновременно несколько потоков, и как минимум один из них пытается внести изменения, необходимо обеспечить синхронизированный доступ извне. Часто это делается за счет другого синхронизируемого объекта, инкапсулирующего HashSet . Если такого объекта нет, то лучше всего подойдет метод Collections.synchronizedSet() . На данный момент это лучшее средство для предотвращения несинхронизированных операций с HashSet .
Set s = Collections.synchronizedSet(new HashSet(. ));
- HashSet h = new HashSet(); — конструктор по умолчанию. Начальная емкость по умолчанию – 16, коэффициент загрузки – 0,75.
- HashSet h = new HashSet(int initialCapacity) – конструктор с заданной начальной емкостью. Коэффициент загрузки – 0,75.
- HashSet h = new HashSet(int initialCapacity, float loadFactor); — конструктор с заданными начальной емкостью и коэффициентом загрузки.
- HashSet h = new HashSet(Collection C) – конструктор, добавляющий элементы из другой коллекции.
import java.util.*; class Test < public static void main(String[]args) < HashSeth = new HashSet(); // Добавляем элементы в HashSet с помощью метода add() h.add("India"); h.add("Australia"); h.add("South Africa"); h.add("India");// пытаемся добавить еще один такой же элемент // Выводим элементы HashSet в консоль System.out.println(h); System.out.println("List contains India or not:" + h.contains("India")); // Удаляем элементы из множества с помощью метода remove() h.remove("Australia"); System.out.println("List after removing Australia:"+h); // Проходимся по элементам HashSet с помощью итератора: System.out.println("Iterating over list:"); Iterator i = h.iterator(); while (i.hasNext()) System.out.println(i.next()); > >
Вывод:
[South Africa, Australia, India] List contains India or not:true List after removing Australia:[South Africa, India] Iterating over list: South Africa India
Все классы, реализующие интерфейс Set , внутренне поддерживаются реализациями Map . HashSet хранит элементы с помощью HashMap . Хоть и для добавления элемента в HashMap он должен быть представлен в виде пары «ключ-значение», в HashSet добавляется только значение. На самом деле значение, которые мы передаем в HashSet , является ключом к объекту HashMap , а в качестве значения в HashMap используется константа. Таким образом, в каждой паре «ключ-значение» все ключи будут иметь одинаковые значения. Реализация HashSet в java doc :
private transient HashMap map; // Конструктор - 1 // Все конструкторы неявно создают объект HashMap. public HashSet() < // Создаем неявно объект HashMap map = new HashMap(); >// Конструктор- 2 public HashSet(int initialCapacity) < // Создаем неявно объект HashMap map = new HashMap(initialCapacity); >// Объект класса Object, каждый раз выступающий в роли значения в HashMap private static final Object PRESENT = new Object();
Если взглянуть на метод add() у HashSet :
public boolean add(E e)
Можно заметить, что метод add() у HashSet вызывает метод put() у внутреннего объекта HashMap , передавая ему в качестве ключа добавляемый элемент, а в качестве значения – константу PRESENT. Сходным образом работает и метод remove() . В нем вызывается метод remove() внутреннего объекта HashMap :
public boolean remove(Object o)
- boolean add(E e) : добавляет элемент в HashSet , если таковой отсутствует, если же такой элемент уже присутствует, метод возвращает false.
- void clear(): удаляет все элементы из множества.
- boolean contains(Object o) : Возвращает true, если данный элемент присутствует в множестве.
- boolean remove(Object o) : удаляет данный элемент из множества, если таковой присутствует.
- Iterator iterator() : возвращает итератор для элементов множества.
- boolean isEmpty() : возвращает true, если в множестве нет элементов.
- Object clone() : выполняет поверхностное клонирование HashSet .
Как работает hashset в java
HashSet в Java — это реализация интерфейса Set , который использует хэш-таблицы для хранения элементов коллекции. HashSet не гарантирует порядок элементов при их переборе, и не допускает хранение дублирующихся элементов.
Основные операции, которые можно выполнить с HashSet :
- добавление элемента: add()
- удаление элемента: remove()
- проверка наличия элемента: contains()
- очистка коллекции: clear()
- получение размера коллекции: size()
HashSet реализован как хэш-таблица , где элементы хранятся в виде ключей, а значения не используются.
- При добавлении элемента, HashSet рассчитывает его хэш-код и добавляет в таблицу с соответствующим индексом.
- Если в таблице уже есть элемент с таким же хэш-кодом , то выполняется проверка на равенство.
- Если элементы равны, то новый элемент не добавляется в коллекцию, иначе он добавляется в таблицу.
При работе с HashSet важно правильно определить методы hashCode() и equals() для класса, который будет храниться в коллекции. Это позволит корректно выполнять поиск и удаление элементов. Если класс не переопределит методы hashCode() и equals() , то будут использоваться реализации по умолчанию, которые могут не давать ожидаемых результатов при работе с HashSet
Hashset java как работает
Интерфейс Set расширяет интерфейс Collection и представляет набор уникальных элементов. Set не добавляет новых методов, только вносит изменения в унаследованные. В частности, метод add() добавляет элемент в коллекцию и возвращает true, если в коллекции еще нет такого элемента.
Обобщенный класс HashSet представляет хеш-таблицу. Он наследует свой функционал от класса AbstractSet , а также реализует интерфейс Set .
Хеш-таблица представляет такую структуру данных, в которой все объекты имеют уникальный ключ или хеш-код. Данный ключ позволяет уникально идентифицировать объект в таблице.
Для создания объекта HashSet можно воспользоваться одним из следующих конструкторов:
- HashSet() : создает пустой список
- HashSet(Collection col) : создает хеш-таблицу, в которую добавляет все элементы коллекции col
- HashSet(int capacity) : параметр capacity указывает начальную емкость таблицы, которая по умолчанию равна 16
- HashSet(int capacity, float koef) : параметр koef или коэффициент заполнения, значение которого должно быть в пределах от 0.0 до 1.0, указывает, насколько должна быть заполнена емкость объектами прежде чем произойдет ее расширение. Например, коэффициент 0.75 указывает, что при заполнении емкости на 3/4 произойдет ее расширение.
Класс HashSet не добавляет новых методов, реализуя лишь те, что объявлены в родительских классах и применяемых интерфейсах:
import java.util.HashSet; public class Program < public static void main(String[] args) < HashSetstates = new HashSet(); // добавим в список ряд элементов states.add("Germany"); states.add("France"); states.add("Italy"); // пытаемся добавить элемент, который уже есть в коллекции boolean isAdded = states.add("Germany"); System.out.println(isAdded); // false System.out.printf("Set contains %d elements \n", states.size()); // 3 for(String state : states) < System.out.println(state); >// удаление элемента states.remove("Germany"); // хеш-таблица объектов Person HashSet people = new HashSet(); people.add(new Person("Mike")); people.add(new Person("Tom")); people.add(new Person("Nick")); for(Person p : people) < System.out.println(p.getName()); >> > class Person < private String name; public Person(String value)< name=value; >String getName() >
HashMap и HashSet. Что это на самом деле?
В данном уроке, я попробую копнуть в теме коллекций и рассказать о двух реализациях построенных на хэш коде.
Шаг 0. Введение
В практике, мы редко оперируем одним элементом, так как большинство задач нужно решать комплексно. Именно по этому, мы всегда берем какое-то множество объектов чтобы оперировать ими. Но вот только вопрос? Что именно и когда стоит выбирать? Есть много реализаций коллекций, есть массивы. Почему стоит выбрать одно, а не другое? Думаю это стоит знать. Тем более, это один из самых популярных вопросов на собеседовании.
Шаг 1. Что такое хэш-код?
Хэш-код – это целое число, которое является уникальным идентификатором содержимого объекта. От сюда вывод – в каждого объекта, с разными данными, свое уникальное число, с помощью которого мы можем судить о равенстве или неравенстве. В яве, за вычисление этого кода отвечает метод hashCode(), который переопределенный в наследниках Object. Для наших классов мы также должны переопределить его.
Есть несколько правил по переопределению данного метода:
1. Это не должна быть константа. Иначе все будет равным, даже если это не так.
2. Метод генерации должен быть хорошо продуман, иначе могут часто попадаться ситуации коллизии.
3. В генерации желательно использовать именно те поля, которые идентифицируют объект, его уникальность.
Пример того как это все выглядит:
У нас есть 2 объекта с двумя полями. Поля одинаковые, значит их хэш-код должен совпадать и указывать на равенство. Создадим генерацию нашего кода на обычной сумме атрибутов:
1 + 2 = 1 + 2 – равенство верно.
Но что будет если у нас такие объекты:
Здесь поменялся только порядок значений для второго объекта. Эти объекты уже не могут быть равны, но…
1 + 2 = 2 + 1 – равенство осталось верно.
Это есть прямой пример коллизии. Два разных объекта имеют одинаковый хэш-код. В нашем случае, причиной этому есть плохо составленный алгоритм вычисления.
Можем сделать вывод:
Для одного и того ж объекта хэш-код всегда один(если не изменять вычисляемые поля)
Если хэш-коды равны, то это не значит что и объекты равны.
Если хэш-коды не равны, то значит и объекты не могут быть равны.
Рассмотрим теперь это на примере. Создадим 2 класса, переопределим вычисление хэш-кода и докажем наши выводы.
public class A < private int a; private int b; public A() < >@Override public int hashCode() < return a + b; >//getters & setters >
И методы main где мы сделаем простую проверку вышесказанного.
A o1 = new A(); A o2 = new A(); o1.setA(1); o1.setB(2); o2.setA(1); o2.setB(2); /* * Объекты одинаковые, ожидаем true * */ System.out.println(o1.hashCode() == o2.hashCode()); o2.setA(2); o2.setA(1); /* * Зесь мы иммем 2 объекта которые имеют разные значение, * то есть и объекты являются разными. Ожидаем false * Получаем коллизию, хэш код одинаковый * */ System.out.println(o1.hashCode() == o2.hashCode()); /* * Объект имеет всегда один хэш-код. Равен сам себе * */ System.out.println(o1.hashCode() == o1.hashCode()); o2.setA(25); o2.setB(100); /* * Пример того, что разные хэш-кода, указывают на разные * объекты. * */ System.out.println("o1="+o1.hashCode() + " o2 async" gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-lazy-type="image" data-lazy-src="https://devcolibri.com/cp/wp-content/uploads/2014/04/4.png" alt="hashset java как работает" width="500" data-lazy-srcset="https://devcolibri.com/cp/wp-content/uploads/2014/04/4.png 693w, https://devcolibri.com/cp/wp-content/uploads/2014/04/4-600x298.png 600w, https://devcolibri.com/cp/wp-content/uploads/2014/04/4-300x148.png 300w" data-lazy-sizes="(max-width: 693px) 100vw, 693px" /> Мы просто сравниваем значимые атрибуты для определения равенства наших объектов. Запомните: изначально, в классе Object идет сравнивание по ссылке, что значит без переопределения данного метода, все ваши объекты будут считаться разными, если только их ссылки не указывают на один и тот же объект.
Используем для примера предыдущий класс и реализуем проверку эквивалентности.
A o1 = new A(); A o2 = new A(); o1.setA(1); o1.setB(2); o2.setA(1); o2.setB(2); /* * Проверка на эквивалентность. * Должно быть true * */ System.out.println(o1.equals(o2)); /* * Меняем значения местами, как с хэш-кодом * и проверяем. * */ o2.setA(2); o2.setB(1); System.out.println(o1.equals(o2));
Как вы заметили, эти два понятия тесно связаны и указывают на равенство объектов. Теперь, разобравшись с этим, перейдом непосредственно к коллекциям.
Шаг 3. Организация работы HashMap
– это число, как мы говорили выше.
– коллекция которая состоит с пар “ключ”-“значение”.
HashMap – внутри состоит с так званых корзин и списка элементов, на которые ссылаются корзины.
Корзины – массив
Элементы – связной список. (это рассмотрим дальше)
Добавление
Когда приходит новый элемент, хэш-код ключа определяет корзину, для элемента. В корзине идет проверка, есть ли у нее элементы. Если нету, то корзина получает ссылку нового элемента, если есть, то происходит прохождение по списку элементов и сравнивание элементов в списке. Проверяется равенство hashcode. Так как мы не можем однозначно судить на счет эквивалентности, зная о случаях коллизии, проводится еще сравнивание ключей методом equals.
Если оба равны: идет перезапись
Если не равен equals: добавляется элемент в список
По этому:
1. Если у нас плохой алгоритм расчета хэш-кода, то мы получим обычный связной список и потеряем все преимущества данной структуры. (Добавление, поиск и удаление элементов выполняется за константное время)
2. Важно переопределять метод hashCode & equals для корректной работы.
Получение
Получение объекта происходит по тому же принципу. Приходит ключ, берется его хэш-код и вычисляется номер корзины, потом, с этой корзины, проходя по списку элементов, находится наш и возвращается ссылка на него.
Предостережение!
Не используйте в качестве ключа массивы. Их хэш код зависит от ссылки. Если даже будете использовать массив с такими ж данными, чтобы получить свое значение, ссылка будет другая и вы не получите свой объект.
Шаг 4. Организация работы HashSet
Почему мы сразу рассмотрели HashMap? Это поможет с пониманием работы следующей коллекции. Здесь все происходит также, единственное отличие здесь в том, что ключом является сам объект.
Предостережение!
Будьте аккуратны в работе с объектом. Если вы поменяете вычисляемые поля объекта, то вы можете навеки потерять его в коллекции.