컬렉션 (HashMap, HashSet)

🔹 HashMap 

use std::collections::HashMap;

let mut map = HashMap::new();
map.insert("KL", "Kerala");
println!("{:?}", map);

🧱 정의

HashMap<K, V>는 K 타입의 키를 해시 함수로 변환하여 V 타입의 값에 매핑하는 연관 배열(Associative Array) 입니다.

• 키는 Eq + Hash 트레잇을 구현해야 한다.
• 평균 시간 복잡도 O(1)로 값을 삽입·삭제·조회할 수 있다.
• 기본 해시 알고리즘은 SipHash-1-3 (DoS-저항형)이다

🧱 기본 구조

use std::collections::HashMap;

let mut map: HashMap<String, i32> = HashMap::new();
map.insert("Blue".to_string(), 10);
map.insert("Yellow".to_string(), 50);

 

• 동질성: 모든 키는 같은 타입, 모든 값도 같은 타입.
• 힙 저장: 데이터는 힙 메모리에 보관된다.

---

🏗️ 다양한 생성 방법

1. new + insert

let mut map = HashMap::new();
map.insert("apple", 3);

 

2. collect로 벡터·zip 활용

let keys   = ["a", "b"];
let vals   = [1, 2];
let map: HashMap<_, _> = keys.iter().zip(vals.iter()).collect();

 

3. 배열 리터럴 (Rust 1.56+)

let map = HashMap::from([
    ("pi", 3.14),
    ("e", 2.71),
]);

 

🔍 주요 API 예시

값 조회	map.get("Blue") → Some(&10)
존재하지 않으면 삽입	map.entry("Red").or_insert(0);
값 업데이트	*map.entry("Blue").or_insert(0) += 5;
전체 순회	for (k, v) in &map { println!("{k}: {v}"); }

🗝️ 소유권 규칙

• Copy 타입(예: i32)은 복사된다.
• String 등 소유형은 move 되므로 이후 사용 불가.
• 참조를 넣으려면 lifetime을 명시해야 한다.

🧪 실전 예제: 단어 빈도 계산

use std::collections::HashMap;

let text = "hello world wonderful world";
let mut freq: HashMap<&str, usize> = HashMap::new();

for word in text.split_whitespace() {
    *freq.entry(word).or_insert(0) += 1;
}

println!("{freq:?}");
// 출력: {"world": 2, "wonderful": 1, "hello": 1}

 

✅ 요약

 

타입	HashMap<K, V>
모듈	std::collections
시간 복잡도	평균 O(1)
중복 키	자동 덮어쓰기
순서 보장	❌ (필요 시 IndexMap 사용)
기본 해셔	SipHash-1-3

🔹 HashSet

use std::collections::HashSet;

let mut set = HashSet::new();
set.insert("Apple");
println!("집합 크기: {}", set.len());

 

 

Rust hashset 내부 구조

Rust의 HashSet은 중복을 허용하지 않는 집합(Set) 자료구조로, 내부적으로는 값이 ()인 HashMap으로 구현되어 있다. 즉, 키(Key)만 존재하고 값(Value)은 없는 형태의 HashMap이라고 보면 된다.

 

✅ 정의 (한 줄 요약)

Rust의 HashSet은 Eq + Hash 트레잇을 구현한 고유한 요소들을 해시 테이블로 관리하며, 삽입·삭제·조회가 평균 O(1)인 집합 자료구조다.

use std::collections::HashSet;

fn main() {
    let mut set = HashSet::new();
    set.insert("apple");
    set.insert("banana");
    set.insert("apple"); // 중복 삽입 무시됨

    println!("집합 크기: {}", set.len()); // 2
    println!("banana 포함 여부: {}", set.contains("banana")); // true
}

 

🧩 주요 특징

항목설명

중복 허용	❌ (동일한 값은 한 번만 저장)
순서 보장	❌ (삽입 순서와 무관)
필요 트레잇	저장하려는 타입은 Eq + Hash 구현 필수
내부 구조	HashMap<T, ()>
평균 시간복잡도	삽입, 삭제, 조회 모두 O(1)

 

🧮 집합 연산 예제

use std::collections::HashSet;

fn main() {
    let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
    let b: HashSet<_> = [2, 3, 4].iter().cloned().collect();

    let union: HashSet<_> = a.union(&b).collect(); // 합집합
    let diff: HashSet<_> = a.difference(&b).collect(); // 차집합
    let inter: HashSet<_> = a.intersection(&b).collect(); // 교집합

    println!("합집합: {:?}", union); // {1, 2, 3, 4}
    println!("차집합: {:?}", diff); // {1}
    println!("교집합: {:?}", inter); // {2, 3}
}

 

📌 요약 그림 (개념도)

HashSet<T>
   ↓ (내부)
HashMap<T, ()>
   ↓
┌─────────────┐
│ 버킷 배열   │
│ [0] → T1    │
│ [1] → ∅     │
│ [2] → T2    │
└─────────────┘

 

참고

• 공식 문서 – HashSet in std::collections
• Delft Stack – Rust HashSet 사용법

HashSet in std::collections - Rust

 

Rust에서 두 세트 간의 차이 계산하기