[Rust] 6. HashMap, BTreeMap

이전에 본 Index와 IndexMut는 이상적이지 않다.

왜냐하면 id로 전체 Vec를 iterate해야하기 때문에,

시간복잡도는 O(n)이다.

 

따라서 tickets를 저장하는 다른 자료구조를 사용할 것이다.

그것이 HashMap<K, V>다.

use std::collections::HashMap;

// Type inference lets us omit an explicit type signature (which
// would be `HashMap<String, String>` in this example).
let mut book_reviews = HashMap::new();

book_reviews.insert(
    "Adventures of Huckleberry Finn".to_string(),
    "My favorite book.".to_string(),
);

 

HashMap은 key-value의 pair로 되어있다.

K는 key type에 대한 generic parameter고,

V는 value type에 대한 generic parameter다.

 

삽입, 접근, 제거에 대한 cost가 모두 O(1)로 동일하다.

 

---

 

HashMap의 구조체 정의에 trait bounds가 없지만,

몇몇 methods에 있다.

예를 들어 insert는 다음과 같다.

// Slightly simplified
impl<K, V> HashMap<K, V>
where
    K: Eq + Hash,
{
    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
        // [...]
    }
}

 

key type은 Eq과 Hash traits를 implement해야한다.

 

---

 

HashMap은 hashing function을 사용하며,

key를 hash하고 key와 관련된 value를 저장하거나 반환할 때 key를 사용한다.

이는 key type이 hashable해야한다는 것을 의미한다.

그래서 Hash trait bound가 K에 있는 것이다.

 

std::hash의 Hash trait은 다음과 같다.

pub trait Hash {
    // Required method
    fn hash<H>(&self, state: &mut H)
       where H: Hasher;
}

 

Hash를 직접 implement할 일은 거의 없을 것이다.

대부분 아래와 같이 derive한다.

#[derive(Hash)]
struct Person {
    id: u32,
    name: String,
}

---

HashMap은 equality에 대한 keys의 비교를 해야한다.

이는 hash collisions를 다룰 때, 매우 중요하다.

hash collisions는 서로다른 두개의 key가 같은 value를 hash할 때, 일어난다.

 

그럼 PartialEq trait만 derive하면 되는거 아닌가?

PartialEq는 reflexivity를 보장하지 않기 때문에, HashMap에 적합하지 않다.

reflexivity는 자기가 자기 자신과 비교할 때, 항상 같은 것이다.

이는 floating point numbers의 경우에서 확인할 수 있다.

 

Reflexivity는 HashMap에서 매우 중요하다.

같은 key를 사용해 접근하는데 서로 다른 결과가 나오면 치명적이지 않을까?

 

Eq trait은 marker trait이다.

다른 어떤 새로운 methods를 추가하지 않는다.

그저 compiler에게 PartialEq의 equality logic이 reflexive하다고 알려주는 것이다.

 

pub trait Eq: PartialEq {
    // No additional methods
}

 

PartialEq를 derive할 때, 자동으로 Eq을 다음과 같이 derive할 수 있다.

#[derive(PartialEq, Eq)]
struct Person {
    id: u32,
    name: String,
}

 

---

 

Eq과 Hash 사이에는 보이지 않는 계약이 있다.

만약 두 개의 key가 같다면, 그것들의 hash들도 같아야한다.

이는 HashMap이 올바르게 동작하는데 매우 중요하다.

만약 이 계약을 깬다면, HashMap을 사용할 때, 이해되지 않는 결과를 얻을 것이다.

 

---

15_hashmap exercise는 Vec로 되어있던 tickets를

HashMap으로 바꾸는 것이었다.

그에 따라 methods도 바꾸었고 잘 통과했다.

---

Vec는 넣은 순서대로 iterate했지만, HashMap은 순서가 없다.

 

HashMap을 BTreeMap으로 바꾸면서, 일관된 ordering을 할 수 있다.

 

---

 

BTreeMap은 entry들이 key를 통해 sort되는 것을 보장한다.

특정한 순서로 entry들을 iterate할 때나,

range query(ex. 10에서 20사이의 id를 가진 모든 ticket을 줘)들을 수행할 때 유용하다.

 

HashMap과 같이, BTreeMap의 정의에서 trait bounds를 찾을 수 없고,

methods에서 찾을 수 있다.

insert를 보자.

// `K` and `V` stand for the key and value types, respectively,
// just like in `HashMap`.
impl<K, V> BTreeMap<K, V> {
    pub fn insert(&mut self, key: K, value: V) -> Option<V>
    where
        K: Ord,
    {
        // implementation
    }
}

 

Hash는 더 이상 필요하지 않다.

대신, key type이 Ord trait을 implement해야한다.

 

---

 

Ord trait은 value들을 compare할 때 사용된다.

PartialEq이 equality에 대한 비교를 할 때, 사용되는 반면,

Ord는 ordering에 대한 비교를 할 때, 사용된다.

 

Ord는 std::cmp에 정의되어있다.

pub trait Ord: Eq + PartialOrd {
    fn cmp(&self, other: &Self) -> Ordering;
}

 

cmp method는 Less, Equal, Greater의 Ordering enum을 return한다.

Ord는 Eq과 PartialOrd의 implement를 요구한다.

 

---

 

PartialEq이 Eq의 약한 버전인 것처럼,

PartialOrd는 Ord의 약한 버전이다.

pub trait PartialOrd: PartialEq {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering>;
}

 

PartialOrd::partial_cmp는 Option을 return한다.

이는 두 value가 compare된다는 것을 보장하지는 못한다.

예를 들어, f32는 NaN value들이 comparable하지 않기 때문에,

Ord를 implement하지 않는다.

같은 이유로, f32는 Eq를 implement하지 않는다.

 

---

 

Ord와 PartialOrd는 특정 type에 derive할 수 있다.

// You need to add `Eq` and `PartialEq` too,
// since `Ord` requires them.
#[derive(Eq, PartialEq, Ord, PartialOrd)]
struct TicketId(u64);

 

만약, 직접 implement한다면, 다음을 주의해라.

• (Ord와 PartialOrd)의 같다고 판단되는 결과는 (Eq과 PartialEq)과 일치해야한다.
• Ord와 PartialOrd의 같다고 판단되는 결과는 서로 일치해야한다.

즉, 위에서 서로의 동작이 일치해야한다는 것을 의미한다.

 

---

16_btreemap exercise는 HashMap을 BTreeMap으로 바꾸고

IntoIterator를 implement하는 것이었다.

IntoIterator를 implement할 때, reference에 대한 것이므로,

유효기간 설정을 해줘야했고,

이는 GPT의 도움을 받았다..

 

그래서 잘 통과했다.

 

---

 

GPT가 설명도 잘하고.. 선생님이다.