Lưu trữ cặp keys/value sử dụng Hash Maps

Lưu trữ key/value trong Hash Maps

Phần cuối của các collections phổ biến là hash map. Kiểu HashMap<K,V> lưu trữ một liên kết giữa các Key có kiểu K tới giá trị của nó với kiểu V sử dụng một hàm hashing (hashing function). Nhiều ngôn ngữ lập trình hỗ trợ cấu trúc dữ liệu này nhưng chúng thường sử dụng tên khác như hash, map (trong Go), hash table, dictionary, hoặc associative array... Kiểu Hash maps là hữu dụng khi bạn muốn to tìm kiềm dữ liệu với một key với dữ liệu bất ký, không phải sử dụng index giống bạn làm với Vector. Ví dụ: trong một game, bạn có thể giữ dấu vết của điểm mỗi đội trong một hash map nơi mỗi Key là tên của mỗi đội, và giá trị của nó là điểm của mỗi đội. Khi biết tên của đội, bạn có thể truy vấn điểm của đội đó.

Chúng ta sẽ đi qua những hàm cơ bản của hash maps trong chương này, nhưng nhiều thứ là ẩn đấu trong những hàm được định nghĩa `HashMap<K,V> bởi thư viện chuẩn. Kiểm tra tài liệu thư viện chuẩn bất cứ khi nào bạn muốn tìm kiếm nhiều thông tin hơn.

Tạo mới một Hash Map

Một cách để tạo một Hash Map rỗng là sử dụng hàm new và thêm thành với mới bằng hàm insert. Trong Listing 8-20, chúng sẽ theo dấu của 2 dội nơi tên của họ là Blue và Yellow. Đội Blue bắt đầu với 10 điểm, và đội Yellow bắt đầu với 50

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: Tạo mới một Hash Map và chèn một keys/values

Chú ý rằng, Đầu tiên chúng ta cần sử dụng HashMap từ phần trong collections của bộ thư viện chuẩn. Trong 3 collections phổ biến, thì đây là một cấu trúc ít được dùng nhất. Nó không bao gồm nhiều tính năng lúc đầu Hashmap cũng có ít hỗ trợ trong thư viện chuẩn, không có kiều macro built-in (macro sẵn) để tạo chúng.

Cũng giống như Vector, Hash Map lưu trữ dữ liệu trong vùng heap. HashMap có các keys của String và giá trị là kiểu i32. Giống như vector, hash map là đồng nhất, nghĩa là tất cả keys phải có cùng một kiểu dữ liệu giống nhau và giá trị của chúng cũng phải như vậy

Một cách khác để khởi tạo một hash map là sử dụng iterators (bộ duyệt) và phương thức collect một vector của tuples, nơi mà mỗi tuple bao gồm một key và giá trị của nó. Chúng ta sẽ chi tiết về iterators và các phương thức liên kết của nó trong ”Xử lý items với Iterator” trong chương 13 Phương thức collect thu thập dữ liệu thành một số kiểu collections bao gồm trong đó có HashMap. Ví dụ, nếu chúng có tên team, và giá trị điểm khởi tạo trong 2 vector riêng rẽ, chúng ta có thể sử dụng hàm zip để tạo một iterator của tupple nơi "Blue" là liên kết với 10, và ngược lại. Sau đó, chúng ta có thể sử dụng phương thức collect to biến iterator của tupple thành hash map như chỉ ra trong Listing 8-21

fn main() {
    use std::collections::HashMap;

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

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

Listing 8-21: Tạo một hash map từ danh sách team và danh sach các điểm

Ký hiệu HashMap<_, _> là cần thiết ở đây bởi nó có khả năng để collect thành nhiều cấu trúc dữ liệu khác nhau và Rust không biết kiểu mà chúngt a muốn trừ khi chúng ta chi tiết nó. Cho tham số key và giá trị, tuy hiên, chúng ta có thể sử dụng ký tự "_" và Rust có thể ngầm hiểu kiểu mà Hash map bao gồm dựa trên kiểu cảu dữ liệu trong Vector. Trong Listing 8-21, Kiểu dữ liệu key là String và kiểu giá trị là i32, như trong Listing 8-20

Hash Map và Quyền sở hữu (Hash Maps and Ownership)

Cho những kiểu mà thực hiện Copy trait, giống như i32, các giá trị được copy vào thành hash map. Cho giá trị có quyền sở hữu (owned) giống như String, giá trị sẽ được chuyển và hashmap sẽ là owner của các giá trị này, như demo trong Listing 8-22

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 and field_value are invalid at this point, try using them and
    // see what compiler error you get!
}

Listing 8-22: Key và gía trị là được sở hữu bởi hash map khi chúng được chèn

Chúng ta đã không có thể sử dụng biến field_name và field_value sau khi chúng ta đã chuyển vào hash map với lời gọi hàm insert.

Nếu chúng ta chèn các tham chiếu tới giá trị trong hash map, các giá trị sẽ không bị chuyển vào hash map. Giá trị mà các tham chiếu trỏ tới phải hợp lệ ít nhất miễn là hash map là hợp lệ. Chúng ta sẽ nói nhiều về vấn đề trong chương "Validate tham chiếu với Lifetimes" mục trong chương 10.

Truy xuất giá trị trong Hash Map

Chúng ta có thể lấy một gía trị từ hash map by cung cấp key tới hàm get, như chỉ ra trong Listing 8-23

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: Truy xuất tới điểm số của đội Blue trong hash map

Ở đây, score sẽ có giá trị mà đã liên với Blue team, và kết quả sẽ trả về Some(&10). Kết quả là được bọc trong Some bởi get trở lên Options<&V>; nếu không có giá trị cho key này trong hash map get sẽ trở về None. Chương trình sẽ cần để xử lý Option một trong các cách chúng ta đã bao qua trong Chương 6.

Chúng ta có thể duyệt qua mỗi cặp key/value trong một hash map tương tự giống như trong Vector sử dụng for:

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

Đoạn code này sẽ in ra mỗi cặp trong thứ tự tuỳ ý:

Yellow: 50
Blue: 10

Cập nhật một HashMap

Mặc dù số key và gía trị là có thể nhiều vô hạn, mỗi key chỉ có một giá trị liên với nó tại một thời điểm. Khi bạn muốn thay đổi dữ liệu trong một hahs map, bạn phải quyết định cách để xử lý khi một key đã có một giá trị liên kết. Bạn có thể thay thế giá trị cũ với giá trị mới bất kể giá trị cũ. Bạn có thể giữ giá trị cũ và tránh giá trị mới, chỉ thêm giá trị mới nếu key là không tồn tại. Hoặc bạn có thể kết hợp giá trị cũ vf giá trị mới.

Ghi đè một gía trị

Nếu chúng ta chèn một key và giá trị vào một hash map và sau đó chèn cũng key đó với giá trị khác, giá trị liên kết với key này sẽ được thay thế. Mặc dù code trong Listing 8-23 gọi insert 2 lần, hash map sẽ chỉ bao gồm 1 cặp key/value bởi vì chúng đang chèn giá chỉ cho Blue team 2 lần.

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: Thay thế một giá trị lưu trữ với key cụ thể

Đoạn code này sẽ in {"Blue": 25}. Giá trị gốc 10 sẽ bị ghi đề.

Chỉ chèn một giá trị nếu key không tồn tại

Thônng thường để check liệu một key cụ thể có giá trị hay không để chúng ta chèn nó. Hash map có một API cụ thể cho nó gọi là entry mà nhận key mà bạn muốn để kiểm tra. Giá trị trả về của phương thức entry là một enum gọi là Entry mà thể hiện giá trị có thể có hoặc không?

Nếu chúng ta muốn kiểm tra key cho đội Yello có giá trị liên kết đến nó không. Nếu không, chúng ta muốn chen giá trị 50. Sử dụng entry API. Sử dụng entry API, code sẽ giống Listing 8-25

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: Sử dụng phương thức entry để chỉ chèn nếu key là chưa có giá trị liên kết tới

Phương thức or_insert trong Entry là được định nghĩa để trả về một tham chiếu mutable (có thể thay đổi) tới giá trị tương ứng Entry key nếu key này tồn tại, hoặc nếu không, chèn tham số như giá trị mới tới key và trở v về một tham chiếu mutable tới giá trị mới này. Kỹ thuật này là rõ ràng hơn viết logic, thêm vào đó, chúng ta có borrow checker (một chương trình kiểm tra luật mượn) hỗ trợ.

Chạy code trong Listing 8-25 sẽ in ra {"Yellow": 50, "Blue": 10}. Lời gọi hàm đầu tiên entry sẽ chèn key cho Yellow team với giá trị 50 bởi vì Yellow team khong có giá trị trước đó. Lời gọi thứ 2 entry sẽ không thay đổi hash map bởi vì Blue team đã có giá trị 10.

Cập nhật giá trị dựa trên giá trị cũ

Một cách khác cho hash map là tìm kiếm giá trị của một key và sau đó cập nhật giá trị này, Ví dụ, Listing 8-26 đếm số lần mỗi từ xuất hiện trong text. Chúng ta sử dụng hash map với các từ như là các key và giá trị liên kết với key đó là số lần từ đó xuất hiện. Nếu là lần đầu tiên chúng ta nhìn thấy từ, chúng ta sẽ chèn nó với giá trị là 1.

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: Đếm số lần xảy ra của các từ sử dụng hash map

Đoạn code này sẽ in ra {"world": 2, "hello": 1, "wonderful": 1}. Phương thức split_whitespace duyệt qua tất các slice con, chia chúng ra bằng khoảng trắng. Phương thức or_insert trở về một tham chiếu mutable (&mut V) tới giá trị key đó. Ở đây, chúng ta lưu trữ tham chiếu mutable trong biến count, nên, để có thể gán tới giá trị này, chúng ta phải dereference (lấy giá trị) count sử dụng ký hiệu (*). Tham chiếu mutable vượt sẽ ra ngoài phạm vị khi kết thúc hàm for, do đó tất cả sự thay đổi là an toàn và được cho phép bởi luật borrowing

Hàm Băm (Hashing Functions)

Bởi mặc định, HashMap sử dụng một hàm Hashing (hàm Băm) gọi là SipHash mà có thể cung cấp trở ngại tới những tấn công như DoS(Denial of Service) liên quan tới bảng băm ¹. Điều này không phải là thuật toán băm nhanh nhất, nhưng đánh đổi hiệu năng cho bảo mật tốt hơn là đáng. Nếu bạn xem xét thời gian xử lý code, và thấy rằng hàm băm mặc định là qúa chậm cho mục đích của bạn, bạn có thể thay đổi hàm khác bải chi tiết một hasher khác. Một hasher là một kiểu mà thực hiện một BuildHasher trait. Chúng ta sẽ nói về trait và cách để thực hiện chúng trong Chương 10. Bạn không cần thiết phải thực hiện hasher của mình trừ đầu. Nhớ rằng thư viện thực hiện có thể tìm thấy trong crates crates.io

https://en.wikipedia.org/wiki/SipHash

Tổng kết

Vector, String, và hash maps sẽ cung cấp một số lượng lớn chức năng cần thiết trong chương trình khi bạn cần để lưu trữ, truy xuất, và chỉnh sửa dữ liệu. Có một số ví dụ bài tập bạn nên trang bị để giải quyết:

Danh sách số nguyên, sử dụng một vector và trở về thành phần ở chính giữa the (media) và mode(giá trị mà thường xuất hiện nhiều nhất - hash map có thể giải quyết
Biến đổi strings tới latin pig. Phụ âm đầu của mỗi từ là chuyển tới cuối và thêm "ay", do đó, "first" trở thành "irst-fay". Những từ bắt đầu với một nguyên âm sẽ thêm "hay" tới cuối (Ví dụ: "apple" sẽ thành "apple-hay"). Nhớ rằng UTF-8
Sử dụng một hash map và vector, tạo một giao diện cho phép người dùng có thể thêm tên nhân viên tới một phòng ban trong công ty. Ví dụ "Add Sally tới Engineering" hoặc "Thêm Amir tới Sales". Sau đó để người dùng lays một danh sách tất cả người trong một phòng bạn hoặc tất cả người trong công ty bởi phòng ban sắp xếp theo thứ alphabet

Tài liệu API của thư viện chuẩn mô tả các phương thức mà vectors, string và hash maps có và sẽ hữu ích cho bài tập này.

Chúng ta đang đi sâu vào chương trình phức tạp, nơi các điều khiển có thể lỗi, do đó, giờ là lúc thao thuận nhiều về xử lý lỗi. Chúng ta sẽ làm điều này trong chương tiếp theo

Ngôn ngữ lập trình Rust