Как работает hashset в java
HashSet в Java — это реализация интерфейса Set , который использует хэш-таблицы для хранения элементов коллекции. HashSet не гарантирует порядок элементов при их переборе, и не допускает хранение дублирующихся элементов.
Основные операции, которые можно выполнить с HashSet :
- добавление элемента: add()
- удаление элемента: remove()
- проверка наличия элемента: contains()
- очистка коллекции: clear()
- получение размера коллекции: size()
HashSet реализован как хэш-таблица , где элементы хранятся в виде ключей, а значения не используются.
- При добавлении элемента, HashSet рассчитывает его хэш-код и добавляет в таблицу с соответствующим индексом.
- Если в таблице уже есть элемент с таким же хэш-кодом , то выполняется проверка на равенство.
- Если элементы равны, то новый элемент не добавляется в коллекцию, иначе он добавляется в таблицу.
При работе с HashSet важно правильно определить методы hashCode() и equals() для класса, который будет храниться в коллекции. Это позволит корректно выполнять поиск и удаление элементов. Если класс не переопределит методы hashCode() и equals() , то будут использоваться реализации по умолчанию, которые могут не давать ожидаемых результатов при работе с HashSet
Как работает HashSet?
Всё отработало и показало 1 — Sts , то есть исключило дубликат. Объясните почему везде пишется что нужно переопределить hashCode() и equals() чтобы это заработало или я в чем-то ошибаюсь. 2 вопрос: Порядок добавления элементов вычисляется с помощью хэш-кода. Как понять это? То есть прежде чем добавлять у элементов вычисляется хэш код и они ставятся по порядку своих хэш кодов?
Отслеживать
66.3k 6 6 золотых знаков 51 51 серебряный знак 112 112 бронзовых знаков
задан 29 мая 2019 в 11:43
Mike Mclaren Mike Mclaren
835 12 12 серебряных знаков 23 23 бронзовых знака
Хороший цикл статей про структуры данных в java: m.habr.com/ru/post/128017
29 мая 2019 в 19:39
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
Объясните почему везде пишется что нужно переопределить hashCode() и equals() чтобы это заработало или я в чем-то ошибаюсь.
Хеш используется для быстрого поиска нужного объекта. Согласитесь, что быстрее сравнить два целочисленных значения (особенно, если они еще и как-то отсортированы), чем сравнивать все поля объекта.
Но т.к. разные объекты могут дать один и тот же хеш, то при нахождении объекта с нужным хешем затем еще и проводится проверка на равенство этих объектов.
Например, для двух строк
String str1 = "aaaaaaaaaaaaaaaaaaaaaaaaaaa"; String str2 = "aaaaaaaaaaaaaaaaaaaaaaaaaab"; чтобы узнать равны они или нет, придется сравнить каждый символ. И только при сравнении последнего, узнать, что строки не равны.
Или же сравнить хеши
int hash1 = str1.hashCode(); int hash2 = str2.hashCode(); if (hash1 != hash2) < // Строки не равны >else < // хеши равны, но строки все равно могут быть не равны, // поэтому сравниваем еще и сами строки if (!str1.equals(str2)) < // Строки не равны >else < // Строки равны >> когда нужно сравнить два объекта, то сравнение быстрее, т.к. вычисление хеша операция не быстрая. Но если нужно проводить регулярный поиск по списку, то хеши можно подсчитать лишь единожды.
Вы используете стандартный класс String . Для него методы hashCode() и equals() уже переопределены
То есть прежде чем добавлять у элементов вычисляется хэш код
Да. Смотри ответ выше
и они ставятся по порядку своих хэш кодов?
Не обязательно. Сортировка по хешу — это особенность реализации. Ее может не быть вообще, она может быть довольно хитрой. Могут использоваться деревья.
В целом, когда мы говорим о Set<> понятие сортировки не определено
Множества: Set, HashSet, LinkedHashSet, TreeSet
HashSet, TreeSet и LinkedHashSet относятся к семейству Set. В множествах Set каждый элемент хранится только в одном экземпляре, а разные реализации Set используют разный порядок хранения элементов. В HashSet порядок элементов определяется по сложному алгоритму. Если порядок хранения для вас важен, используйте контейнер TreeSet, в котором объекты хранятся отсортированными по возрастанию в порядке сравнения или LinkedHashSet с хранением элементов в порядке добавления.
Множества часто используются для проверки принадлежности, чтобы вы могли легко проверить, принадлежит ли объект заданному множеству, поэтому на практике обычно выбирается реализация HashSet, оптимизированная для быстрого поиска.
В Android 11 (R) обещают добавить несколько перегруженных версий метода of(), которые являются частью Java 8.
HashSet
Название Hash. происходит от понятия хэш-функция. Хэш-функция — это функция, сужающая множество значений объекта до некоторого подмножества целых чисел. Класс Object имеет метод hashCode(), который используется классом HashSet для эффективного размещения объектов, заносимых в коллекцию. В классах объектов, заносимых в HashSet, этот метод должен быть переопределен (override).
Имеет два основных конструктора (аналогично ArrayList):
// Строит пустое множество public HashSet() // Строит множество из элементов коллекции public HashSet(Collection c)
Методы
- public Iterator iterator()
- public int size()
- public boolean isEmpty()
- public boolean contains(Object o)
- public boolean add(Object o)
- public boolean addAll(Collection c)
- public Object[] toArray()
- public boolean remove(Object o)
- public boolean removeAll(Collection c)
- public boolean retainAll(Collection c) — (retain — сохранить). Выполняет операцию «пересечение множеств».
- public void clear()
- public Object clone()
Методы аналогичны методам ArrayList за исключением того, что метод add(Object o) добавляет объект в множество только в том случае, если его там нет. Возвращаемое методом значение — true, если объект добавлен, и false, если нет.
Перейдём к практике. Как это ни странно, но в жизни встречаются несколько Барсиков, Мурзиков и прочих Рыжиков. Несмотря на одинаковые имена, каждый кот неповторим. Надеюсь, с этим никто не спорит. Но пихать имена котов в множество HashSet не стоит, так как в множестве может храниться только одно имя и двух Мурзиков тут не записать. Другое дело — страны. Не может быть двух Франций, двух Англий, двух Россий (даже партия такая есть Единая Россия, впрочем мы отвлеклись).
Итак, создадим множество стран.
public void onClick(View view) < HashSetcountryHashSet = new HashSet<>(); countryHashSet.add("Россия"); countryHashSet.add("Франция"); countryHashSet.add("Гондурас"); countryHashSet.add("Кот-Д'Ивуар"); // любимая страна всех котов // Получим размер HashSet mInfoTextView.setText("Размер HashSet Кот-Д'Ивуар"); после России, то всё-равно размер останется прежним. Убедиться в этом можно, если вызвать метод iterator(), который позволяет получить всё множество элементов:
public void onClick(View view) < HashSetcountryHashSet = new HashSet<>(); countryHashSet.add("Россия"); countryHashSet.add("Кот-Д'Ивуар"); // любимая страна всех котов countryHashSet.add("Франция"); countryHashSet.add("Гондурас"); countryHashSet.add("Кот-Д'Ивуар"); // кот попросил добавить ещё раз для надёжности Iterator iterator = countryHashSet.iterator(); while (iterator.hasNext()) < mInfoTextView.setText(mInfoTextView.getText() + iterator.next() + ", "); >>
Несмотря на наше упрямство, мы видим только четыре добавленных элемента.
Стоит отметить, что порядок добавления стран во множество будет непредсказуемым. HashSet использует хэширование для ускорения выборки. Если вам нужно, чтобы результат был отсортирован, то пользуйтесь TreeSet.
Преобразовать в массив и вывести в ListView
Следующий пример - задел на будущее. Когда вы узнаете, что такое ListView, то вернитесь к этому уроку и узнайте, как сконвертировать множество в массив и вывести результат в компонент ListView (Список):
public void onClick(View view) < ArrayAdapteradapter; HashSet countryHashSet = new HashSet<>(); countryHashSet.add("Россия"); countryHashSet.add("Кот-Д'Ивуар"); // любимая страна всех котов countryHashSet.add("Франция"); countryHashSet.add("Гондурас"); // Конвертируем HashSet в массив String[] myArray = <>; myArray = countryHashSet.toArray(new String[countryHashSet.size()]); // Выводим массив в ListView final ListView listView = (ListView) findViewById(R.id.listView); adapter = new ArrayAdapter<>(this, android.R.layout.simple_list_item_1, myArray); listView.setAdapter(adapter); >
Продолжим опыты. Поработаем теперь с числами.
public void onClick(View view) < Random random = new Random(30); SetnumberSet = new HashSet<>(); for(int i = 0; i
Здесь мы ещё раз убеждаемся, что повторное добавление числа не происходит. В цикле случайным образом выбирается число от 0 до 9 тысячу раз. Естественно, многие числа должны были повториться при таком сценарии, но во множество каждое число попадёт один раз.
При этом данные не сортируются, так как расположены как попало.
Специально для Android был разработан новый класс ArraySet, который более эффективен.
ArraySet = HashSet
LinkedHashSet
Класс LinkedHashSet расширяет класс HashSet, не добавляя никаких новых методов. Класс поддерживает связный список элементов набора в том порядке, в котором они вставлялись. Это позволяет организовать упорядоченную итерацию вставки в набор.
TreeSet
Переделанный пример для вывода случайных чисел в отсортированном порядке. HashSet не может гарантировать, что данные будут отсортированы, так как работает по другому алгоритму. Если сортировка для вас важна, то используйте TreeSet.
public void onClick(View view) < Random random = new Random(30); SortedSetnumberSet = new TreeSet<>(); for(int i = 0; i
Со строками это выглядит нагляднее:
public void onClick(View view) < SortedSetcountrySet = new TreeSet<>(); countrySet.add("Россия"); countrySet.add("Франция"); countrySet.add("Гондурас"); countrySet.add("Кот-Д'Ивуар"); // любимая страна всех котов mInfoTextView.setText(countrySet.toString()); >
Названия стран выведутся в алфавитном порядке.
Класс TreeSet создаёт коллекцию, которая для хранения элементов применяет дерево. Объекты сохраняются в отсортированном порядке по возрастанию.
SortedSet
В примере с TreeSet использовался интерфейс SortedSet, который позволяет сортировать элементы множества. По умолчанию сортировка производится привычным способом, но можно изменить это поведение через интерфейс Comparable.
Кроме стандартных методов Set у интерфейса есть свои методы.
- Comparator comparator()
- subSet(Object fromElement, Object toElement)
- tailSet(Object fromElement)
- headSet(Object toElement)
- Object first()
- Object last()
SortedSet animalSet = new TreeSet(); animalSet.add("Antilope"); animalSet.add("Fox"); animalSet.add("Goat"); animalSet.add("Dog"); animalSet.add("Elephant"); animalSet.add("Bear"); animalSet.add("Hippo"); animalSet.add("Cat"); Iterator iterator = animalSet.iterator(); while(iterator.hasNext()) < // Antilope Bear Cat Dog Elephant Fox Goat Hippo mInfoTextView.append(iterator.next().toString() + " "); >Log.i(TAG, animalSet.subSet("Dog", "Hippo").toString()); // [Dog, Elephant, Fox, Goat] Log.i(TAG, animalSet.tailSet("Dog").toString()); // [Dog, Elephant, Fox, Goat, Hippo] Log.i(TAG, animalSet.headSet("Dog").toString()); // [Antilope, Bear, Cat] Log.i(TAG, animalSet.first()); // Antilope Log.i(TAG, animalSet.last()); // Hippo
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() >