해쉬맵(hash map)

마지막으로 볼 일반적인 컬렉션은 해쉬맵입니다. HashMap<K, V> 타입은 K 타입의 키에 V 타입의 값을 매핑한 것을 저장합니다. 이 매핑은 해쉬 함수(hashing function) 을 통해 동작하는데, 해쉬 함수는 이 키와 값을 메모리 어디에 저장할지 결정합니다. 많은 다른 프로그래밍 언어들도 이러한 종류의 데이터 구조를 지원하지만, 종종 해쉬, 맵, 오브젝트, 해쉬 테이블, 혹은 연관 배열 (associative) 등과 같은 그저 몇몇 다른 이름으로 이용됩니다.

해쉬맵은 여러분이 벡터를 이용하듯 인덱스를 이용하는 것이 아니라 임의의 타입으로 된 키를 이용하여 데이터를 찾기를 원할때 유용합니다. 예를 들면, 게임 상에서는 각 팀의 점수를 해쉬맵에 유지할 수 있는데, 여기서 키는 팀의 이름이고 값은 팀의 점수가 될 수 있습니다. 팀의 이름을 주면, 여러분은 그 팀의 점수를 찾을 수 있습니다.

이 장에서는 해쉬맵의 기본 API를 다룰 것이지만, 표준 라이브러리의 HashMap에 정의되어 있는 함수 중에는 더 좋은 것들이 숨어있습니다. 항상 말했듯이, 더 많은 정보를 원하신다면 표준 라이브러리 문서를 확인하세요.

새로운 해쉬맵 생성하기

우리는 빈 해쉬맵을 new로 생성할 수 있고, insert를 이용하여 요소를 추가할 수 있습니다. Listing 8-20에서, 우리는 팀 이름이 각각 블루(Blue)와 옐로우(Yellow)인 두 팀의 점수를 유지하고 있습니다. 블루 팀은 10점, 옐로우 팀은 50점으로 시작할 것입니다:


# #![allow(unused_variables)]
#fn main() {
use std::collections::HashMap;

let mut scores = HashMap::new();

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

Listing 8-20: 새로운 해쉬맵을 생성하여 몇 개의 키와 값을 집어넣기

먼저 표준 라이브러리의 컬렉션 부분으로부터 HashMapuse로 가져와야할 필요가 있음을 주목하세요. 우리가 보고 있는 세 가지 일반적인 컬렉션 중에서 이 해쉬맵이 제일 덜 자주 사용되는 것이기 때문에, 프렐루드(prelude) 내에 자동으로 가져와지는 기능에 포함되어 있지 않습니다. 또한 해쉬맵은 표준 라이브러리로부터 덜 지원을 받습니다; 예를 들면 해쉬맵을 생성하는 빌트인 매크로가 없습니다.

벡터와 마찬가지로, 해쉬맵도 데이터를 힙에 저장합니다. 이 HashMapString 타입의 키와 i32 타입의 값을 갖습니다. 벡터와 비슷하게 해쉬맵도 동질적입니다: 모든 키는 같은 타입이어야 하고, 모든 값도 같은 타입이여야 합니다.

해쉬맵을 생성하는 또다른 방법은 튜플의 벡터에 대해 collect 메소드를 사용하는 것인데, 이 벡터의 각 튜플은 키와 키에 대한 값으로 구성되어 있습니다. collect 메소드는 데이터를 모아서 HashMap을 포함한 여러 컬렉션 타입으로 만들어줍니다. 예를 들면, 만약 두 개의 분리된 벡터에 각각 팀 이름과 초기 점수를 갖고 있다면, 우리는 zip 메소드를 이용하여 “Blue”와 10이 한 쌍이 되는 식으로 튜플의 벡터를 생성할 수 있습니다. 그 다음 Listing 8-21과 같이 collect 메소드를 사용하여 튜플의 벡터를 HashMap으로 바꿀 수 있습니다:


# #![allow(unused_variables)]
#fn main() {
use std::collections::HashMap;

let teams  = vec![String::from("Blue"), String::from("Yellow")];
let initial_scores = vec![10, 50];

let scores: HashMap<_, _> = teams.iter().zip(initial_scores.iter()).collect();
#}

Listing 8-21: 팀의 리스트와 점수의 리스트로부터 해쉬맵 생성하기

타입 명시 HashMap<_, _>이 필요한데 이는 collect가 다른 많은 데이터 구조로 바뀔 수 있고, 러스트는 여러분이 특정하지 않으면 어떤 것을 원하는지 모르기 때문입니다. 그러나 키와 값의 타입에 대한 타입 파라미터에 대해서는 밑줄을 쓸 수 있으며 러스트는 벡터에 담긴 데이터의 타입에 기초하여 해쉬에 담길 타입을 추론할 수 있습니다.

해쉬맵과 소유권

i32와 같이 Copy 트레잇을 구현한 타입에 대하여, 그 값들은 해쉬맵 안으로 복사됩니다. String과 같이 소유된 값들에 대해서는, 아래의 Listing 8-22와 같이 값들이 이동되어 해쉬맵이 그 값들에 대한 소유자가 될 것입니다:


# #![allow(unused_variables)]
#fn main() {
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은 이 지점부터 유효하지 않습니다.
// 이들을 이용하는 시도를 해보고 어떤 컴파일러 에러가 나오는지 보세요!
#}

Listing 8-22: 키와 값이 삽입되는 순간 이들이 해쉬맵의 소유가 되는 것을 보여주는 예

insert를 호출하여 field_namefield_value를 해쉬맵으로 이동시킨 후에는 더 이상 이 둘을 사용할 수 없습니다.

만일 우리가 해쉬맵에 값들의 참조자들을 삽입한다면, 이 값들은 해쉬맵으로 이동되지 않을 것입니다. 하지만 참조자가 가리키고 있는 값은 해쉬맵이 유효할 때까지 계속 유효해야합니다. 이것과 관련하여 10장의 “라이프타임을 이용한 참조자 유효화”절에서 더 자세히 이야기할 것입니다.

해쉬맵 내의 값 접근하기

Listing 8-23과 같이 해쉬맵의 get 메소드에 키를 제공하여 해쉬맵으로부터 값을 얻어올 수 있습니다:


# #![allow(unused_variables)]
#fn main() {
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);
#}

Listing 8-23: 해쉬맵 내에 저장된 블루 팀의 점수 접근하기

여기서 score는 블루 팀과 연관된 값을 가지고 있을 것이고, 결과값은 Some(&10)일 것입니다. 결과값은 Some으로 감싸져 있는데 왜냐하면 getOption<&V>를 반환하기 때문입니다; 만일 해쉬맵 내에 해당 키에 대한 값이 없다면 getNone을 반환합니다. 프로그램은 우리가 6장에서 다루었던 방법 중 하나로 Option을 처리해야 할 것입니다.

우리는 벡터에서 했던 방법과 유사한 식으로 for 루프를 이용하여 해쉬맵에서도 각각의 키/값 쌍에 대한 반복작업을 할 수 있습니다:


# #![allow(unused_variables)]
#fn main() {
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

해쉬맵 갱신하기

키와 값의 개수가 증가할 수 있을지라도, 각각의 개별적인 키는 한번에 연관된 값 하나만을 가질 수 있습니다. 해쉬맵 내의 데이터를 변경하길 원한다면, 키에 이미 값이 할당되어 있을 경우에 대한 처리를 어떻게 할지 결정해야 합니다. 예전 값을 완전히 무시하면서 예전 값을 새 값으로 대신하할 수도 있습니다. 혹은 예전 값을 계속 유지하면서 새 값은 무시하고, 해당 키에 값이 할당되지 않을 경우에만 새 값을 추가하는 방법을 선택할 수도 있습니다. 또는 예전 값과 새 값을 조합할 수도 있습니다. 각각의 경우를 어떻게 할지 살펴봅시다!

값을 덮어쓰기

만일 해쉬맵에 키와 값을 삽입하고, 그 후 똑같은 키에 다른 값을 삽입하면, 키에 연관지어진 값은 새 값으로 대신될 것입니다. 아래 Listing 8-24의 코드가 insert를 두 번 호출함에도, 해쉬맵은 딱 하나의 키/값 쌍을 담게 될 것인데 그 이유는 두 번 모두 블루 팀의 키에 대한 값을 삽입하고 있기 때문입니다:


# #![allow(unused_variables)]
#fn main() {
use std::collections::HashMap;

let mut scores = HashMap::new();

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

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

Listing 8-24: 특정한 키로 저장된 값을 덮어쓰기

이 코드는 {"Blue": 25}를 출력할 것입니다. 원래의 값 10은 덮어써졌습니다.

키에 할당된 값이 없을 경우에만 삽입하기

특정 키가 값을 가지고 있는지 검사하고, 만일 가지고 있지 않다면 이 키에 대한 값을 삽입하고자 하는 경우는 흔히 발생합니다. 해쉬맵은 이를 위하여 entry라고 하는 특별한 API를 가지고 있는데, 이는 우리가 검사하고자 하는 키를 파라미터로 받습니다. entry 함수의 리턴값은 열거형 Entry인데, 해당 키가 있는지 혹은 없는지를 나타냅니다. 우리가 옐로우 팀에 대한 키가 연관된 값을 가지고 있는지 검사하고 싶어한다고 해봅시다. 만일 없다면, 값 50을 합입하고, 블루팀에 대해서도 똑같이 하고 싶습니다. 엔트리 API를 사용한 코드는 아래의 Listing 8-25와 같습니다:


# #![allow(unused_variables)]
#fn main() {
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);
#}

Listing 8-25: entry 메소드를 이용하여 어떤 키가 값을 이미 갖고 있지 않을 경우에만 추가하기

Entry에 대한 or_insert 메소드는 해당 키가 존재할 경우 관련된 Entry 키에 대한 값을 반환하도록 정의되어 있고, 그렇지 않을 경우에는 파라미터로 주어진 값을 해당 키에 대한 새 값을 삽입하고 수정된 Entry에 대한 값을 반환합니다. 이 방법은 우리가 직접 로직을 작성하는 것보다 훨씬 깔끔하고, 게다가 빌림 검사기와 잘 어울려 동작합니다.

Listing 8-25의 코드를 실행하면 {"Yellow": 50, "Blue": 10}를 출력할 것입니다. 첫번째 entry 호출은 옐로우 팀에 대한 키에 대하여 값 50을 삽입하는데, 이는 옐로우 팀이 값을 가지고 있지 않기 떄문입니다. 두번째 entry 호출은 해쉬맵을 변경하지 않는데, 왜냐하면 블루 팀은 이미 값 10을 가지고 있기 때문입니다.

예전 값을 기초로 값을 갱신하기

해쉬맵에 대한 또다른 흔한 사용 방식은 키에 대한 값을 찾아서 예전 값에 기초하여 값을 갱신하는 것입니다. 예를 들어, Listing 8-26은 어떤 텍스트 내에 각 단어가 몇번이나 나왔는지를 세는 코드를 보여줍니다. 단어를 키로 사용하는 해쉬맵을 이용하여 해당 단어가 몇번이나 나왔는지를 유지하기 위해 값을 증가시켜 줍니다. 만일 어던 단어를 처음 본 것이라면, 값 0을 삽입할 것입니다.


# #![allow(unused_variables)]
#fn main() {
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);
#}

Listing 8-26: 단어와 횟수를 저장하는 해쉬맵을 사용하여 단어의 등장 횟수 세기

이 코드는 {"world": 2, "hello": 1, "wonderful": 1}를 출력할 것입니다. or_insert 메소드는 실제로는 해당 키에 대한 값의 가변 참조자 (&mut V)를 반환합니다. 여기서는 count 변수에 가변 참조자를 저장하였고, 여기에 값을 할당하기 위해 먼저 애스터리스크 (*)를 사용하여 count를 역참조해야 합니다. 가변 참조자는 for 루프의 끝에서 스코프 밖으로 벗어나고, 따라서 모든 값들의 변경은 안전하며 빌림 규칙에 위배되지 않습니다.

해쉬 함수

기본적으로, HashMap은 서비스 거부 공격(Denial of Service(DoS) attack)에 저항 기능을 제공할 수 있는 암호학적으로 보안되는 해쉬 함수를 사용합니다. 이는 사용 가능한 가장 빠른 해쉬 알고리즘은 아니지만, 성능을 떨어트리면서 더 나은 보안을 취하는 거래는 가치가 있습니다. 만일 여러분이 여러분의 코드를 프로파일하여 기본 해쉬 함수가 여러분의 목표에 관해서는 너무 느리다면, 다른 해쉬어(hasher) 를 특정하여 다른 함수로 바꿀 수 있습니다. 해쉬어는 BuildHasher 트레잇을 구현한 타입을 말합니다. 트레잇과 이를 어떻게 구현하는지에 대해서는 10장에서 다룰 것입니다. 여러분의 해쉬어를 바닥부터 새로 구현해야할 필요는 없습니다; crates.io에서는 많은 수의 범용적인 해쉬 알고리즘을 구현한 해쉬어를 제공하는 공유 라이브러리를 제공합니다.

정리

벡터, 스트링, 그리고 해쉬맵은 프로그램 내에서 여러분이 데이터를 저장하고, 접근하고, 수정하고 싶어하는 곳마다 필요한 수많은 기능들을 제공해줄 것입니다. 이제 여러분이 풀 준비가 되어있어야 할만한 몇가지 연습문제를 소개합니다:

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

표준 라이브러리 API 문서는 이 연습문제들에 대해 도움이 될만한 벡터, 스트링, 그리고 해쉬맵의 메소드들을 설명해줍니다!

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