[Chapter 8-3] Rust 해쉬맵(hash map)

Hash map

HashMap<K, V> 타입은 K 타입의 키에 V 차입의 값을 매핑한 것을 저장합니다. 매핑은 해쉬 함수(hashing function)을 통해 동작하며, 해쉬 함수는 키와 값을 메모리 어디에 저장할지 결정합니다. 해쉬맵은 임의의 타입으로 된 키를 이용해 데이터를 찾길 원할 때 유용합니다.

새로운 Hash map 생성

new 를 이용해 빈 해쉬맵을 생성할 수 있고, insert 를 이용해 요소를 추가할 수 있습니다.

use std::collections::HashMap;

let mut scores = HashMap::new();

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

사용 전에 표준 라이브러리의 컬렉션 부분으로부터 HashMap 을 use 로 가져와야합니다.

벡터와 마찬가지로 해쉬맵도 데이터를 힙에 저장하며 동질적입니다. 모든 키는 같은 타입이어야 하며 모든 값도 같은 타입이어야 합니다. 위 코드의 HashMap 은 String 타입의 키와 i32 타입의 값을 갖습니다.

튜플의 벡터에 대해 collect 메소드를 사용해 해쉬맵을 사용할 수도 있습니다. collect 메소드는 데이터를 모아 HashMap 을 포함한 여러 컬렉션 타입으로 만들어줍니다.

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();

두 개의 분리된 벡터에 각각 String과 i32 값을 갖고 있다면, zip 메소를 이용해 "Blue"와 10이 한 쌍이 되는 식으로 튜플의 벡터를 생성할 수 있습니다. 그 후 collect 메소드를 사용해 튜플의 벡터를 HashMap 으로 바꿀 수 있습니다.

타입 명시 HashMap<_, _> 은 collect 가 다른 많은 데이터 구조 중 HashMap으로 특정해주기 위해 사용해주어야 합니다. 키와 값의 타입에 대한 타입 파라미터에 대해서는 밑줄을 사용할 수 있습니다.

HashMap과 소유권

i32 와 같이 Copy 트레잇을 구현한 타입에 대해서는 값들이 해쉬맵 안으로 복사됩니다. 하지만 String 과 같이 소유된 값들에 대해서는 값들이 이동되어 해쉬맵이 소유권을 갖게 됩니다.

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는 이 지점부터 유효하지 않습니다.

만일 해쉬맵에 값들의 참조자들을 삽입한다면, 소유권은 해쉬맵으로 이동되지 않습니다. 하지만 참조자가 가리키고 있는 값은 해쉬맵이 유효할 때까지 계속 유효해야합니다.

HashMap 내의 값 접근

해쉬맵의 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);

결과값은 Some(&10) 입니다. Some으로 감싸져있는 이유는 get이 Option<&V>를 반환하기 때문입니다. 만일 해쉬맵 내에 해당 키에 대한 값이 없다면 None을 반환합니다.

벡터와 유사하게 해쉬맵에서도 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

HashMap 갱신

값 덮어쓰기

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}

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

특정 키가 값을 가지고 있는지 검사하고, 가지고 있지 않는 경우에만 값을 삽입하고자 하는 경우를 위해 해쉬맵은 entry 라고 하는 특별한 API를 제공합니다. 검사하고자 하는 키를 파라미터로 받고 해당 키가 있는지 없는지를 나타내는 열거형 Entry를 return 해줍니다.

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 메소드는 해당 키가 존재할 경우 관련된 Entry 키에 대한 값을 반환하고, 키가 존재하지 않을 경우에는 파라미터로 주어진 값을 새로운 키와 새 값으로 삽입하고 수정된 Entry에 대한 값을 반환합니다.

해당 방법은 직접 로직을 작성하는 것보다 훨씬 깔끔하고 borrow checker(빌림 검사기)와 잘 어울려 동작합니다.

위 코드의 출력 결과는 {"Yellow": 50, "Blue": 10}입니다.

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

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_insesrt(0);
	*count += 1;
}

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

출력: {"world": 2, "hello": 1, "wonderful": 1}

or_insert 메소드는 키에 대한 값의 가변 참조자(&mut V)를 반환합니다. count 변수에 가변 참조자를 저장하였고 여기에 값을 할당하기 위해 *를 사용해 count를 역참조하여야 합니다. 가변 참조자는 for 루프의 끝에서 스코프 밖으로 벗어나므로 모든 값들의 변경은 안전하며 borrow 규칙에 위배되지 않습니다.

Hash Function

기본적으로 HashMap은 Dos attack에 저항 기능을 제공할 수 있는 보안되는 해쉬 함수를 사용합니다. 이는 사용 가능한 가장 빠른 해쉬 알고리즘은 아니지만, 성능 대신 보안을 취합니다. 만약 더 빠른 성능을 원한다면 다른 hasher를 특정하여 다른 함수로 바꿀 수 있습니다. hasher는 BuildHasher 트레잇을 구현한 타입을 말합니다. crates.io에서는 많은 수의 범용적인 해쉬 알고리즘을 구현한 해쉬어를 제공하는 공유 라이브러리를 제공합니다.