해시맵의 키와 값

마지막으로 볼 일반적인 컬렉션은 해시맵(hash map) 입니다.

HashMap<K, V> 타입은 K 타입의 키와 V 타입의 값에 대해 해시 함수(hashing function) 를 사용하여 매핑한 것을 저장하는데, 이 해시 함수는 이 키와 값을 메모리 어디에 저장할지 결정합니다.

수많은 다른 프로그래밍 언어도 이러한 종류의 데이터 구조를 지원하지만, 종종 해시, 맵, 오브젝트, 해시 테이블, 혹은 연관 배열(associative) 등과 같이 이름만 다르게 사용됩니다.

해시맵은 벡터에서처럼 인덱스를 이용하는 것이 아니라 임의의 타입으로 된 키를 이용하여 데이터를 찾고 싶을 때 유용합니다.

키 타입은 Eq + Hash 계약을 만족해야 합니다. 서로 같은 키라면 같은 해시를 만들어야 하며, 맵에 들어간 동안 동등성이나 해시 결과가 바뀌지 않도록 설계해야 합니다.

예를 들면, 게임에서 각 팀의 점수를 해시맵에 유지할 수 있는데, 여기서 키는 팀의 이름이고 값은 팀의 점수가 됩니다.

팀의 이름을 제공하면 그 팀의 점수를 조회할 수 있습니다.

이번 절에서는 해시맵의 기본 API를 다룰 것이지만, 표준 라이브러리의 HashMap에 정의되어 있는 함수 중에는 더 많은 좋은 것들이 숨어있습니다.

항상 말했듯이, 더 많은 정보를 원하신다면 표준 라이브러리 문서를 확인하세요.

새로운 해시맵 생성하기

빈 해시맵을 생성하는 한 가지 방법으로 new를 사용한 뒤 insert를 이용하여 요소를 추가하는 것이 있습니다.

예제 7-20에서는 팀 이름이 각각 블루와 옐로인 두 팀의 점수를 관리하고 있습니다.

블루 팀은 10점, 옐로 팀은 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 타입의 값을 갖습니다.

벡터와 비슷하게 해시맵도 동질적입니다.

모든 키는 서로 같은 타입이어야 하고, 모든 값도 같은 타입이여야 합니다.

해시맵의 값 접근하기

예제 7-23처럼 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는 블루 팀과 연관된 값을 갖게 될 것이고, 결괏값은 10일 것입니다.

get 메서드는 Option<&V>를 반환합니다; 만일 이 해시맵에 해당 키에 대한 값이 없다면 get은 None을 반환할 것입니다.

조회 키는 맵이 소유한 키 타입의 빌린 형태일 수도 있습니다. 예를 들어 HashMap<String, V>는 동등한 해시·비교 계약을 가진 &str로 조회할 수 있으므로, 단순 조회를 위해 새 String을 만들 필요가 없습니다.

이 프로그램에서는 copied를 호출하여 Option<&i32>가 아닌 Option<i32>를 얻어온 다음, unwrap_or를 써서 scores가 해당 키에 대한 아이템을 가지고 있지 않을 경우 score에 0을 설정하도록 처리합니다.

벡터에서와 유사한 방식으로 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처럼 소유권이 있는 값의 경우, 아래의 예제 7-22와 같이 값들이 이동되어 해시맵이 그 값의 소유자가 됩니다.

    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를 해시맵으로 이동시킨 후에는 더 이상 이 둘을 사용할 수 없습니다.

해시맵에 값들의 참조자들을 삽입한다면, 이 값들은 해시맵으로 이동되지 않을 것입니다.

하지만 참조자가 가리키고 있는 값은 해시맵이 유효할 때까지 계속 유효해야 합니다.

이와 관련하여 9장의 ‘라이프타임으로 참조자의 유효성 검증하기’절에서 더 자세히 이야기할 것입니다.

아래 다이어그램은 조회, 교체, 조건부 삽입과 누적 갱신을 소유권·키 계약과 함께 비교합니다.

해시맵 업데이트하기

키와 값 쌍의 개수는 늘어날 수 있을지라도, 각각의 유일한 키는 연관된 값을 딱 하나만 가질 수 있습니다.

그 역은 성립하지 않습니다.

예를 들면 블루 팀과 옐로 팀 모두 scores 해시맵에 10점을 저장할 수도 있습니다.

해시맵의 데이터를 변경하고 싶을 때는 키에 이미 값이 할당되어 있을 경우에 대한 처리 방법을 결정해야 합니다.

예전 값을 완전히 무시하면서 새 값으로 대신할 수도 있습니다.

혹은 예전 값을 계속 유지하면서 새 값은 무시하고, 해당 키에 값이 할당되어 있지 않을 경우에만 새 값을 추가하는 방법을 선택할 수도 있습니다.

또는 예전 값과 새 값을 조합할 수도 있습니다.

각각의 경우를 어떻게 할지 살펴봅시다!

값을 덮어쓰기

해시맵에 어떤 키와 값을 삽입하고, 그 후 똑같은 키에 다른 값을 삽입하면, 해당 키에 연관된 값은 새 값으로 대신될 것입니다.

아래 예제 7-23의 코드가 insert를 두 번 호출함에도, 해시맵은 딱 하나의 키/값 쌍을 담게 되는데 그 이유는 두 번 모두 블루 팀의 키에 대한 값을 삽입하고 있기 때문입니다.

    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(old_value)이므로 호출부가 삽입과 교체를 구분할 수 있습니다.

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

해시맵 내에 특정 키가 이미 있는지 검사한 뒤, 다음과 같은 동작을 하는 경우는 흔합니다.

만일 키가 해시맵 내에 존재하면, 해당 값은 그대로 둬야 합니다.

만일 키가 없다면, 키와 그에 대한 값을 추가합니다.

해시맵은 이를 위해 entry라고 하는 특별한 API를 가지고 있는데, 이는 검사하려는 키를 매개변수로 받습니다.

entry 함수의 반환 값은 열거형 Entry인데, 해당 키가 있는지 혹은 없는지를 나타냅니다.

옐로 팀에 대한 키에 대한 값이 있는지 검사하고 싶다고 해봅시다.

만일 없다면 값 50을 삽입하고, 블루 팀에 대해서도 똑같이 하려고 합니다.

entry API를 사용한 코드는 아래의 예제 7-24와 같습니다.

    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 메서드는 키가 비어 있으면 기본값을 삽입하고, 어느 경우든 그 값의 가변 참조자 &mut V를 반환합니다.

이 방법은 직접 로직을 작성하는 것보다 훨씬 깔끔하고, 게다가 대여 검사기와 잘 어울려 동작합니다.

예제 7-24의 출력 순서는 달라질 수 있지만, "Yellow": 50과 "Blue": 10 두 키/값 쌍을 포함합니다.

첫 번째 entry 호출은 옐로 팀에 대한 키에 대하여 값 50을 삽입하는데, 이는 옐로 팀이 값을 가지고 있지 않기 때문입니다.

두 번째 entry 호출은 해시맵을 변경하지 않는데, 왜냐하면 블루 팀은 이미 값 10을 가지고 있기 때문입니다.

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

해시맵에 대한 또 다른 일반적인 사용 방식은 키에 대한 값을 찾아서 예전 값에 기초하여 값을 업데이트하는 것입니다.

예를 들어, 예제 7-25는 어떤 텍스트 내에 각 단어가 몇 번이나 나왔는지를 세는 코드를 보여줍니다.

단어를 키로 사용하는 해시맵을 이용하여 해당 단어가 몇 번이나 나왔는지 추적하기 위해 값을 증가시켜 줍니다.

처음 본 단어라면, 값 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를 역참조해야 합니다.

가변 참조자는 for 루프의 끝에서 스코프 밖으로 벗어나고, 따라서 모든 값의 변경은 안전하며 대여 규칙에 위배되지 않습니다.

기존 값에만 먼저 작업한 뒤 없을 때 기본값을 넣고 싶다면 and_modify와 or_insert를 연결할 수 있습니다.

map.entry(word)
    .and_modify(|count| *count += 1)
    .or_insert(1);

해시 함수

기본 HashMap<K, V>의 해시 빌더 타입은 무작위로 시드되는 RandomState입니다. 표준 라이브러리가 내부에서 선택하는 구체적인 해시 알고리즘은 바뀔 수 있으므로 애플리케이션 계약으로 의존하지 않습니다.

프로파일링 결과와 입력의 신뢰 경계를 함께 검토한 뒤에만 BuildHasher 구현을 지정해 교체합니다. 더 빠른 알고리즘이 항상 HashDoS 같은 적대적 입력에도 같은 방어 특성을 제공하는 것은 아닙니다.

해시맵까지 살펴본 뒤에는 세 컬렉션을 어떤 상황에서 고를지 다시 묶어 보면 좋습니다.

벡터는 순서가 있는 같은 타입의 목록, 문자열은 유효한 UTF-8 텍스트, 해시맵은 Eq + Hash 키로 값을 찾는 관계에 맞습니다. 해시맵 반복 순서는 안정된 출력 계약이 아니므로 순서가 필요하면 키나 결과를 별도로 정렬합니다.

패키지 정리

벡터, 문자열, 해시맵은 프로그램에서 여러분이 데이터를 저장하고, 접근하고, 수정하고 싶은 곳에 필요한 수많은 기능들을 제공해 줄 것입니다.

다음 연습문제에서는 지금까지 다룬 내용을 직접 적용합니다.

• 정수 리스트가 주어졌을 때, 벡터를 이용하여 이 리스트의 중간값(median, 정렬했을 때 가장 가운데 위치한 값), 그리고 최빈값(mode, 가장 많이 발생한 값; 해시맵이 여기서 도움이 될 것입니다)을 반환해보세요.
• 문자열을 피그 라틴(pig Latin)으로 변경해보세요. 각 단어의 첫 번째 자음은 단어의 끝으로 이동하고 ‘ay’를 붙이므로, ‘first’는 ‘irst-fay’가 됩니다. 모음으로 시작하는 단어는 대신 끝에 ‘hay’를 붙입니다. (‘apple’은 ‘apple-hay’가 됩니다.) UTF-8 인코딩에 대한 세부 사항을 명심하세요!
• 해시맵과 벡터를 이용하여 사용자가 회사 부서의 직원 이름을 추가할 수 있도록 하는 텍스트 인터페이스를 만들어 보세요. 예를 들어 ‘Add Sally to Engineering’이나 ‘Add Amir to Sales’ 같은 식으로요. 그 후 사용자가 모든 사람에 대해 알파벳 순으로 정렬된 목록이나 부서별 모든 사람에 대한 목록을 조회할 수 있도록 해보세요.

해시맵 연습문제는 키 선택, 값 소유권, entry API, 출력 정렬을 함께 묻기 때문에 작은 명령 처리 흐름으로 나누어 점검하면 구현이 안정적입니다.

중간값은 빈 입력과 짝수 길이 정책을, 최빈값은 동률 처리 정책을 먼저 정합니다. 부서별 직원 목록은 HashMap<String, Vec<String>>에 저장하더라도 부서와 이름을 표시할 때 각각 정렬해야 재현 가능한 결과가 됩니다.

표준 라이브러리 API 문서는 이 연습문제들에 도움될 만한 벡터, 문자열, 해시맵의 메서드를 설명해 줍니다!

연산이 실패할 수 있는 더 복잡한 프로그램이 등장하고 있는 상황입니다; 따라서, 다음은 에러 처리에 대해 다룰 완벽한 시간이란 뜻이죠!