Я изучаю использование наборов. Мой вопрос: наборы не содержат дубликатов. Когда мы пытаемся вставить дубликаты, это не вызывает никакой ошибки и автоматически удаляет дубликаты. Является ли хорошей практикой проверять каждое значение перед вставкой в набор, существует ли он или нет? Или это нормально делать что-то вроде приведенного ниже кода? Я думаю, что Java будет делать внутреннюю проверку, используя .contains(value). Как вы думаете?
Какова была бы сложность Big O в обоих случаях, учитывая, что в набор входит n элементов?
import java.util.HashSet;
import java.util.Set;
public class DuplicateTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
Set<Integer> mySet = new HashSet<Integer>();
mySet.add(10);
mySet.add(20);
mySet.add(30);
mySet.add(40);
mySet.add(50);
mySet.add(50);
mySet.add(50);
mySet.add(50);
mySet.add(50);
mySet.add(50);
System.out.println("Contents of the Hash Set :"+mySet);
}
}
В соответствии с docs:
public boolean add(E e)Добавляет указанный элемент к этому набору, если он еще не присутствует. Более формально добавляет указанный элемент e к этому набору, если этот набор не содержит элемента e2, такого, что (e == null? E2 == null: e.equals(e2)). Если этот набор уже содержит элемент, вызов оставляет неизменным и возвращает false.
Итак, метод add() уже возвращает вам значение true или false. Поэтому вам не нужно делать дополнительную проверку.
Сравните с документацию API Set.add(E)
Метод add проверяет, находится ли элемент уже в Set. Если элемент уже присутствует, то новый элемент не добавляется, а Set остается неизменным. В большинстве случаев вам не нужно ничего проверять.
Сложность метода зависит от конкретной реализации Set, который вы используете.
Его нормально не проверять. Это основное преимущество над наборами списков, поскольку они автоматически отфильтровывают дубликаты.
HashSet имеет постоянную производительность (http://docs.oracle.com/javase/8/docs/api/java/util/HashSet.html)
Этот класс предлагает постоянную производительность по времени для основных операций (добавление, удаление, наличие и размер), предполагая, что хеш-функция правильно распределяет элементы среди ковшей
Функция add возвращает логическое значение, которое вы можете проверить, чтобы определить, был ли элемент уже установлен в Set. Это, конечно, основывается на ваших потребностях и не является лучшей практикой. Хорошо знать, что он не удалит элемент, который уже существует, поэтому он не может зависеть, чтобы обновить существующее значение с помощью новой информации, если вы определяете равные на основе суррогатных ключей из своей базы данных. Это противоположно тому, как Карты работают как карта, возвратит любое существующее значение и заменит его новым значением.
Вот ответы на ваши вопросы:
Когда мы пытаемся вставить дубликаты, это не вызывает никаких ошибок и автоматически удаляет дубликаты.
Ваше понимание неверно. Вызов Set.add() не будет добавлять новый элемент, если он уже находится в наборе; это утверждение применяется ко всем реализациям Set, включая HashSet и TreeSet.
Хорошо ли проверять каждое значение перед вставкой в набор существует ли это или нет? или это нормально сделать что-то вроде ниже код? Я думаю, что java будет внутренне выполнять проверку, используя .contains(значение). Как вы думаете?
Поскольку ваше понимание было неправильным с самого начала, вам не нужно проверять каждое значение перед вставкой в набор, чтобы увидеть, существует ли он уже. Да, внутри, он делает что-то вроде contains().
Какова будет сложность Big Oh в обоих случаях, учитывая есть "n" элементов, входящих в множество?
Для HashSet временная сложность O(1) для каждого add(). Для TreeSet() - который вы не использовали - временная сложность O(lg N) для каждого add().