The Rust Programming Language — ฉบับแปลภาษาไทย

เก็บ Key พร้อมค่าที่ผูกกันด้วย Hash Map

Collection ที่ใช้บ่อยตัวสุดท้ายของเราคือ hash map type HashMap<K, V> เก็บการ map ของ key type K กับค่า type V โดยใช้ hashing function ซึ่งกำหนดว่ามันวาง key และค่าเหล่านี้ในหน่วยความจำอย่างไร ภาษาโปรแกรม หลายภาษารองรับโครงสร้างข้อมูลชนิดนี้ แต่มักใช้ชื่อต่าง เช่น hash, map, object, hash table, dictionary หรือ associative array เป็นต้น

Hash map มีประโยชน์เมื่อคุณอยาก lookup ข้อมูล ไม่ใช่โดยใช้ index อย่างที่ คุณทำได้กับ vector แต่โดยใช้ key ที่เป็น type ใดก็ได้ เช่น ในเกม คุณติด ตามคะแนนของแต่ละทีมใน hash map ได้ ที่แต่ละ key เป็นชื่อทีมและค่าเป็น คะแนนของแต่ละทีม เมื่อให้ชื่อทีม คุณดึงคะแนนได้

เราจะดู API พื้นฐานของ hash map ในส่วนนี้ แต่ของดีอีกมากซ่อนในฟังก์ชันที่ ประกาศบน HashMap<K, V> โดย standard library เช่นเคย เช็ค documentation ของ standard library สำหรับข้อมูลเพิ่มเติม

สร้าง Hash Map ใหม่

วิธีหนึ่งในการสร้าง hash map ว่างคือใช้ new และเพิ่ม element ด้วย insert ใน Listing 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 จากส่วน collection ของ standard library ก่อน จาก collection ที่ใช้บ่อยสามตัวของเรา ตัวนี้ใช้น้อยที่สุด มันจึงไม่รวมในฟีเจอร์ที่นำเข้า scope อัตโนมัติใน prelude Hash map ยังมี support จาก standard library น้อยกว่า — ไม่มี macro built-in สำหรับ สร้างพวกมัน เช่น

เหมือนกับ vector hash map เก็บข้อมูลบน heap HashMap นี้มี key type String และค่า type i32 เหมือนกับ vector hash map เป็น homogeneous — key ทั้งหมดต้องมี type เดียวกัน และค่าทั้งหมดต้องมี type เดียวกัน

เข้าถึงค่าใน Hash Map

เราดึงค่าออกจาก hash map ได้โดยให้ key ของมันกับเมธอด get ดังที่แสดง ใน Listing 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 return Option<&V> — ถ้าไม่มีค่าสำหรับ key นั้นใน hash map get จะ return None โปรแกรมนี้จัดการ Option โดยเรียก copied เพื่อรับ Option<i32> แทน Option<&i32> แล้ว unwrap_or set score เป็นศูนย์ ถ้า scores ไม่มี entry สำหรับ key

เรา iterate ผ่านแต่ละคู่ key-value ใน hash map ได้ในแบบคล้ายที่เราทำกับ vector โดยใช้ for loop:

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

จัดการ Ownership ใน Hash Map

สำหรับ type ที่ implement trait Copy อย่าง i32 ค่าถูกคัดลอกเข้า hash map สำหรับค่าที่ owned อย่าง String ค่าจะถูก move และ hash map จะเป็น owner ของค่าเหล่านั้น ดังที่แสดงใน 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!
}

เราใช้ตัวแปร field_name และ field_value ไม่ได้หลังจากพวกมันถูก move เข้า hash map ด้วยการเรียก insert

ถ้าเราแทรก reference ของค่าเข้า hash map ค่าจะไม่ถูก move เข้า hash map ค่าที่ reference ชี้ไปต้อง valid อย่างน้อยตราบที่ hash map valid เราจะ พูดถึงปัญหาเหล่านี้เพิ่มใน “ตรวจสอบ Reference ด้วย Lifetime” ในบทที่ 10

Update Hash Map

แม้จำนวนคู่ key และค่าจะเติบโตได้ แต่ละ key ที่ไม่ซ้ำมีค่าผูกอยู่ได้แค่ ค่าเดียวในเวลาเดียว (แต่ไม่ตรงข้าม — เช่น ทั้งทีม Blue และทีม Yellow มี ค่า 10 เก็บใน hash map scores ได้)

เมื่อคุณอยากเปลี่ยนข้อมูลใน hash map คุณต้องตัดสินใจวิธีจัดการกรณีที่ key มีค่า assign อยู่แล้ว คุณแทนค่าเดิมด้วยค่าใหม่ ละเลยค่าเดิมโดย สมบูรณ์ได้ คุณเก็บค่าเดิมและละเว้นค่าใหม่ เพิ่มค่าใหม่เฉพาะถ้า key ยังไม่ มีค่าได้ หรือคุณรวมค่าเดิมและค่าใหม่ได้ มาดูวิธีทำแต่ละอย่าง!

เขียนทับค่า

ถ้าเราแทรก key และค่าเข้า hash map แล้วแทรก key เดียวกันด้วยค่าต่าง ค่า ที่ผูกกับ key นั้นจะถูกแทน แม้โค้ดใน Listing 8-23 เรียก insert สอง ครั้ง hash map จะมีแค่หนึ่งคู่ key-value เพราะเรากำลังแทรกค่าสำหรับ key ของทีม 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 ถูกเขียนทับ

เพิ่ม Key และค่าเฉพาะถ้า Key ไม่มีอยู่

มันใช้บ่อยที่จะเช็คว่า key เฉพาะมีอยู่แล้วใน hash map พร้อมค่า แล้วทำ action ต่อไปนี้ — ถ้า key มีอยู่ใน hash map ค่าที่มีอยู่ควรอยู่เหมือนเดิม ถ้า key ไม่มี แทรกมันและค่าสำหรับมัน

Hash map มี API พิเศษสำหรับเรื่องนี้ชื่อ entry ที่รับ key ที่คุณอยาก เช็คเป็น parameter Return value ของเมธอด entry คือ enum ชื่อ Entry ที่แทนค่าที่อาจมีหรือไม่มี สมมติเราอยากเช็คว่า key สำหรับทีม Yellow มี ค่าผูกกับมันไหม ถ้าไม่ เราอยากแทรกค่า 50 และเหมือนกันสำหรับทีม Blue ด้วย API entry โค้ดดูเหมือน Listing 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 ประกาศให้ return mutable reference ของค่า สำหรับ key Entry ที่สอดคล้องถ้า key นั้นมีอยู่ และถ้าไม่ มันแทรก parameter เป็นค่าใหม่สำหรับ key นี้ และ return mutable reference ของ ค่าใหม่ เทคนิคนี้สะอาดกว่าการเขียน logic เองมาก และเพิ่มเติม เล่นได้ดี ขึ้นกับ borrow checker

การรันโค้ดใน Listing 8-24 จะพิมพ์ {"Yellow": 50, "Blue": 10} การเรียก entry ครั้งแรกจะแทรก key สำหรับทีม Yellow ด้วยค่า 50 เพราะทีม Yellow ยังไม่มีค่า การเรียก entry ครั้งที่สองจะไม่เปลี่ยน hash map เพราะทีม Blue มีค่า 10 อยู่แล้ว

Update ค่าตามค่าเดิม

อีก use case ที่ใช้บ่อยสำหรับ hash map คือ lookup ค่าของ key แล้ว update ตามค่าเดิม เช่น Listing 8-25 แสดงโค้ดที่นับว่าแต่ละคำปรากฏกี่ครั้งใน ข้อความ เราใช้ hash map ที่มีคำเป็น key และ increment ค่าเพื่อติดตามว่า เราเห็นคำนั้นกี่ครั้ง ถ้าเป็นครั้งแรกที่เห็นคำ เราจะแทรกค่า 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} คุณอาจเห็นคู่ key-value เดียวกันพิมพ์ในลำดับต่างกัน — จำได้จาก “เข้าถึงค่าใน Hash Map” ว่าการ iterate ผ่าน hash map เกิดในลำดับสุ่ม

เมธอด split_whitespace return iterator บน subslice ที่คั่นด้วย whitespace ของค่าใน text เมธอด or_insert return mutable reference (&mut V) ของค่าสำหรับ key ที่ระบุ ที่นี่เราเก็บ mutable reference นั้น ในตัวแปร count ดังนั้นในการ assign ให้ค่านั้น เราต้อง dereference count โดยใช้ asterisk (*) ก่อน Mutable reference ออกจาก scope ที่ท้าย for loop การเปลี่ยนเหล่านี้ทั้งหมดจึงปลอดภัยและกฎ borrowing อนุญาต

Hashing Function

โดย default HashMap ใช้ hashing function ชื่อ SipHash ที่ให้การ ต้านทาน denial-of-service (DoS) attack ที่เกี่ยวกับ hash table¹ นี่ไม่ใช่ hashing algorithm ที่เร็วที่สุด แต่ trade-off สำหรับ security ที่ดีกว่าที่มากับการลด performance คุ้มค่า ถ้าคุณ profile โค้ดและพบว่า default hash function ช้าเกินไปสำหรับจุด ประสงค์ของคุณ คุณเปลี่ยนเป็นฟังก์ชันอื่นได้โดยระบุ hasher ต่าง hasher คือ type ที่ implement trait BuildHasher เราจะพูดถึง trait และวิธี implement ใน บทที่ 10 คุณไม่จำเป็นต้อง implement hasher ของคุณเองจากศูนย์ crates.io มี library ที่แชร์โดย user Rust อื่นที่ให้ hasher ที่ implement hashing algorithm ที่ใช้บ่อยหลายตัว

สรุป

Vector, string และ hash map จะให้ functionality มากที่จำเป็นในโปรแกรม เมื่อคุณต้องเก็บ เข้าถึง และแก้ข้อมูล นี่คือแบบฝึกหัดที่ตอนนี้คุณควร แก้ได้:

1. ให้ list ของ integer ใช้ vector และ return median (เมื่อเรียง ค่าใน ตำแหน่งกลาง) และ mode (ค่าที่เกิดบ่อยที่สุด — hash map จะช่วยตรงนี้) ของ list
2. แปลง string เป็น Pig Latin พยัญชนะแรกของแต่ละคำถูกย้ายไปท้ายคำ และ เพิ่ม ay ดังนั้น first กลายเป็น irst-fay คำที่ขึ้นต้นด้วยสระ เพิ่ม hay ที่ท้ายแทน (apple กลายเป็น apple-hay) จำรายละเอียด เกี่ยวกับ UTF-8 encoding ไว้!
3. ใช้ hash map และ vector สร้าง text interface ให้ user เพิ่มชื่อพนัก งานเข้าแผนกในบริษัทได้ เช่น “Add Sally to Engineering” หรือ “Add Amir to Sales” จากนั้นให้ user ดึง list ของคนทั้งหมดในแผนก หรือคน ทั้งหมดในบริษัทแยกตามแผนก เรียงตามตัวอักษร

API documentation ของ standard library อธิบายเมธอดที่ vector, string และ hash map มี ที่จะช่วยกับแบบฝึกหัดเหล่านี้!

เรากำลังเข้าสู่โปรแกรมที่ซับซ้อนขึ้นที่ operation ล้มเหลวได้ ดังนั้นเป็น เวลาที่สมบูรณ์แบบที่จะพูดถึงการจัดการ error เราจะทำเรื่องนั้นต่อไป!

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