Серия Java Collection (3): использование и различия HashSet, LinkedHashSet и TreeSet

В этом блоге в основном объясняется, как использовать три класса реализации интерфейса Set, HashSet, LinkedHashSet и TreeSet, а также различия между ними.

Примечание. Версия JDK, используемая в коде в этой статье, — 1.8.0_191.

1. Использование HashSet

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

private transient HashMap<E,Object> map;

Объявление кода класса HashSet выглядит так:

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
	......
}

1.1 Добавление элементов

Использование добавления элементов с помощью HashSet выглядит следующим образом:

HashSet<String> platformSet = new HashSet<>();

// 添加元素
System.out.println(platformSet.add("博客园"));
System.out.println(platformSet.add("掘金"));
System.out.println(platformSet.add("微信公众号"));

// 添加重复元素,不会添加成功,因为Set不允许重复元素
// 不过代码不会报错,而是返回false,即添加失败
System.out.println(platformSet.add("博客园"));
System.out.println(platformSet.add("掘金"));

Результат выполнения приведенного выше кода:

true

true

true

false

false

Отладка кода также обнаружит, что в platformSet всего 3 элемента:

Примечательно,platformSet.add(3, "个人博客");В этом коде возникнет ошибка компиляции, так как коллекция Set имеет только один метод для добавления элементов и не предоставляет двух перегрузок, таких как интерфейс List, описанный в предыдущем блоге.

1.2 Получить элементы

В отличие от интерфейса List, интерфейс класса Set не имеет метода для получения элементов.

1.3 Получить количество элементов набора

Метод использования для получения количества элементов HashSet следующий:

System.out.println("platformSet的元素个数为：" + platformSet.size());

1.4 Удаление элементов

Стоит отметить, что существует только один метод удаления элементов с помощью HashSet, в отличие от использования ArrayList для удаления элементов существует две перегрузки:

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

Метод использования следующий:

// 删除不存在的元素"个人博客",返回false
System.out.println(platformSet.remove("个人博客"));
// 删除存在的元素 "微信公众号",返回true
System.out.println(platformSet.remove("微信公众号"));

1.5 Изменение элементов

В отличие от интерфейса List, интерфейс класса Set не имеет методов для изменения элементов.

1.6 Определить, пуста ли коллекция

Метод использования для определения того, является ли HashSet пустым, выглядит следующим образом:

System.out.println("isEmpty:" + platformSet.isEmpty());

1.7 Элементы обхода (часто задают на собеседованиях)

Существует два основных способа обхода элементов HashSet:

обход итератора
цикл foreach

Метод использования следующий:

System.out.println("使用Iterator遍历：");
Iterator<String> platformIterator = platformSet.iterator();
while (platformIterator.hasNext()) {
    System.out.println(platformIterator.next());
}

System.out.println();
System.out.println("使用foreach遍历：");
for (String platform : platformSet) {
    System.out.println(platform);
}

1.8 Очистить коллекцию

Метод использования для очистки всех элементов в HashSet следующий:

platformSet.clear();

1.9 Полный пример кода

Для пунктов, объясненных выше, полный код выглядит следующим образом:

package collection;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class SetTest {
    public static void main(String[] args) {
        Set<String> platformSet = new HashSet<>();

        // 添加元素
        System.out.println(platformSet.add("博客园"));
        System.out.println(platformSet.add("掘金"));
        System.out.println(platformSet.add("微信公众号"));

        // 添加重复元素,不会添加成功,因为Set不允许重复元素
        // 不过代码不会报错,而是返回false,即添加失败
        System.out.println(platformSet.add("博客园"));
        System.out.println(platformSet.add("掘金"));


        System.out.println("platformSet的元素个数为：" + platformSet.size());

        // 删除不存在的元素"个人博客",返回false
        System.out.println(platformSet.remove("个人博客"));
        // 删除存在的元素 "微信公众号",返回true
        System.out.println(platformSet.remove("微信公众号"));

        System.out.println("platformSet的元素个数为：" + platformSet.size());

        System.out.println("isEmpty:" + platformSet.isEmpty());

        System.out.println("使用Iterator遍历：");
        Iterator<String> platformIterator = platformSet.iterator();
        while (platformIterator.hasNext()) {
            System.out.println(platformIterator.next());
        }

        System.out.println();
        System.out.println("使用foreach遍历：");
        for (String platform : platformSet) {
            System.out.println(platform);
        }

        System.out.println();

        platformSet.clear();
        System.out.println("isEmpty:" + platformSet.isEmpty());
    }
}

Результат:

true

true

true

false

false

Количество элементов platformSet: 3

false

true

Количество элементов platformSet: 2

isEmpty:false

Обход с помощью Iterator:

Блог Парк

Наггетс

Используйте foreach для обхода:

Блог Парк

Наггетс

isEmpty:true

2. Использование LinkedHashSet

LinkedHashSet также является классом реализации интерфейса Set. Базовая структура данных представляет собой связанный список и хеш-таблицу. Хеш-таблица используется для обеспечения уникальности элементов, а связанный список используется для обеспечения порядка вставки элементов. элементы, то есть FIFO (First Input First Output).

Объявление кода для класса LinkedHashSet выглядит следующим образом:

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
{
}

Как видно из приведенного выше кода, класс LinkedHashSet наследует класс HashSet.

Использование класса LinkedHashSet в основном такое же, как и у HashSet, просто измените код в следующем объявлении:

Set<String> platformSet = new LinkedHashSet<>();

3. Использование набора деревьев

TreeSet также является классом реализации интерфейса Set. Базовая структура данных — красно-черное дерево. TreeSet не только гарантирует уникальность элементов, но и порядок элементов.

Объявление кода для класса TreeSet выглядит следующим образом:

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
}

Использование класса TreeSet в основном такое же, как и у HashSet, просто измените код в следующем объявлении:

Set<String> platformSet = new TreeSet<>();

4. Разница между HashSet, LinkedHashSet и TreeSet (опросите часто задаваемые вопросы)

HashSet, LinkedHashSet и TreeSet — это три класса реализации, которые реализуют интерфейс Set, среди которых:

HashSet — это просто общий набор хранимых данных,

Основная функция LinkedHashSet состоит в том, чтобы гарантировать, что FIFO (первым пришел, первым вышел) является упорядоченным набором,

Основная функция TreeSet — сортировка (естественная сортировка или сортировка компаратором).

4.1 Сходства

1) HashSet, LinkedHashSet и TreeSet реализуют интерфейс Set.

2) Все три обеспечивают уникальность элементов, то есть элементы не могут повторяться

3) Ни один из трех не является потокобезопасным

Вы можете использовать метод Collections.synchronizedSet() для обеспечения безопасности потоков.

4.2 Отличия

4.2.1 Сортировка

HashSet не гарантирует порядок элементов

LinkHashSet гарантирует, что FIFO сортируется в порядке вставки.

TreeSet гарантирует порядок элементов и поддерживает настраиваемые правила сортировки.

В воздухе нет доказательств, просто посмотрите на эффект от кода:

HashSet<String> hashSet = new HashSet<>();
LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
TreeSet<String> treeSet = new TreeSet<>();

String[] letterArray = new String[]{"B", "A", "D", "C", "E"};
for (String letter : letterArray) {
    hashSet.add(letter);
    linkedHashSet.add(letter);
    treeSet.add(letter);
}

System.out.println("HashSet(我不保证顺序):" + hashSet);
System.out.println("LinkedHashSet(我保证元素插入时的顺序):" + linkedHashSet);
System.out.println("TreeSet(我按排序规则保证元素的顺序):" + treeSet);

Вывод приведенного выше кода:

HashSet (порядок не гарантирую): [A, B, C, D, E]

LinkedHashSet (порядок при вставке элементов гарантирую): [B, A, D, C, E]

TreeSet (порядок элементов гарантирую по сопоставлению): [A, B, C, D, E]

4.2.2 нулевое значение

HashSet, LinkedHashSet позволяет добавлять нулевые значения, TreeSet не позволяет добавлять нулевые значения, он будет выдавать при добавлении нулевого значенияjava.lang.NullPointerExceptionаномальный.

Set<String> platformSet = new TreeSet<>();
platformSet.add(null);

Запустив приведенный выше код, сообщение об ошибке выглядит следующим образом:

4.2.3 Производительность

Теоретически, добавляя одинаковое количество элементов, HashSet является самым быстрым, за ним следует LinkedHashSet, а TreeSet является самым медленным (из-за внутренней сортировки).

Затем мы используем пример для проверки, сначала создаем новый класс Employee и настраиваем правила сортировки:

package collection;

public class Employee implements Comparable<Employee> {
    private Integer employeeNo;

    public Employee(Integer employeeNo) {
        this.employeeNo = employeeNo;
    }

    public Integer getEmployeeNo() {
        return employeeNo;
    }

    public void setEmployeeNo(Integer employeeNo) {
        this.employeeNo = employeeNo;
    }

    @Override
    public int compareTo(Employee o) {
        return this.employeeNo - o.employeeNo;
    }
}

Затем добавьте следующий код подтверждения, чтобы добавить 10 000 элементов в HashSet, LinkedHashSet и TreeSet соответственно:

Random random = new Random();
HashSet<Employee> hashSet = new HashSet<>();
LinkedHashSet<Employee> linkedHashSet = new LinkedHashSet<>();
TreeSet<Employee> treeSet = new TreeSet<>();

int maxNo = 10000;

long startTime = System.nanoTime();
for (int i = 0; i < maxNo; i++) {
    int randomNo = random.nextInt(maxNo - 10) + 10;
    hashSet.add(new Employee(randomNo));
}

long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("HashSet耗时: " + duration);

startTime = System.nanoTime();
for (int i = 0; i < maxNo; i++) {
    int randomNo = random.nextInt(maxNo - 10) + 10;
    linkedHashSet.add(new Employee(randomNo));
}

endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedHashSet:耗时 " + duration);

startTime = System.nanoTime();
for (int i = 0; i < maxNo; i++) {
    int randomNo = random.nextInt(maxNo - 10) + 10;
    treeSet.add(new Employee(randomNo));
}

endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("TreeSet耗时: " + duration);

Первый запуск, результат вывода:

Время HashSet: 6203357

LinkedHashSet: занимает много времени 5246129

Время TreeSet: 7813460

Второй запуск, результаты вывода:

Время хешсета: 9726115

LinkedHashSet: отнимает много времени 5521640

Время TreeSet: 6884474

Третий запуск, результаты вывода:

Время HashSet: 7263940

LinkedHashSet: занимает много времени 6156487

Время TreeSet: 8554666

Четвертый запуск, результаты вывода:

Время хешсета: 6140263

LinkedHashSet: занимает много времени 4643429

Время TreeSet: 7804146

Пятый запуск, результаты вывода:

Время хешсета: 7913810

LinkedHashSet: занимает много времени 5847025

Время TreeSet: 8511402

Из 5 прогонов видно, что TreeSet занимает больше всего времени, но время LinkedHashSet каждый раз меньше, чем у HashSet.

Это противоречит самому быстрому HashSet, упомянутому выше, поэтому возникает вопрос:Что быстрее HashSet или LinkedHashSet?

Что вы думаете по этому поводу, добро пожаловать, чтобы оставить сообщение.

5. Два метода сортировки TreeSet (часто задаваемые вопросы в интервью)

Давайте рассмотрим приведенный выше код для сортировки с помощью TreeSet:

TreeSet<String> treeSet = new TreeSet<>();

String[] letterArray = new String[]{"B", "A", "D", "C", "E"};
for (String letter : letterArray) {
    treeSet.add(letter);
}

System.out.println("TreeSet(我按排序规则保证元素的顺序):" + treeSet);

Порядок, в котором мы вставляем элементы,"B", "A", "D", "C", "E", но порядок выходных элементов"A", "B", "C", "D", "E", что доказывает, что TreeSet отсортирован по внутренним правилам.

Итак, если тип элемента, помещенный в TreeSet, является нашим пользовательским ссылочным типом, каково его правило сортировки?

Имея в виду этот вопрос, мы создаем новый класс Student следующим образом:

package collection;

public class Student {
    private String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }
}

Затем добавьте следующий код подтверждения:

TreeSet<Student> studentTreeSet = new TreeSet<>();

Student student1 = new Student("zhangsan", 20);
Student student2 = new Student("lisi", 22);
Student student3 = new Student("wangwu", 24);
Student student4 = new Student("zhaoliu", 26);

Student student5 = new Student("zhangsan", 22);

studentTreeSet.add(student1);
studentTreeSet.add(student2);
studentTreeSet.add(student3);
studentTreeSet.add(student4);
studentTreeSet.add(student5);

for (Student student : studentTreeSet) {
    System.out.println("name:" + student.getName() + ",age:" + student.getAge());
}

Я с радостью запустил код и хотел увидеть эффект, но обнаружил следующую ошибку:

Почему это так?

Это потому, что мы не определили никаких правил сортировки для класса Student.TreeSet сказал, что я не знаю, как сортировать, поэтому давайте сгенерируем исключение, ха-ха.

Как это решить? Есть два способа:

естественный порядок
Компараторная сортировка

5.1 Естественный порядок

Способ реализации естественной сортировки состоит в том, чтобы позволить классу Student реализовать интерфейс Comparable и переопределить метод compareTo интерфейса, который определяет правила сортировки.

Метод compareTo, сгенерированный с помощью сочетаний клавиш IDEA, по умолчанию имеет следующее значение:

@Override
public int compareTo(Student o) {
    return 0;
}

Этот метод выполняется, когда элемент добавляется методом add(), чтобы определить позицию элемента.

Если он возвращает 0, это означает, что два элемента одинаковы, и сохраняется только первый элемент.

Если возвращаемое значение больше 0, это означает, что элемент должен быть размещен после элемента o, указанного в параметре

Если возвращаемое значение меньше 0, это означает, что этот элемент должен быть помещен перед элементом o, указанным в параметре

Поэтому, если вы не вносите никаких изменений в метод compareTo() и запускаете предыдущий проверочный код напрямую, вы обнаружите, что в коллекции есть только 1 элемент:

name:zhangsan,age:20

Затем измените логику метода compareTo() следующим образом:

@Override
public int compareTo(Student o) {
    // 排序规则描述如下
    // 按照姓名的长度排序,长度短的排在前面,长度长的排在后面
    // 如果姓名的长度相同，按字典顺序比较String
    // 如果姓名完全相同,按年龄排序,年龄小的排在前面,年龄大的排在后面

    int orderByNameLength = this.name.length() - o.name.length();
    int orderByName = orderByNameLength == 0 ? this.name.compareTo(o.name) : orderByNameLength;
    int orderByAge = orderByName == 0 ? this.age - o.age : orderByName;

    return orderByAge;
}

Снова запустив предыдущий проверочный код, вы получите следующий результат:

name:lisi,age:22

name:wangwu,age:24

name:zhaoliu,age:26

name:zhangsan,age:20

name:zhangsan,age:22

5.2 Сортировка компаратором

Сортировка компаратором реализована путем создания нового класса компаратора, наследования интерфейса Comparator и переопределения метода Compare() в интерфейсе.

Примечание. Таким образом, классу Student не нужно реализовывать интерфейс Comparable, а также не нужно переопределять метод compareTo интерфейса.

package collection;

import java.util.Comparator;

public class StudentComparator implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        // 排序规则描述如下
        // 按照姓名的长度排序,长度短的排在前面,长度长的排在后面
        // 如果姓名的长度相同，按字典顺序比较String
        // 如果姓名完全相同,按年龄排序,年龄小的排在前面,年龄大的排在后面

        int orderByNameLength = o1.getName().length() - o2.getName().length();
        int orderByName = orderByNameLength == 0 ? o1.getName().compareTo(o2.getName()) : orderByNameLength;
        int orderByAge = orderByName == 0 ? o1.getAge() - o2.getAge() : orderByName;

        return orderByAge;
    }
}

Затем измените код, который объявляет studentTreeSet в проверочном коде:

TreeSet<Student> studentTreeSet = new TreeSet<>(new StudentComparator());

Вывод точно такой же, как при использовании естественного порядка.

6. Исходный код и ссылка

Подробное объяснение систем коллекций, таких как List, Set и Map в коллекциях Java (наиболее полное в истории)