Что такое hashset в java
Перейти к содержимому

Что такое hashset в java

  • автор:

31.10. Java – Класс HashSet

Класс HashSet в Java расширяет AbstractSet и реализует интерфейс Set. Он создает коллекцию, которая использует хеш-таблицу для хранения.

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

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

Конструкторы

Ниже приведен список конструкторов, предоставляемых классом HashSet.

Конструктор и описание
1 HashSet( )
Этот конструктор создает стандартный HashSet.
2 HashSet(Collection c)
Этот конструктор инициализирует хэш-набор, используя элементы коллекции c.
3 HashSet(int capacity)
Этот конструктор инициализирует емкость хэш-набора для заданной целочисленной емкости. Емкость растет автоматически по мере добавления элементов в HashSet.
4 HashSet(int capacity, float fillRatio)
Этот конструктор инициализирует как емкость, так и коэффициент заполнения (также называемый нагрузочной способностью) хэш-набора из его аргументов.
При этом отношение заполнения должно находиться в диапазоне от 0,0 до 1,0, и это определяет, как полный набор хэша, прежде чем его размер будет увеличен. В частности, когда количество элементов больше, чем емкость хеш-множества, умноженная на его коэффициент заполнения, хэш-набор расширяется.

Методы

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

и описание
1 boolean add(Object o)
Добавляет указанный элемент к этому набору, если он еще не присутствует.
2 void clear()
Удаляет все элементы из этого набора.
3 Object clone()
Возвращает мелкую копию этого экземпляра HashSet: сами элементы не клонируются.
4 boolean contains(Object o)
Возвращает true, если этот набор содержит указанный элемент.
5 boolean isEmpty()
Возвращает true, если этот набор не содержит элементов.
6 Iterator iterator()
Возвращает итератор по элементам этого набора.
7 boolean remove(Object o)
Удаляет указанный элемент из этого набора, если он присутствует.
8 int size()
Возвращает количество элементов в этом наборе (его количество элементов).

Пример

Следующая программа демонстрирует работу нескольких методов, поддерживаемых HashSet в Java:

import java.util.*; public class HashSetDemo < public static void main(String args[]) < // Создаём HashSet HashSet hs = new HashSet(); // Добавляем элементы к HashSet hs.add("B"); hs.add("A"); hs.add("D"); hs.add("E"); hs.add("C"); hs.add("F"); System.out.println(hs); >> 

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

[A, B, C, D, E, F] 

Оглавление

  • 1. Java – Самоучитель для начинающих
  • 2. Java – Обзор языка
  • 3. Java – Установка и настройка
  • 4. Java – Синтаксис
  • 5. Java – Классы и объекты
  • 6. Java – Конструкторы
  • 7. Java – Типы данных и литералы
  • 8. Java – Типы переменных
  • 9. Java – Модификаторы
  • 10. Java – Операторы
  • 11. Java – Циклы и операторы цикла
  • 11.1. Java – Цикл while
  • 11.2. Java – Цикл for
  • 11.3. Java – Улучшенный цикл for
  • 11.4. Java – Цикл do..while
  • 11.5. Java – Оператор break
  • 11.6. Java – Оператор continue
  • 12. Java – Операторы принятия решений
  • 12.1. Java – Оператор if
  • 12.2. Java – Оператор if..else
  • 12.3. Java – Вложенный оператор if
  • 12.4. Java – Оператор switch..case
  • 12.5. Java – Условный оператор (? 🙂
  • 13. Java – Числа
  • 13.1. Java – Методы byteValue(), shortValue(), intValue(), longValue(), floatValue(), doubleValue()
  • 13.2. Java – Метод compareTo()
  • 13.3. Java – Метод equals()
  • 13.4. Java – Метод valueOf()
  • 13.5. Java – Метод toString()
  • 13.6. Java – Метод parseInt()
  • 13.7. Java – Метод Math.abs()
  • 13.8. Java – Метод Math.ceil()
  • 13.9. Java – Метод Math.floor()
  • 13.10. Java – Метод Math.rint()
  • 13.11. Java – Метод Math.round()
  • 13.12. Java – Метод Math.min()
  • 13.13. Java – Метод Math.max()
  • 13.14. Java – Метод Math.exp()
  • 13.15. Java – Метод Math.log()
  • 13.16. Java – Метод Math.pow()
  • 13.17. Java – Метод Math.sqrt()
  • 13.18. Java – Метод Math.sin()
  • 13.19. Java – Метод Math.cos()
  • 13.20. Java – Метод Math.tan()
  • 13.21. Java – Метод Math.asin()
  • 13.22. Java – Метод Math.acos()
  • 13.23. Java – Метод Math.atan()
  • 13.24. Java – Метод Math.atan2()
  • 13.25. Java – Метод Math.toDegrees()
  • 13.26. Java – Метод Math.toRadians()
  • 13.27. Java – Метод Math.random()
  • 14. Java – Символы
  • 14.1. Java – Метод Character.isLetter()
  • 14.2. Java – Метод Character.isDigit()
  • 14.3. Java – Метод Character.isWhitespace()
  • 14.4. Java – Метод Character.isUpperCase()
  • 14.5. Java – Метод Character.isLowerCase()
  • 14.6. Java – Метод Character.toUpperCase()
  • 14.7. Java – Метод Character.toLowerCase()
  • 14.8. Java – Метод Character.toString()
  • 15. Java – Строки
  • 15.1. Java – Метод charAt()
  • 15.2. Java – Метод compareTo()
  • 15.3. Java – Метод compareToIgnoreCase()
  • 15.4. Java – Метод concat()
  • 15.5. Java – Метод contentEquals()
  • 15.6. Java – Метод copyValueOf()
  • 15.7. Java – Метод endsWith()
  • 15.8. Java – Метод equals()
  • 15.9. Java – Метод equalsIgnoreCase()
  • 15.10. Java – Метод getBytes()
  • 15.11. Java – Метод getChars()
  • 15.12. Java – Метод hashCode()
  • 15.13. Java – Метод indexOf()
  • 15.14. Java – Метод intern()
  • 15.15. Java – Метод lastIndexOf()
  • 15.16. Java – Метод length()
  • 15.17. Java – Метод matches()
  • 15.18. Java – Метод regionMatches()
  • 15.19. Java – Метод replace()
  • 15.20. Java – Метод replaceAll()
  • 15.21. Java – Метод replaceFirst()
  • 15.22. Java – Метод split()
  • 15.23. Java – Метод startsWith()
  • 15.24. Java – Метод subSequence()
  • 15.25. Java – Метод substring()
  • 15.26. Java – Метод toCharArray()
  • 15.27. Java – Метод toLowerCase()
  • 15.28. Java – Метод toString()
  • 15.29. Java – Метод toUpperCase()
  • 15.30. Java – Метод trim()
  • 15.31. Java – Метод valueOf()
  • 15.32. Java – Классы StringBuilder и StringBuffer
  • 15.32.1. Java – Метод append()
  • 15.32.2. Java – Метод reverse()
  • 15.32.3. Java – Метод delete()
  • 15.32.4. Java – Метод insert()
  • 15.32.5. Java – Метод replace()
  • 16. Java – Массивы
  • 17. Java – Дата и время
  • 18. Java – Регулярные выражения
  • 19. Java – Методы
  • 20. Java – Потоки ввода/вывода, файлы и каталоги
  • 20.1. Java – Класс ByteArrayInputStream
  • 20.2. Java – Класс DataInputStream
  • 20.3. Java – Класс ByteArrayOutputStream
  • 20.4. Java – Класс DataOutputStream
  • 20.5. Java – Класс File
  • 20.6. Java – Класс FileReader
  • 20.7. Java – Класс FileWriter
  • 21. Java – Исключения
  • 21.1. Java – Встроенные исключения
  • 22. Java – Вложенные и внутренние классы
  • 23. Java – Наследование
  • 24. Java – Переопределение
  • 25. Java – Полиморфизм
  • 26. Java – Абстракция
  • 27. Java – Инкапсуляция
  • 28. Java – Интерфейсы
  • 29. Java – Пакеты
  • 30. Java – Структуры данных
  • 30.1. Java – Интерфейс Enumeration
  • 30.2. Java – Класс BitSet
  • 30.3. Java – Класс Vector
  • 30.4. Java – Класс Stack
  • 30.5. Java – Класс Dictionary
  • 30.6. Java – Класс Hashtable
  • 30.7. Java – Класс Properties
  • 31. Java – Коллекции
  • 31.1. Java – Интерфейс Collection
  • 31.2. Java – Интерфейс List
  • 31.3. Java – Интерфейс Set
  • 31.4. Java – Интерфейс SortedSet
  • 31.5. Java – Интерфейс Map
  • 31.6. Java – Интерфейс Map.Entry
  • 31.7. Java – Интерфейс SortedMap
  • 31.8. Java – Класс LinkedList
  • 31.9. Java – Класс ArrayList
  • 31.10. Java – Класс HashSet
  • 31.11. Java – Класс LinkedHashSet
  • 31.12. Java – Класс TreeSet
  • 31.13. Java – Класс HashMap
  • 31.14. Java – Класс TreeMap
  • 31.15. Java – Класс WeakHashMap
  • 31.16. Java – Класс LinkedHashMap
  • 31.17. Java – Класс IdentityHashMap
  • 31.18. Java – Алгоритмы Collection
  • 31.19. Java – Iterator и ListIterator
  • 31.20. Java – Comparator
  • 32. Java – Дженерики
  • 33. Java – Сериализация
  • 34. Java – Сеть
  • 34.1. Java – Обработка URL
  • 35. Java – Отправка Email
  • 36. Java – Многопоточность
  • 36.1. Java – Синхронизация потоков
  • 36.2. Java – Межпоточная связь
  • 36.3. Java – Взаимная блокировка потоков
  • 36.4. Java – Управление потоками
  • 37. Java – Основы работы с апплетами
  • 38. Java – Javadoc

Для чего нужен hash-set

Структура данных hash-set (и вообще set) — это такая редкая структура, что присутствует не во всех стандартных библиотеках. В .NET Framework, например, она появилась только с версии 3.5. Однако в некоторых случаях hash-set может быть весьма полезен.

В этой статье я покажу, когда имеет смысл применять hash-set и чем за это придется заплатить.

Во-первых, что такое set. Это такая коллекция, элементы которой неупорядоченны и уникальны (т.е. присутствуют в коллекции не более одного раза). Set поддерживает базовые операции:

  • Добавить элемент.
  • Удалить элемент.
  • Проверить, существует ли элемент.
  • Перебрать все элементы.

Реализации set различаются только структурой данных, используемой для поиска — это может быть массив, список, дерево, hash-таблица или что угодно еще. На практике, чаще всего используется hash-таблица, поскольку дает максимальную производительность с приемлемыми накладными расходами.

Теперь рассмотрим пример. Допустим нам нужно реализовать группировку большого числа элементов по равенству списка тэгов, причем для тэгов определен ignore list — то есть, тэги, которые не должны участвовать в сравнении. Тэги, в данном случае, — это недлинные строки (в основном, слова). Предположим так же, что ignore list содержит порядка 100 тэгов.

На Ruby алгоритм выглядит следующим образом:

def group_elements(elements, ignore_list) groups = [] for element in elements assigned = false for group in groups #Если элемент принадлежит группе, он добавляется и возвращается true; #в противном случае, возвращается false. if group.accept(element, ignore_list) assigned = true break end end #Если элемент не принадлежит ни одной группе, #создаем новую группу для этого элемента. if !assigned groups  

Вот как реализован метод Group::accept():

class Group . def accept(element, ignore_list) for my_element in @elements if my_element.match(element) @elements  

И наконец, метод Element::match():

class Element . def match(element, ignore_list) #Фильтруем списки тэгов. my_tags_filtered = @tags.select < |tag| !ignore_list.include?(tag) >its_tags_filtered = element.tags.select < |tag| !ignore_list.include?(tag) >#Находим пересечение множеств. intersection = my_tags_filtered & its_tags_filtered #Множества совпадают если их пересечение не пустое и #его размер равен размеру большего из множеств. return intersection.length > 0 && intersection.length == [my_tags_filtered.length, its_tags_filtered.length].max end . end 

Здесь продемонстрирована реализация в лоб, где и сами списки тэгов, и ignore list — это обычные динамические массивы. То есть, операция ignore_list.include? имеет линейную сложность. Кроме того, вспомним, что тэги — это строки длиной в среднем 5-10 символов, а сравнение строк само по себе имеет линейную сложность. Учитывая, что группировка имеет сложность O(n 2 ), оптимизация базовых операций сравнения может дать существенный прирост в производительности.

Сделать реализацию более оптимальной помогает hash-set. Если реализовать ignore list при помощи него, мы получим два серьезных преимущества. Во-первых, мы избавимся от линейного поиска по списку, заменяя его поиском hash-ключа; во-вторых, мы избавимся от сравнения строк. Есть правда один нюанс — в Ruby нет структуры данных hash-set. Однако это не проблема, потому что hash-set может заменить обычная hash-таблица, в которой элементы используются как ключи (в качестве значений можно использовать любой тип как можно меньшего размера). Этот странный прием применяется, например, в NHibernate, и хорошо работает если нет лучшего.

Я сравнивал две реализации вышеописанного алгоритма на Ruby с количеством элементов порядка 2000-3000, размером тэга 2-15 символов UTF-8 и количеством тэгов на элемент, в среднем, 5. Замена массива hash-set-ом дала прирост в производительности приблизительно в 10 раз.

В целом, hash-set-ы позволяют более оптимально реализовать операции над множествами — пересечение, объединение и вычитание. Однако не стоит забывать об их избыточности. Hash-set-ы резервируют значительно больше памяти, чем нужно для хранения их элементов, поэтому их имеет смысл использовать только для множеств среднего размера (100-10000 элементов). Фактически, вы тратите память, чтобы получить более быстрые вычисления. Для больших множеств следует использовать деревья.

  • программирование
  • структуры данных

Про Java

Set - множество уникальных элементов. Как определить уникальность мы поговорим в другой раз, вкратце - это делается с помощью метода equals(). Теперь о внутреннем устройстве: множество уникальных объектов - это как раз та вещь, о которой мы говорили в статье HashMap, только там это было множество объектов ключей. И действительно, если мы посмотрим на внутреннее устройство HashSet, найдем там объект HashMap. То есть HashSet - обертка для HashMap. Объекты, записываемые в Set, располагаются в качестве ключей, в качестве значения всегда записывается один и тот же объект типа Object.

Кстати, в классе LinkedHashSet данные содержатся во внутреннем объекте типа LinkedHashMap, а в классе TreeSet - в TreeMap

Как не стоит работать с HashSet в Java?

Данная статья рассчитана на тех, кто только начинает постигать основы языка Java. И людям с опытом может показаться очевидной банальщиной.

Года полтора назад работал над одним проектом. Развернут он был на AWS. Сервис на Java работал с БД DynamoDB (NoSQL). После очередной фичи в логах стали появляться ошибки, что приложение не может сохранить данные в БД из-за дублирования ключа. Я был в замешательстве, поскольку в коде для работы с данными использовал HashSet, и был уверен, что дубликаты не могут существовать. Оказалось - еще как могут.

Мы вполне законно можем закинуть объект в HashSet и дальше использовать и модифицировать его в коде. Из-за чего наш объект, находящийся в HashSet, тоже меняется. Это связано с тем, что в HashSet хранятся ссылки на объекты, а не сами объекты. Таким образом, два разных с точки зрения места в памяти объекта могут быть совершенно одинаковыми по своему наполнению. И в этом случае переопределение методов equals() и hashCode() не даст нужного эффекта, поскольку они срабатывают при добавлении нового элемента в коллекцию.

Для примера возьмем класс Dog, который имеет два поля - имя и возраст со стандартной реализацией equals и hashCode из пакета commons-lang3:

public class Dog < private String name; private int age; public Dog(String name, int age) < this.name = name; this.age = age; >public String getName() < return name; >public int getAge() < return age; >public void setName(String name) < this.name = name; >public void setAge(int age) < this.age = age; >@Override public String toString() < return "Dog"; > @Override public boolean equals(Object o) < if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Dog dog = (Dog) o; return new EqualsBuilder().append(age, dog.age).append(name, dog.name).isEquals(); >@Override public int hashCode() < return new HashCodeBuilder(17, 37).append(name).append(age).toHashCode(); >>

А теперь добавим в HashSet два объекта класса Dog - fluffy и jimmy:

Dog fluffy = new Dog("Fluffy", 3); Dog jimmy = new Dog("Jimmy", 4); Set dogs = new HashSet<>(); dogs.add(fluffy); dogs.add(jimmy);

Если мы выведем в консоль содержимое множества dogs, то получим строку вида:

[Dog, Dog]

А теперь объекту jimmy изменим значения полей name и age на 'Fluffy' и '3'. И тут самое интересное: в нашем множестве окажутся два одинаковых по своему наполнению объекта.

[Dog, Dog]

Почему так произошло? Здесь стоит вспомнить о типах переменных.

В Java переменные бывают двух типов: примитивные и ссылочные. Если с примитивами все понятно - они сразу хранят значение внутри себя, то с ссылочными переменными все несколько сложнее - они лишь хранят ссылку на область памяти, где расположено значение. Соответственно, меняя поля внутри объекта, мы не изменяем ссылку на него.

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

p.s. при хранении внутри коллекции immutable объектов данной ситуации не случится, но разбор mutable/immutable - это уже другая история.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *