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 1. Đ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
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