HashSet и BTreeMap в Rust

HashSet (множество) — это коллекция уникальных значений. Положишь одно и то же значение дважды — сохранится оно один раз. Представь список гостей у входа: охраннику важно только, есть ли твоё имя в списке, а не сколько раз его туда вписали.

Ты уже знаешь Vec и HashMap. Эта страница добавляет остальные коллекции, которые нужны чаще всего: HashSet, отсортированные BTreeMap и BTreeSet, а ещё VecDeque для очередей. В конце есть таблица, которая поможет выбрать подходящую.

Создаём HashSet

HashSet лежит в std::collections, поэтому нужна строка use. Метод insert возвращает bool: true, если значение новое, и false, если оно уже было.

use std::collections::HashSet;

fn main() {
    let mut tags = HashSet::new();

    println!("{}", tags.insert("rust"));
    println!("{}", tags.insert("web"));
    println!("{}", tags.insert("rust")); // уже есть

    println!("уникальных тегов: {}", tags.len());
}

Вывод:

true
true
false
уникальных тегов: 2

▶ Попробуй сам

Этот bool полезнее, чем кажется. Он отвечает на вопрос «видел ли я это раньше?» за тот же шаг, что и добавление, так что отдельная проверка не нужна.

Проверяем и удаляем значения

contains говорит, есть ли значение в множестве. remove убирает его и, как и insert, возвращает bool — было ли что-то на самом деле удалено.

use std::collections::HashSet;

fn main() {
    let mut online: HashSet<&str> = HashSet::from(["ana", "ben", "chen"]);

    println!("ben в сети? {}", online.contains("ben"));

    println!("удалили ben: {}", online.remove("ben"));
    println!("удалили ben ещё раз: {}", online.remove("ben"));

    println!("ben в сети? {}", online.contains("ben"));
    println!("в сети: {}", online.len());
}

Вывод:

ben в сети? true
удалили ben: true
удалили ben ещё раз: false
ben в сети? false
в сети: 2

▶ Попробуй сам

Почему здесь множество, а не Vec? contains у Vec просматривает все элементы по одному. А HashSet сразу переходит к ответу, каким бы большим он ни был. Когда пользователей миллион, разница огромная.

Осторожно

У HashSet нет фиксированного порядка. Если вывести его через {:?} или перебрать в цикле, порядок может меняться от запуска к запуску. Когда для вывода нужен стабильный порядок, скопируй значения в Vec и отсортируй его или используй BTreeSet (о нём ниже).

Убираем повторы из Vec

Очень частая задача: в списке есть повторы, а нужно каждое значение по одному разу. Есть два хороших способа — в зависимости от того, важен ли исходный порядок.

use std::collections::HashSet;

fn main() {
    let visits = vec![3, 1, 3, 2, 1, 5, 2];

    // Способ 1: собрать в множество, потом отсортировать для стабильного порядка
    let unique: HashSet<i32> = visits.iter().copied().collect();
    let mut sorted: Vec<i32> = unique.into_iter().collect();
    sorted.sort();
    println!("уникальные по порядку: {:?}", sorted);

    // Способ 2: оставить первое появление каждого значения, в исходном порядке
    let mut seen = HashSet::new();
    let mut in_order = visits.clone();
    in_order.retain(|x| seen.insert(*x));
    println!("в исходном порядке:    {:?}", in_order);
}

Вывод:

уникальные по порядку: [1, 2, 3, 5]
в исходном порядке:    [3, 1, 2, 5]

▶ Попробуй сам

Способ 2 использует bool из insert. retain оставляет элемент, только когда замыкание возвращает true, а insert возвращает true только при первой встрече значения.

Математика множеств: объединение, пересечение, разность

Множества можно комбинировать, как круги на диаграмме Венна. Каждый метод возвращает итератор, поэтому мы собираем результаты в Vec и сортируем их перед выводом, чтобы каждый раз получать одно и то же. Названия языков здесь — английские слова, поэтому сортировка по алфавиту работает предсказуемо.

use std::collections::HashSet;

fn main() {
    let alice: HashSet<&str> = HashSet::from(["rust", "python", "go"]);
    let bob: HashSet<&str> = HashSet::from(["go", "java", "rust"]);

    let mut both: Vec<_> = alice.intersection(&bob).collect();
    both.sort();
    println!("знают оба:         {:?}", both);

    let mut either: Vec<_> = alice.union(&bob).collect();
    either.sort();
    println!("знает хоть один:   {:?}", either);

    let mut only_alice: Vec<_> = alice.difference(&bob).collect();
    only_alice.sort();
    println!("только Алиса:      {:?}", only_alice);

    let mut only_one: Vec<_> = alice.symmetric_difference(&bob).collect();
    only_one.sort();
    println!("знает только один: {:?}", only_one);
}

Вывод:

знают оба:         ["go", "rust"]
знает хоть один:   ["go", "java", "python", "rust"]
только Алиса:      ["python"]
знает только один: ["java", "python"]

▶ Попробуй сам

difference работает в одну сторону: alice.difference(&bob) — это «что знает Алиса и не знает Боб». Поменяй их местами — и получишь список Боба. symmetric_difference — обе стороны сразу: всё, что знает только кто-то один из них.

BTreeMap и BTreeSet: всегда отсортированы

BTreeMap работает так же, как HashMap, а BTreeSet — как HashSet. Разница в том, что они держат ключи отсортированными. При переборе ты каждый раз получаешь ключи по порядку.

use std::collections::{BTreeMap, BTreeSet};

fn main() {
    let text = "the cat sat on the mat the end";

    let mut counts: BTreeMap<&str, u32> = BTreeMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }
    for (word, count) in &counts {
        println!("{word}: {count}");
    }

    let scores: BTreeSet<u32> = BTreeSet::from([72, 95, 58, 88]);
    println!("наименьший: {:?}", scores.first());
    println!("наибольший: {:?}", scores.last());
    println!("все: {:?}", scores);
}

Вывод:

cat: 1
end: 1
mat: 1
on: 1
sat: 1
the: 3
наименьший: Some(58)
наибольший: Some(95)
все: {58, 72, 88, 95}

▶ Попробуй сам

Текст здесь оставлен на английском, потому что результат зависит от сортировки по буквам. API entry — тот же, что ты видел в уроке HashMap. Раз таблица — BTreeMap, слова выходят в алфавитном порядке без отдельной сортировки.

Что выбрать?

• По умолчанию бери HashMap / HashSet. Поиск в них обычно быстрее.
• Бери BTreeMap / BTreeSet, когда данные нужны по порядку: вывести отсортированный отчёт, найти наименьший или наибольший ключ или получить диапазон ключей.

VecDeque: очередь

VecDeque (произносится «век-дек») — это список, в который можно быстро добавлять и из которого можно быстро удалять с обоих концов. Поэтому он естественно подходит для очереди: первым пришёл — первым ушёл, как люди в очереди.

use std::collections::VecDeque;

fn main() {
    let mut line: VecDeque<&str> = VecDeque::new();
    line.push_back("Аня");
    line.push_back("Бен");
    line.push_back("Чэнь");

    while let Some(person) = line.pop_front() {
        println!("обслуживаем: {person}, ждут ещё: {}", line.len());
    }
}

Вывод:

обслуживаем: Аня, ждут ещё: 2
обслуживаем: Бен, ждут ещё: 1
обслуживаем: Чэнь, ждут ещё: 0

▶ Попробуй сам

Можно было бы использовать для этого Vec::remove(0), но он сдвигает все остальные элементы на одну позицию. pop_front у VecDeque этого не делает, поэтому остаётся быстрым даже для длинной очереди.

Какую коллекцию выбрать?

Коллекция	Используй, когда нужно…	Пример
Vec<T>	Упорядоченный список с доступом по позиции	Строки файла, список результатов
HashMap<K, V>	Быстро находить значение по ключу	Логин → профиль пользователя
HashSet<T>	Уникальные значения и быстрая проверка «есть ли тут?»	Посещённые страницы, запрещённые слова
BTreeMap<K, V>	Ключ → значение, ключи отсортированы	Подсчёт слов с выводом по алфавиту
VecDeque<T>	Добавлять и удалять с обоих концов	Очередь задач или сообщений

Если сомневаешься, начни с Vec. Меняй его, когда заметишь, что снова и снова ищешь в нём (бери множество или таблицу) или часто удаляешь с начала (бери VecDeque).

Частые ошибки

Положить свою структуру в HashSet без нужных derive. HashSet должен хешировать значения и сравнивать их на равенство. Твоя структура сама этого не умеет:

use std::collections::HashSet;

struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut visited = HashSet::new();
    visited.insert(Point { x: 0, y: 0 });
}

error[E0277]: the trait bound `Point: Eq` is not satisfied
  --> src/main.rs:10:13
   |
10 |     visited.insert(Point { x: 0, y: 0 });
   |             ^^^^^^ the trait `Eq` is not implemented for `Point`

error[E0277]: the trait bound `Point: Hash` is not satisfied
  --> src/main.rs:10:13
   |
10 |     visited.insert(Point { x: 0, y: 0 });
   |             ^^^^^^ the trait `Hash` is not implemented for `Point`

Компилятор сообщает, что для Point не реализованы трейты Eq и Hash. Исправление — одна строка над структурой: #[derive(PartialEq, Eq, Hash)]. Для BTreeSet понадобятся ещё PartialOrd и Ord, чтобы он знал, как сортировать. Что значит каждый из них, рассказано в уроке Популярные трейты.

use std::collections::HashSet;

#[derive(PartialEq, Eq, Hash)]
struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut visited = HashSet::new();
    visited.insert(Point { x: 0, y: 0 });
    visited.insert(Point { x: 1, y: 0 });
    visited.insert(Point { x: 0, y: 0 }); // повтор, игнорируется
    println!("посещено клеток: {}", visited.len());
}

Вывод:

посещено клеток: 2

▶ Попробуй сам

Дальше

Нужна очередь (первым пришёл — первым ушёл) или «всегда давай следующим самый большой»? В уроке VecDeque и BinaryHeap разобраны две коллекции, созданные именно для этого.

Практика

1. Первый повтор

Дан список слов ["красный", "синий", "зелёный", "синий", "красный"]. Выведи первое слово, которое встречается второй раз. Подсказка: insert возвращает false, когда значение уже есть в множестве, а break останавливает цикл.

Показать решение

use std::collections::HashSet;

fn main() {
    let words = ["красный", "синий", "зелёный", "синий", "красный"];
    let mut seen = HashSet::new();

    for word in words {
        if !seen.insert(word) {
            println!("Первый повтор: {word}");
            break;
        }
    }
}

Вывод:

Первый повтор: синий

▶ Попробуй сам

!seen.insert(word) читается как «вставить не удалось», то есть «это я уже видел». Первым повторяется "синий". "красный" тоже повторяется, но позже.

2. Буквы по порядку

Посчитай, сколько раз каждая буква встречается в "mississippi", и выведи результат в алфавитном порядке. Подсказка: используй BTreeMap с тем же приёмом entry(...).or_insert(0) из раздела про BTreeMap и перебирай word.chars().

Показать решение

use std::collections::BTreeMap;

fn main() {
    let word = "mississippi";
    let mut counts = BTreeMap::new();

    for letter in word.chars() {
        *counts.entry(letter).or_insert(0) += 1;
    }

    for (letter, count) in &counts {
        println!("{letter}: {count}");
    }
}

Вывод:

i: 4
m: 1
p: 2
s: 4

▶ Попробуй сам

С HashMap эти четыре строки могли бы выйти в любом порядке. BTreeMap держит ключи отсортированными, поэтому i, m, p, s каждый раз выводятся по алфавиту.

Итоги

• HashSet хранит уникальные значения. insert и remove возвращают bool — изменилось ли что-то.
• contains у множества быстрый даже для огромных множеств. У Vec он проверяет каждый элемент.
• union, intersection, difference и symmetric_difference выполняют операции над множествами. Перед выводом результаты сортируй.
• BTreeMap и BTreeSet держат ключи отсортированными — бери их, когда важен порядок.
• VecDeque — основной выбор для очереди: push_back, чтобы встать в очередь, pop_front, чтобы выйти из неё.

Проверь себя

Проверь себя

1. Что вернёт set.insert(x), если x уже есть в множестве?

true Ошибку false Старое значение

2. Нужен подсчёт слов с выводом по алфавиту, без ручной сортировки. Какая таблица подойдёт лучше всего?

HashMap BTreeMap Vec VecDeque

3. Почему вывод HashSet через {:?} может отличаться от запуска к запуску?

У HashSet нет фиксированного порядка {:?} работает случайно Множества со временем теряют значения Так бывает только в отладочном режиме

4. Какая коллекция лучше всего подходит для очереди «первым пришёл — первым ушёл»?

HashSet BTreeSet HashMap VecDeque

Результат: 0 / 4

Что почитать

• std::collections overview — документация стандартной библиотеки (на английском): подробное руководство по выбору коллекции со скоростью каждой операции.
• HashSet — Rust на примерах: запускаемый пример с union, intersection и difference (перевод на русский).
• HashSet — документация стандартной библиотеки (на английском): все методы множества, включая is_subset и retain.
• BTreeMap — документация стандартной библиотеки (на английском): отсортированные таблицы, в том числе range для получения диапазона ключей.
• VecDeque — документация стандартной библиотеки (на английском): все методы очереди, например push_front, pop_back и front.