해시맵의 키와 값

마지막으로 볼 컬렉션은 해시 맵(hash map)입니다. HashMap<K, V> 타입은 K 타입의 키와 V 타입의 값을 짝지어 저장하며, 해시 함수(hashing function)로 키와 값을 메모리 어디에 둘지 정합니다. 해시 함수가 키를 자리 번호로 바꾸는 방식과, 서로 다른 키가 같은 자리를 받았을 때 처리하는 기본 원리는 해시 테이블의 동작 원리에서 다룹니다. 그 글은 한 자리에 여러 항목을 함께 두는 체이닝으로 충돌을 처리하지만, 러스트의 HashMap은 표준 라이브러리 문서에 적힌 대로 정해진 순서로 다른 자리를 살펴보는 이차 탐사(quadratic probing)를 씁니다. 다른 많은 언어에도 이런 자료 구조가 있으며, 해시, 맵, 오브젝트, 해시 테이블, 딕셔너리, 연관 배열 같은 다른 이름으로 부르기도 합니다.

해시 맵은 벡터처럼 인덱스가 아니라 어떤 타입의 키로든 데이터를 찾고 싶을 때 쓸모가 있습니다. 예를 들어 게임에서 팀마다 점수를 기록할 때, 팀 이름을 키로 하고 점수를 값으로 하면 팀 이름으로 그 팀의 점수를 찾을 수 있습니다. 키의 타입은 같은지 비교할 수 있는 Eq와 해시 값을 만드는 Hash를 구현해야 하며, 같은 키는 같은 해시 값을 내야 합니다. 이 글에서는 해시 맵의 기본 API를 다루며, 표준 라이브러리의 HashMap에는 그 밖에도 쓸모 있는 기능이 많으니 문서를 찾아보세요.

새로운 해시맵 생성하기

빈 해시 맵을 만드는 한 가지 방법은 new로 만든 뒤 insert로 원소를 넣는 것입니다. 다음 코드는 Blue와 Yellow 두 팀의 점수를 기록하며, Blue는 10점, Yellow는 50점에서 시작합니다.

    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);

먼저 표준 라이브러리의 컬렉션 모듈에서 HashMap을 use로 가져와야 합니다. 이 장의 세 컬렉션 가운데 해시 맵은 가장 덜 쓰이므로 프렐류드에 없으며, 표준 라이브러리에는 해시 맵을 만드는 vec! 같은 매크로도 없습니다. 벡터처럼 해시 맵도 데이터를 힙에 저장하며, 이 HashMap은 String 타입의 키와 i32 타입의 값을 가집니다. 해시 맵도 벡터처럼 모든 키가 같은 타입이고 모든 값이 같은 타입이어야 합니다.

해시맵의 값 접근하기

get 메서드에 키를 넘기면 해시 맵에서 그 값을 꺼낼 수 있습니다. 아래 코드는 두 팀의 점수를 넣은 뒤 Blue 팀의 점수를 꺼내는데, 키가 없을 수도 있으므로 get의 결과를 바로 쓰지 않고 두 메서드를 이어 불러 정수로 만듭니다.

    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);

    let team_name = String::from("Blue");
    let score = scores.get(&team_name).copied().unwrap_or(0);

score는 Blue 팀의 값인 10이 됩니다. get은 Option<&V>를 돌려주며, 해시 맵에 그 키의 값이 없으면 None을 돌려줍니다. 이 코드는 copied로 Option<&i32>를 Option<i32>로 바꾼 뒤, unwrap_or로 그 키가 없으면 score를 0으로 정합니다. HashMap<String, i32>는 &str로도 찾을 수 있으므로, 찾기만 할 때는 scores.get("Blue")처럼 새 String을 만들지 않아도 됩니다.

벡터처럼 for로 해시 맵의 키와 값의 쌍을 반복할 수 있습니다.

    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);

    for (key, value) in &scores {
        println!("{key}: {value}");
    }

Yellow: 50
Blue: 10

이 코드는 각 쌍을 정해지지 않은 순서로 출력하므로, 실행할 때마다 순서가 다를 수 있습니다. 해시 맵의 반복 순서에 기대는 출력은 만들지 않으며, 순서가 필요하면 뒤에서처럼 키를 따로 정렬합니다.

해시맵과 소유권

i32처럼 Copy를 구현한 타입의 값은 해시 맵 안으로 복사되고, String처럼 소유권이 있는 값은 해시 맵으로 이동해 해시 맵이 그 값의 소유자가 됩니다. 아래 코드에서는 키와 값이 모두 String이므로, insert를 부르는 순간 두 변수의 값이 해시 맵으로 옮겨 갑니다.

    use std::collections::HashMap;

    let field_name = String::from("Favorite color");
    let field_value = String::from("Blue");

    let mut map = HashMap::new();
    map.insert(field_name, field_value);
    // field_name과 field_value는 여기부터 쓸 수 없음

insert로 field_name과 field_value를 해시 맵으로 옮긴 뒤에는 두 변수를 쓸 수 없습니다. 값의 참조를 해시 맵에 넣으면 그 값은 해시 맵으로 이동하지 않지만, 참조가 가리키는 값은 해시 맵이 유효한 동안 계속 유효해야 하며, 이는 라이프타임과 참조 유효성에서 다룹니다.

해시맵 업데이트하기

키와 값의 쌍은 늘어날 수 있지만, 각 키에는 값이 하나만 연결됩니다. 반대로 서로 다른 키가 같은 값을 가질 수는 있어서, Blue와 Yellow가 모두 10점일 수 있습니다. 해시 맵의 데이터를 바꿀 때는 키에 이미 값이 있을 때 어떻게 할지 정해야 합니다. 이전 값을 무시하고 새 값으로 바꿀 수도, 이전 값을 두고 새 값을 버리면서 키에 값이 없을 때만 새 값을 넣을 수도, 이전 값과 새 값을 합칠 수도 있습니다.

값을 덮어쓰기

어떤 키와 값을 넣은 뒤 같은 키로 다른 값을 넣으면, 그 키의 값은 새 값으로 바뀝니다. 다음 코드는 insert를 두 번 부르지만 둘 다 Blue의 값을 넣으므로, 해시 맵에는 쌍이 하나만 남습니다.

    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Blue"), 25);

    println!("{scores:?}");

{"Blue": 25}

원래 값 10은 덮어써졌습니다. insert는 바뀌기 전의 값을 Option<V>로 돌려주므로, 키가 처음 들어갔다면 None이, 이미 있던 값을 바꿨다면 Some(이전 값)이 됩니다. 그래서 부른 쪽이 새로 넣은 것인지 바꾼 것인지 알 수 있습니다.

키가 없을 때만 키와 값 추가하기

키가 해시 맵에 이미 있으면 그 값을 그대로 두고, 없으면 키와 값을 넣는 일은 흔합니다. 해시 맵에는 이를 위한 entry라는 API가 있습니다. entry는 확인할 키를 받아, 그 키의 값이 있는지 없는지를 나타내는 열거형 Entry를 돌려줍니다. Yellow 팀의 값이 있는지 확인해 없으면 50을 넣고, Blue 팀에도 똑같이 해 봅니다.

    use std::collections::HashMap;

    let mut scores = HashMap::new();
    scores.insert(String::from("Blue"), 10);

    scores.entry(String::from("Yellow")).or_insert(50);
    scores.entry(String::from("Blue")).or_insert(50);

    println!("{scores:?}");

Entry의 or_insert 메서드는 키에 값이 있으면 그 값의 가변 참조를 돌려주고, 없으면 인수로 받은 값을 넣은 뒤 그 새 값의 가변 참조를 돌려줍니다. 이렇게 하면 직접 로직을 쓰는 것보다 훨씬 깔끔하고, 대여 검사기와도 잘 맞습니다. 출력에는 순서가 다를 수 있지만 "Yellow": 50과 "Blue": 10 두 쌍이 들어 있습니다. 첫 entry는 Yellow에 값이 없으므로 50을 넣고, 둘째 entry는 Blue에 이미 10이 있으므로 해시 맵을 바꾸지 않습니다.

예전 값에 기초하여 값을 업데이트하기

해시 맵의 또 다른 흔한 쓰임은 키의 값을 찾아 이전 값을 바탕으로 고치는 것입니다. 예를 들어 다음 코드는 문장에 각 단어가 몇 번 나오는지 셉니다. 단어를 키로 해서 나올 때마다 값을 늘리며, 처음 보는 단어라면 먼저 0을 넣습니다.

    use std::collections::HashMap;

    let text = "hello world wonderful world";

    let mut map = HashMap::new();

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

    println!("{map:?}");

이 코드는 {"world": 2, "hello": 1, "wonderful": 1} 같은 결과를 출력하며, 해시맵의 값 접근하기에서 본 것처럼 쌍의 순서는 다를 수 있습니다. split_whitespace는 text를 공백으로 나눈 조각을 하나씩 돌려주는 반복자를 만듭니다. or_insert는 그 키의 값을 가리키는 가변 참조 &mut V를 돌려주므로, 그 참조를 count에 담고 *count로 역참조해 1을 더합니다. 가변 참조는 for의 한 회차가 끝날 때 스코프를 벗어나므로, 이 변경은 모두 안전하며 대여 규칙에 어긋나지 않습니다.

이미 있는 값만 먼저 고치고 없을 때는 처음 값을 넣고 싶다면 and_modify와 or_insert를 이어 씁니다. 아래 그림은 이 방법으로 단어를 셀 때, 처음 나온 단어와 이미 있는 단어가 어떻게 처리되는지 보여 줍니다.

처음 나온 단어는 entry로 찾았을 때 값이 없으므로 or_insert(1)이 1을 넣고, 이미 있는 단어는 and_modify가 그 값에 1을 더합니다. and_modify에 넘긴 |count| *count += 1은 클로저(closure)라는 작은 익명 함수로, 클로저: 자신의 환경을 캡처하는 익명 함수에서 다룹니다. 이 방식으로 단어를 세고, 출력할 때는 키를 정렬해 순서를 정합니다.

use std::collections::HashMap;

fn main() {
    let text = String::from("red blue red green blue red");
    let mut counts: HashMap<&str, usize> = HashMap::new();

    for word in text.split_whitespace() {
        counts.entry(word).and_modify(|count| *count += 1).or_insert(1);
    }

    let mut keys: Vec<&str> = counts.keys().copied().collect();
    keys.sort_unstable();

    for word in keys {
        println!("{word}: {}", counts.get(word).copied().unwrap_or(0));
    }
}

blue: 2
green: 1
red: 3

키는 text에서 빌린 &str이므로, text가 counts보다 오래 살아 있어야 합니다. 해시 맵의 반복 순서에 기대지 않도록 keys로 키를 벡터에 모아 정렬한 뒤 출력했으므로, 결과는 언제나 알파벳 순입니다. 각 메서드의 반환 타입은 HashMap 문서와 Entry 문서에 있습니다.

해시 함수

기본 HashMap은 해시 테이블을 노리는 서비스 거부(DoS) 공격에 견딜 수 있는 해시 함수를 무작위 시드로 쓰며, 표준 라이브러리 문서에 따르면 지금은 SipHash 1-3이지만 앞으로 바뀔 수 있습니다. 가장 빠른 해시 알고리즘은 아니지만, 성능을 조금 내주고 보안을 얻는 편이 낫다고 보았습니다. 프로그램을 측정해 보니 기본 해시 함수가 너무 느리다면, 다른 해셔(hasher)를 지정해 바꿀 수 있습니다. 해셔는 BuildHasher 트레이트를 구현한 타입이며, 트레이트는 9장에서 다룹니다. 해셔를 직접 처음부터 만들 필요는 없고, crates.io에 흔한 해싱 알고리즘을 구현한 라이브러리가 있습니다. 다만 더 빠른 알고리즘이 악의적인 입력에도 같은 방어력을 갖는 것은 아니므로, 입력을 믿을 수 있는지와 측정 결과를 함께 보고 바꿉니다.

더 깊이: 해시맵 안에 든 키를 바꾸면 어떻게 될까

표준 라이브러리의 해시 테이블은 구글의 SwissTable을 러스트로 옮긴 구현입니다. Rust 1.36 발표에 따르면 이때 HashMap의 구현이 SwissTable 설계를 따른 hashbrown 크레이트의 것으로 바뀌었고, 인터페이스는 그대로이면서 평균적으로 더 빠르고 메모리를 덜 쓰게 되었습니다. 다만 hashbrown 크레이트를 직접 쓸 때와 달리, 표준 라이브러리의 HashMap은 기본 해시 함수로 여전히 SipHash 1-3을 씁니다.

해시 맵은 키를 넣을 때 계산한 해시 값으로 자리를 정하므로, 키가 맵 안에 있는 동안 그 키의 해시 값이나 Eq로 판단한 같음이 바뀌면 안 됩니다. HashMap 문서는 이런 변경이 보통 Cell이나 RefCell, 전역 상태, 입출력, unsafe 코드를 거쳐야만 가능하며, 그렇게 하는 것은 논리 오류(logic error)라고 설명합니다. 그 결과는 정해져 있지 않아 패닉, 틀린 결과, 프로그램 중단, 메모리 누수, 끝나지 않는 실행이 모두 가능하지만, 그 문제를 겪은 HashMap 안에 머물 뿐 정의되지 않은 동작으로 이어지지는 않습니다. 그래서 키 타입에는 내부 가변성으로 해시에 쓰이는 부분을 바꿀 수 있는 필드를 두지 않는 것이 안전합니다.

컬렉션을 써 보는 문제

벡터, 문자열, 해시 맵은 데이터를 저장하고, 꺼내고, 고쳐야 하는 프로그램에 필요한 기능을 많이 제공합니다. 다음 문제로 직접 연습해 보세요. 정수 목록이 주어지면 벡터로 중앙값(median, 정렬했을 때 가운데 값)을, 해시 맵으로 최빈값(mode, 가장 많이 나오는 값)을 구하는 문제, 문자열을 피그 라틴(pig Latin)으로 바꾸는 문제, 그리고 회사의 부서에 직원 이름을 더하고 목록을 보여 주는 문자 인터페이스를 만드는 문제입니다. 피그 라틴에서는 단어의 첫 자음을 단어 끝으로 옮기고 ay를 붙여 first가 irst-fay가 되고, 모음으로 시작하는 단어는 끝에 hay를 붙여 apple이 apple-hay가 되는데, UTF-8을 다루는 방법을 떠올리며 만들어야 합니다.

이런 문제는 자료 구조의 이름부터 고르기보다, 입력의 모양과 자주 하는 접근, 바꾸는 규칙, 출력의 순서를 먼저 정해야 합니다. 같은 컬렉션을 써도 빈 입력이나 동률, 중복, 정렬을 어떻게 처리할지에 따라 결과가 달라지기 때문입니다. 부서 문제를 예로, 명령을 Add 이름 to 부서의 네 단어로 받고, 같은 부서에 같은 이름은 한 번만 저장하며, 부서와 이름을 모두 알파벳 순으로 보여 주기로 정해 봅니다.

use std::collections::HashMap;

fn main() {
    let commands = [
        "Add Sally to Engineering",
        "Add Amir to Sales",
        "Add Amir to Engineering",
    ];
    let mut departments: HashMap<String, Vec<String>> = HashMap::new();

    for command in commands {
        let words: Vec<&str> = command.split_whitespace().collect();
        if words.len() == 4 && words[0] == "Add" && words[2] == "to" {
            let name = words[1].to_string();
            let people = departments.entry(words[3].to_string()).or_default();
            if !people.contains(&name) {
                people.push(name);
            }
        }
    }

    let mut names: Vec<&String> = departments.keys().collect();
    names.sort();

    for department in names {
        let mut people = departments[department].clone();
        people.sort();
        println!("{department}: {}", people.join(", "));
    }
}

Engineering: Amir, Sally
Sales: Amir

아래 그림처럼 첫 명령은 네 단어를 확인한 뒤 빈 맵의 Engineering에 Sally를 저장하고, 나머지 두 명령은 Sales와 Engineering에 Amir를 더합니다. 부서는 Engineering, Sales 순으로 정렬하고, Engineering에 저장된 Sally, Amir는 보여 줄 때 Amir, Sally로 정렬합니다. or_default는 키가 없으면 그 타입의 기본값, 여기서는 빈 벡터를 넣고 그 가변 참조를 돌려줍니다.

표준 라이브러리의 API 문서에는 이런 문제에 쓸모 있는 벡터, 문자열, 해시 맵의 메서드가 설명되어 있습니다.

정리

• HashMap<K, V>는 키와 값을 짝지어 저장하며, use std::collections::HashMap;으로 가져와 new와 insert로 만듭니다.
• get은 Option<&V>를 돌려주며, for (k, v) in &map으로 쌍을 반복하지만 그 순서는 정해져 있지 않습니다.
• Copy 타입은 해시 맵에 복사되고, String 같은 값은 해시 맵으로 이동합니다.
• 같은 키로 insert하면 값을 덮어쓰고 이전 값을 Some으로 돌려줍니다.
• entry(k).or_insert(v)는 키가 없을 때만 값을 넣고, 어느 경우든 그 값의 가변 참조를 돌려줍니다.
• 이전 값을 바탕으로 고칠 때는 or_insert가 돌려준 참조를 역참조하거나, and_modify와 or_insert를 이어 씁니다.
• 기본 해시 함수는 DoS 공격에 견디도록 고른 것이며, 필요하면 다른 해셔로 바꿀 수 있습니다.

연습 문제

1. 반환 값과 저장된 값

단어 세기 프로그램으로 "go stop go"를 센 뒤, let before = counts.insert("go", 5);, *counts.entry("stop").or_insert(10) += 2;, counts.entry("new").or_insert(0);을 차례로 실행했습니다. before와 정렬해 출력한 세 줄은 무엇인가요?

2. 같은 이름을 두 번 더하기

부서 프로그램의 명령을 "Add Zoe to Sales", "Add Amir to Sales", "Add Zoe to Sales"로 바꾸면 무엇이 출력되나요? 같은 이름을 두 번 저장하지 않는 규칙을 빼면 어떻게 달라지나요?

3. 중앙값과 최빈값

정수 목록 [3, 1, 4, 1, 5]의 중앙값과 최빈값은 무엇인가요? 목록이 [3, 1, 4, 1]이라면 중앙값을 어떻게 정해야 하나요?

이것으로 7장을 마칩니다. 프로그램이 복잡해지면 실패할 수 있는 연산이 늘어나므로, 다음 장의 panic!과 복구 불가능한 오류부터는 러스트의 오류 처리를 살펴봅니다.