เก็บคีย์พร้อมค่าที่เชื่อมโยงกันในแฮชแมป
คอลเลกชันพื้นฐานตัวสุดท้ายที่เราจะพูดถึงคือ แฮชแมป (hash map) โดยประเภท HashMap<K, V> จะเก็บการจับคู่ระหว่างคีย์ประเภท K กับค่าประเภท V โดยอาศัย ฟังก์ชันแฮช (hashing function) ซึ่งเป็นตัวกำหนดวิธีการจัดวางคีย์และค่าเหล่านี้ลงในหน่วยความจำ ภาษาโปรแกรมหลายภาษารองรับโครงสร้างข้อมูลแบบนี้ แต่มักเรียกด้วยชื่อที่ต่างกันไป เช่น hash, map, object, hash table, dictionary หรือ associative array
แฮชแมปมีประโยชน์เมื่อคุณต้องการค้นหาข้อมูลด้วยคีย์ (ซึ่งเป็นประเภทข้อมูลใดก็ได้) แทนที่จะค้นหาด้วยดัชนีเหมือนกับเวกเตอร์ ตัวอย่างเช่น ในเกม คุณสามารถใช้แฮชแมปเก็บคะแนนของแต่ละทีม โดยใช้ชื่อทีมเป็นคีย์ และคะแนนของทีมนั้นเป็นค่า เพียงแค่ระบุชื่อทีม คุณก็สามารถดึงคะแนนของทีมดังกล่าวออกมาได้ทันที
ในหัวข้อนี้เราจะแนะนำ API พื้นฐานของแฮชแมป แต่ยังมีฟังก์ชันและลูกเล่นอีกมากมายที่ไลบรารีมาตรฐานนิยามไว้สำหรับ HashMap<K, V> ซึ่งคุณสามารถดูรายละเอียดเพิ่มเติมได้จากเอกสารประกอบของไลบรารีมาตรฐานเช่นเคย
การสร้างแฮชแมปใหม่
วิธีหนึ่งในการสร้างแฮชแมปว่างเปล่าคือการเรียกใช้ new แล้วเพิ่มข้อมูลด้วย insert ในลิสติ้ง 8-20 เราจะเก็บคะแนนของสองทีมชื่อ Blue และ Yellow โดยทีม Blue เริ่มต้นด้วย 10 คะแนน และทีม Yellow เริ่มต้นด้วย 50 คะแนน
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);
}
สังเกตว่าเราจำเป็นต้อง use ตัว HashMap มาจากส่วนคอลเลกชันของไลบรารีมาตรฐานก่อน เพราะในบรรดาคอลเลกชันพื้นฐานทั้งสามชนิดนี้ แฮชแมปถูกใช้งานน้อยที่สุด จึงไม่ได้ถูกดึงเข้าสู่ขอบเขต (scope) โดยอัตโนมัติใน prelude นอกจากนี้ แฮชแมปยังได้รับการสนับสนุนจากไลบรารีมาตรฐานน้อยกว่า เช่น ไม่มีแมโครในตัวสำหรับสร้างแฮชแมปเหมือนกับ vec!
เช่นเดียวกับเวกเตอร์ แฮชแมปจัดเก็บข้อมูลไว้บนฮีป (heap) โดย HashMap ในตัวอย่างนี้มีคีย์เป็นประเภท String และค่าเป็นประเภท i32 และเฉกเช่นเดียวกับเวกเตอร์ ข้อมูลในแฮชแมปจะต้องเป็นประเภทเดียวกันทั้งหมด (homogeneous) นั่นคือ คีย์ทุกตัวจะต้องเป็นประเภทเดียวกัน และค่าทุกตัวก็จะต้องเป็นประเภทเดียวกันด้วย
การเข้าถึงค่าในแฮชแมป
เราสามารถดึงค่าออกจากแฮชแมปได้โดยส่งคีย์ของมันให้เมธอด get ดังที่แสดงในลิสติ้ง 8-21
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).copied().unwrap_or(0);
}
ในตัวอย่างนี้ ตัวแปร score จะได้รับค่าของทีม Blue ซึ่งผลลัพธ์คือ 10 โดยเมธอด get จะคืนค่าเป็น Option<&V> หากไม่มีคีย์ดังกล่าวอยู่ในแฮชแมป เมธอด get จะคืนค่า None โปรแกรมนี้จัดการกับ Option ดังกล่าวโดยการเรียกใช้ copied เพื่อเปลี่ยนจาก Option<&i32> ให้กลายเป็น Option<i32> (คัดลอกค่าออกมา) จากนั้นใช้ unwrap_or เพื่อกำหนดให้ score มีค่าเป็น 0 หาก scores ไม่มีคีย์นั้นอยู่
เราสามารถวนซ้ำผ่านคู่คีย์-ค่าทุกคู่ในแฮชแมปในลักษณะคล้ายกับที่เราทำกับเวกเตอร์ โดยใช้ลูป 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}");
}
}
โค้ดนี้จะพิมพ์แต่ละคู่ในลำดับใดก็ได้:
Yellow: 50
Blue: 10
การจัดการความเป็นเจ้าของในแฮชแมป
สำหรับประเภทข้อมูลที่อิมพลีเมนต์เทรต Copy อย่างเช่น i32 ค่าจะถูกคัดลอกเข้าไปยังแฮชแมป ส่วนประเภทข้อมูลที่ถือครองความเป็นเจ้าของอย่างเช่น String ค่าจะถูกย้าย (move) และแฮชแมปจะกลายเป็นเจ้าของค่าเหล่านั้นแทน ดังที่แสดงในลิสติ้ง 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!
}
เราจะไม่สามารถใช้งานตัวแปร field_name และ field_value ได้อีกต่อไปหลังจากที่พวกมันถูกย้ายเข้าไปในแฮชแมปด้วยการเรียก insert
หากเราแทรกเรเฟอเรนซ์ของค่าต่างๆ เข้าไปในแฮชแมป ตัวค่าเองจะไม่ถูกย้ายเข้าไปในแฮชแมป แต่ค่าที่เรเฟอเรนซ์นั้นชี้อยู่จะต้องมีอายุใช้งาน (valid) อย่างน้อยนานเท่ากับที่แฮชแมปยังคงใช้งานได้ เราจะพูดคุยเรื่องนี้กันอย่างละเอียดในหัวข้อ “การตรวจสอบความถูกต้องของเรเฟอเรนซ์ด้วยไลฟ์ไทม์” ในบทที่ 10
การอัปเดตแฮชแมป
แม้ว่าจำนวนคู่คีย์-ค่าในแฮชแมปจะเพิ่มขึ้นได้เรื่อยๆ แต่ละคีย์ที่ไม่ซ้ำกันสามารถเชื่อมโยงกับค่าได้เพียงค่าเดียวในเวลาเดียวกันเท่านั้น (แต่ไม่ใช่ในทางกลับกัน ตัวอย่างเช่น ทั้งทีม Blue และทีม Yellow ต่างก็อาจมีคะแนนเป็น 10 เก็บอยู่ในแฮชแมป scores ได้พร้อมกัน)
เมื่อคุณต้องการปรับเปลี่ยนข้อมูลในแฮชแมป คุณต้องตัดสินใจว่าจะจัดการอย่างไรเมื่อคีย์นั้นมีค่าถูกกำหนดไว้อยู่ก่อนแล้ว คุณอาจเลือกแทนที่ค่าเดิมด้วยค่าใหม่ไปเลยโดยไม่สนใจค่าเดิม หรือจะเก็บค่าเดิมไว้โดยไม่สนใจค่าใหม่ และจะเพิ่มค่าใหม่เข้าไปก็ต่อเมื่อคีย์นั้น ยังไม่มี ค่าอยู่ หรือคุณอาจเลือกที่จะรวมค่าเดิมเข้ากับค่าใหม่ มาดูวิธีการทำในแต่ละกรณีกัน!
การเขียนทับค่า
หากเราแทรกคีย์และค่าคู่หนึ่งลงในแฮชแมป แล้วแทรกคีย์เดิมซ้ำอีกครั้งด้วยค่าใหม่ ค่าเดิมที่ผูกกับคีย์นั้นจะถูกแทนที่ แม้ว่าโค้ดในลิสติ้ง 8-23 จะเรียก insert สองครั้ง แต่แฮชแมปจะมีคู่คีย์-ค่าเพียงคู่เดียวเท่านั้น เพราะเราแทรกค่าให้กับคีย์ของทีม Blue ทั้งสองครั้ง
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:?}");
}
โค้ดนี้จะพิมพ์ {"Blue": 25} ออกมา ซึ่งค่าเดิมที่เป็น 10 ได้ถูกเขียนทับไปแล้ว
การเพิ่มคีย์และค่าเฉพาะเมื่อยังไม่มีคีย์นั้น
การตรวจสอบว่าคีย์ใดคีย์หนึ่งมีอยู่ในแฮชแมปพร้อมกับค่าอยู่แล้วหรือไม่ แล้วดำเนินการตามเงื่อนไขต่อไปนี้ถือเป็นกรณีที่พบได้บ่อย: ถ้าคีย์นั้นมีอยู่ในแฮชแมปอยู่แล้ว ก็ให้คงค่าเดิมไว้เช่นนั้น แต่ถ้ายังไม่มีคีย์นั้นอยู่ ให้แทรกคีย์และค่าใหม่เข้าไป
แฮชแมปมี API พิเศษสำหรับงานนี้โดยเฉพาะชื่อว่า entry ซึ่งรับคีย์ที่คุณต้องการตรวจสอบเป็นพารามิเตอร์ ค่าที่ส่งกลับจากเมธอด entry คือ enum ชื่อ Entry ซึ่งเป็นตัวแทนของค่าที่อาจจะมีอยู่หรือไม่มีอยู่ก็ได้ สมมติว่าเราต้องการตรวจสอบว่าคีย์ของทีม Yellow มีค่าผูกอยู่แล้วหรือไม่ ถ้ายังไม่มี เราต้องการแทรกค่า 50 เข้าไป และทำแบบเดียวกันนี้กับทีม Blue เมื่อใช้ API entry โค้ดจะเขียนได้ดังลิสติ้ง 8-24
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:?}");
}
เมธอด or_insert บน Entry ถูกกำหนดมาให้คืนค่าเป็นเรเฟอเรนซ์แบบเปลี่ยนแปลงได้ไปยังค่าของคีย์ Entry นั้นหากมีคีย์ดังกล่าวอยู่แล้ว แต่ถ้ายังไม่มี มันจะแทรกค่าจากพารามิเตอร์เข้าไปเป็นค่าใหม่ของคีย์นี้ แล้วส่งคืนเรเฟอเรนซ์แบบเปลี่ยนแปลงได้ไปยังค่าใหม่นั้น เทคนิคนี้ช่วยให้โค้ดดูสะอาดตาขึ้นมากเมื่อเทียบกับการเขียนตรรกะตรวจสอบด้วยตัวเอง และยังทำงานร่วมกับตัวตรวจการยืม (borrow checker) ได้อย่างราบรื่นอีกด้วย
เมื่อรันโค้ดในลิสติ้ง 8-24 จะพิมพ์ {"Yellow": 50, "Blue": 10} ออกมา การเรียก entry ครั้งแรกจะแทรกคีย์ของทีม Yellow พร้อมค่า 50 เพราะทีม Yellow ยังไม่มีค่าอยู่ก่อน แต่การเรียก entry ครั้งที่สองจะไม่มีการเปลี่ยนแปลงใดๆ ในแฮชแมป เพราะทีม Blue มีค่าเป็น 10 อยู่แล้ว
การอัปเดตค่าจากค่าเดิม
อีกกรณีการใช้งานหนึ่งที่พบบ่อยสำหรับแฮชแมปคือ การค้นหาค่าของคีย์แล้วนำมาอัปเดตต่อยอดจากค่าเดิม ตัวอย่างเช่น ลิสติ้ง 8-25 แสดงโค้ดที่นับจำนวนครั้งที่แต่ละคำปรากฏในข้อความ โดยเราจะใช้แฮชแมปที่มีคำเป็นคีย์ และเพิ่มค่าตัวนับขึ้นเรื่อยๆ เพื่อติดตามว่าเราพบคำนั้นไปแล้วกี่ครั้ง หากเพิ่งเคยพบคำนั้นเป็นครั้งแรก เราจะแทรกค่าเริ่มต้นเป็น 0 เข้าไปก่อน
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:?}");
}
โค้ดนี้จะพิมพ์ {"world": 2, "hello": 1, "wonderful": 1} ออกมา ซึ่งคุณอาจเห็นคู่คีย์-ค่าเหล่านี้แสดงในลำดับที่ต่างไปจากนี้ได้: อย่าลืมว่าจากหัวข้อ “การเข้าถึงค่าในแฮชแมป” การวนซ้ำในแฮชแมปจะเกิดขึ้นในลำดับที่ไม่แน่นอน (arbitrary order)
เมธอด split_whitespace จะคืนค่าเป็นตัววนซ้ำ (iterator) บนสับสไลซ์ที่ถูกคั่นด้วยช่องว่างของข้อความใน text ส่วนเมธอด or_insert จะคืนค่าเป็นเรเฟอเรนซ์แบบเปลี่ยนแปลงได้ (&mut V) ไปยังค่าของคีย์ที่ระบุ ในที่นี้เราจัดเก็บเรเฟอเรนซ์แบบเปลี่ยนแปลงได้ดังกล่าวไว้ในตัวแปร count ดังนั้นหากต้องการกำหนดค่าใหม่ให้กับค่านั้น เราจะต้องดีเรเฟอเรนซ์ (dereference) count โดยใช้เครื่องหมายดอกจัน (*) เสียก่อน และเรเฟอเรนซ์แบบเปลี่ยนแปลงได้นี้จะหลุดออกจากขอบเขตเมื่อจบลูป for แต่ละรอบ การแก้ไขค่าทั้งหมดนี้จึงปลอดภัยและถูกต้องตามกฎการยืมทุกประการ
ฟังก์ชันแฮช
โดยค่าเริ่มต้น HashMap จะใช้ฟังก์ชันแฮชที่ชื่อว่า SipHash ซึ่งมีความสามารถในการป้องกันการโจมตีแบบปฏิเสธการให้บริการ (denial-of-service หรือ DoS) ที่พุ่งเป้าไปที่ตารางแฮช1 แม้นี่จะไม่ใช่อัลกอริทึมการแฮชที่เร็วที่สุด แต่ข้อแลกเปลี่ยนในเรื่องความปลอดภัยที่เพิ่มขึ้นเพื่อแลกกับประสิทธิภาพที่ลดลงเล็กน้อยนั้นถือว่าคุ้มค่า หากคุณทำโพรไฟล์ (profile) โค้ดแล้วพบว่าฟังก์ชันแฮชเริ่มต้นนี้ทำงานช้าเกินไปสำหรับความต้องการของคุณ คุณสามารถสลับไปใช้ฟังก์ชันอื่นได้โดยการระบุแฮชเชอร์ (hasher) ตัวอื่น โดย แฮชเชอร์ คือประเภทข้อมูลที่อิมพลีเมนต์เทรต BuildHasher ซึ่งเราจะพูดถึงเทรตและวิธีอิมพลีเมนต์เทรตใน บทที่ 10 และคุณไม่จำเป็นต้องเขียนแฮชเชอร์ขึ้นมาเองตั้งแต่ต้นเสมอไป เพราะบน crates.io มีไลบรารีที่ชุมชนผู้ใช้ Rust ร่วมกันแบ่งปัน ซึ่งมีแฮชเชอร์ที่อิมพลีเมนต์อัลกอริทึมแฮชยอดนิยมต่างๆ ไว้อย่างครบถ้วน
สรุป
เวกเตอร์, สตริง และแฮชแมปช่วยมอบความสามารถมากมายที่จำเป็นสำหรับโปรแกรมเวลาที่คุณต้องจัดเก็บ เข้าถึง และแก้ไขข้อมูล ต่อไปนี้คือแบบฝึกหัดที่คุณน่าจะพร้อมลงมือทำได้แล้วในตอนนี้:
- กำหนดรายการของจำนวนเต็มมาให้ ให้ใช้เวกเตอร์ในการหาและส่งคืนค่ามัธยฐาน (median ซึ่งเมื่อเรียงลำดับแล้วคือค่าที่อยู่ตำแหน่งกึ่งกลาง) และฐานนิยม (mode ซึ่งเป็นค่าที่ปรากฏบ่อยที่สุด โดยแฮชแมปจะมีประโยชน์มากในส่วนนี้) ของรายการนั้น
- แปลงข้อความสตริงเป็นภาษาพิกละติน (Pig Latin) โดยพยัญชนะตัวแรกของแต่ละคำจะถูกย้ายไปไว้ท้ายคำแล้วต่อท้ายด้วย -ay ดังนั้นคำว่า first จะกลายเป็น irst-fay ส่วนคำที่ขึ้นต้นด้วยสระ ให้เติม -hay ต่อท้ายแทน (เช่น apple จะกลายเป็น apple-hay) และอย่าลืมคำนึงถึงรายละเอียดเกี่ยวกับการเข้ารหัส UTF-8 ด้วย!
- ใช้แฮชแมปและเวกเตอร์เพื่อสร้างอินเทอร์เฟซแบบข้อความที่อนุญาตให้ผู้ใช้เพิ่มชื่อพนักงานเข้าสู่แผนกต่างๆ ของบริษัทได้ เช่น “Add Sally to Engineering” หรือ “Add Amir to Sales” จากนั้นเปิดให้ผู้ใช้สามารถเรียกดูรายชื่อพนักงานทั้งหมดในแผนกใดแผนกหนึ่ง หรือพนักงานทุกคนในบริษัทโดยจัดกลุ่มตามแผนก และเรียงลำดับตามตัวอักษร
เอกสาร API ของไลบรารีมาตรฐานมีคำอธิบายเมธอดต่างๆ ของเวกเตอร์ สตริง และแฮชแมป ซึ่งจะเป็นประโยชน์อย่างยิ่งสำหรับแบบฝึกหัดเหล่านี้!
จากนี้ไปเรากำลังจะก้าวเข้าสู่การเขียนโปรแกรมที่มีความซับซ้อนยิ่งขึ้น ซึ่งการทำงานต่างๆ อาจเกิดข้อผิดพลาดขึ้นได้ ดังนั้นจึงเป็นจังหวะที่เหมาะสมที่สุดที่เราจะมาพูดคุยกันถึงเรื่องการจัดการข้อผิดพลาด (error handling) ในบทถัดไป!