해시셋(HashSet)

해시셋(HashSet)은 중복되지 않는 데이터의 집합을 다루기 위한 표준 라이브러리 컬렉션 중 하나이다. 해시셋 내부에서는 해시 함수를 사용하여 데이터를 효율적으로 저장하고 조회한다. 예를 들어, 해시셋에 10, 20, 30을 넣었다면 같은 값이 중복해서 추가되지 않으며, 특정 값이 이미 존재하는지를 빠르게 확인할 수 있다. 이는 집합(Set)의 기본적인 특징으로, 동일한 값을 오직 하나만 보관한다. 따라서 데이터가 중복 없이 한 번씩만 존재해야 하는 상황에서 매우 유용하다.

해시셋을 사용하기 위해서는 우선 std::collections에 정의된 HashSet을 스코프로 가져와야 한다. 일반적으로 HashSet 타입을 정의할 때는 T가 해시 가능한(Hash) 특성과 동등 비교(PartialEq, Eq)를 만족해야 한다. 이러한 제약은 표준 라이브러리에 구현된 해시 알고리즘이 원소를 구분하기 위해 해시 값과 동등 비교를 수행하기 때문이다.

HashSet은 내부적으로 해시 충돌에 대비하는 방법을 구현하고 있다. 해싱 과정에서 두 개 이상의 서로 다른 원소가 동일한 해시 값을 가질 수 있는데, 이를 충돌이라 한다. 러스트 표준 라이브러리의 HashSet은 보편적으로 해시 충돌을 다루는 알고리즘을 사용해 평균적으로 O(1)에 가까운 삽입, 삭제, 조회가 가능하도록 설계되어 있다. 해시 충돌이 빈번하게 발생하면 성능이 저하될 수 있으므로, T에 대해 충돌을 최소화하는 해시 함수가 구현되는 것이 중요하다. 다행히 표준 라이브러리에서 기본 제공하는 해시 함수는 대부분의 일반적인 상황에서 충분한 성능을 낸다.

해시셋을 생성하는 가장 간단한 방법은 HashSet::new 함수를 사용하는 것이다. 이때 별도의 타입 파라미터를 명시하거나, 삽입되는 값의 타입을 통해 유추하도록 할 수 있다. 다음 예시는 정수 타입을 담는 해시셋을 생성해 여러 가지 연산을 수행하는 방식이다.

use std::collections::HashSet;

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

    numbers.insert(10);
    numbers.insert(20);
    numbers.insert(30);
    numbers.insert(20); // 이미 존재하므로 추가되지 않음

    println!("현재 해시셋: {:?}", numbers);

    if numbers.contains(&10) {
        println!("10은 이미 해시셋에 존재한다.");
    }

    numbers.remove(&30);
    println!("30을 제거한 후: {:?}", numbers);
}

위 코드에서 numbers.insert(20)이 여러 번 호출되어도 해시셋에는 20이 오직 한 번만 저장된다. 또한 contains 메서드를 사용하면 특정 값의 존재 여부를 확인할 수 있으며, remove 메서드를 통해 원소를 제거할 수 있다.

해시셋을 다른 해시셋과 연산하는 기능도 자주 사용된다. 수학에서의 집합 연산 개념인 합집합(union), 교집합(intersection), 차집합(difference), 대칭차집합(symmetric_difference)을 모두 제공한다. 이러한 연산은 값이 중복되지 않는 집합 특성을 살려, 필요한 연산 결과를 효율적으로 구할 수 있도록 해준다.

use std::collections::HashSet;

fn main() {
    let mut a = HashSet::new();
    a.insert(1);
    a.insert(2);
    a.insert(3);

    let mut b = HashSet::new();
    b.insert(3);
    b.insert(4);
    b.insert(5);

    let union_ab = a.union(&b);
    let intersection_ab = a.intersection(&b);
    let difference_ab = a.difference(&b);
    let symmetric_diff_ab = a.symmetric_difference(&b);

    println!("합집합: {:?}", union_ab.collect::<Vec<_>>());
    println!("교집합: {:?}", intersection_ab.collect::<Vec<_>>());
    println!("차집합(a - b): {:?}", difference_ab.collect::<Vec<_>>());
    println!("대칭차집합: {:?}", symmetric_diff_ab.collect::<Vec<_>>());
}

union 메서드는 두 해시셋을 합쳐서 모든 원소를 순회할 수 있는 이터레이터를 반환한다. intersection 메서드는 두 해시셋에 모두 존재하는 원소만, difference 메서드는 한쪽 해시셋에는 존재하지만 다른 해시셋에는 없는 원소만, symmetric_difference 메서드는 두 해시셋 간에 서로 겹치지 않는 원소만을 순회할 수 있는 이터레이터를 제공한다. collect 메서드를 사용해 결과를 원하는 컬렉션 타입으로 변환할 수 있다.

해시셋을 사용할 때 주의해야 할 점은 순서가 보장되지 않는다는 것이다. 내부적으로 해시를 이용해 관리하므로, 원소를 삽입한 순서와 실제 순회 순서가 다를 수 있다. 이는 집합 자료 구조가 원소의 순서 정보를 유지하지 않는다는 점에서 자연스러운 특성이며, 해시셋이 빠른 삽입, 검색, 삭제를 제공할 수 있는 근거이기도 하다.

해시 함수를 고정하지 않고 사용자가 직접 지정할 수 있는 고급 기능도 있다. 예를 들어 사용자 정의 해시 함수가 필요하거나 보안 강화를 위해 SipHash가 아닌 다른 해시를 사용하고 싶다면, HashSet<T, S> 제네릭 타입의 두 번째 파라미터로 BuildHasher 트레이트를 구현한 타입을 전달할 수 있다. 이렇게 하면 Rust 표준 라이브러리가 아니라 사용자가 원하는 해시 알고리즘으로 원소를 해싱할 수 있다. 그러나 대부분의 경우 기본 해시 알고리즘이 충분하며, 주로 극단적인 성능 최적화나 보안을 고려하는 경우에만 이 옵션을 사용한다.

일반적인 시나리오에서 HashSet은 원소가 중복 없이 관리되어야 하고, 빠른 삽입과 조회가 중요할 때 적합하다. 해시셋의 크기가 커질수록 내부적으로 해시 테이블을 재할당하거나 리사이즈(resize)하는 과정이 발생할 수 있다. 이는 러스트가 내부적으로 처리해 주므로, 성능 최적화를 위해서는 해시셋을 다루는 동안 어떤 크기로 성장할 가능성이 있는지 미리 짐작해 capacity를 설정해 주는 방법을 고려할 수도 있다.

HashSet은 데이터의 중복을 허용하지 않는 집합 추상화로서, 해시 충돌을 효율적으로 관리하고 평균적으로 O(1)에 가까운 연산 복잡도를 제공하는 강력한 도구다. Rust의 안전성과 결합되어, 중복이 없어야 하는 데이터를 안전하고 빠르게 관리해야 할 때 해시셋이 이상적인 선택이 될 수 있다.