The Rust Programming Language

การจัดเก็บคีย์คู่กับค่าที่เกี่ยวข้องในแฮชแมป (Storing Keys with Associated Values in Hash Maps)

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

แฮชแมปจะมีประโยชน์มากเมื่อคุณต้องการค้นหาข้อมูลโดยไม่ได้ใช้ค่าดัชนี (index) แบบเดียวกับที่ใช้ในเวกเตอร์ แต่ต้องการค้นหาด้วยคีย์ที่สามารถเป็นประเภทข้อมูลใดก็ได้ ตัวอย่างเช่น ในเกม คุณสามารถบันทึกคะแนนของแต่ละทีมไว้ในแฮชแมป โดยมีคีย์เป็นชื่อทีมและค่าเป็นคะแนนของทีมนั้น ๆ เมื่อกำหนดชื่อทีมให้ คุณก็จะสามารถดึงคะแนนของทีมนั้นออกมาใช้งานได้

ในส่วนนี้เราจะกล่าวถึงการทำงานพื้นฐาน (basic API) ของแฮชแมป แต่ทว่ายังมีฟังก์ชันเจ๋ง ๆ อีกมากมายที่ซ่อนอยู่ในเมธอดของ HashMap<K, V> ซึ่งจัดเตรียมไว้โดยไลบรารีมาตรฐาน และเช่นเคย คุณสามารถตรวจสอบข้อมูลเพิ่มเติมได้จากเอกสารของไลบรารีมาตรฐาน

การสร้างแฮชแมปใหม่ (Creating a New Hash Map)

วิธีหนึ่งในการสร้างแฮชแมปที่ว่างเปล่าคือการเรียกใช้ฟังก์ชัน 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 จากกลุ่มของคอลเลกชัน (collections) ในไลบรารีมาตรฐานก่อน ในบรรดาคอลเลกชันทั่วไปทั้งสามประเภทที่เราเรียนรู้ไป แฮชแมปถือเป็นตัวที่ถูกเรียกใช้งานน้อยที่สุด ดังนั้นมันจึงไม่ได้ถูกดึงเข้ามาในขอบเขตการใช้งานโดยอัตโนมัติ (prelude) นอกจากนี้แฮชแมปยังมีการสนับสนุนจากไลบรารีมาตรฐานน้อยกว่า เช่น ไม่มีมาโครในตัวสําหรับสร้างแฮชแมปโดยเฉพาะ

ข้อมูลในแฮชแมปจะถูกจัดเก็บไว้บนพื้นที่หน่วยความจำฮีป (heap) เช่นเดียวกับเวกเตอร์ ตัว HashMap นี้มีคีย์เป็นประเภท String และค่าเป็นประเภท i32 และคุณสมบัติของแฮชแมปก็เหมือนกับเวกเตอร์คือเป็นข้อมูลประเภทเดียวกัน (homogeneous): นั่นคือคีย์ทั้งหมดต้องเป็นประเภทเดียวกัน และค่าทั้งหมดก็ต้องเป็นประเภทเดียวกันด้วย

การเข้าถึงค่าต่าง ๆ ในแฮชแมป (Accessing Values in a Hash Map)

เราสามารถดึงข้อมูลออกจากแฮชแมปได้โดยการส่งคีย์ไปให้เมธอด 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 ให้เป็นศูนย์ หากในแฮชแมป scores ไม่มีข้อมูลสำหรับคีย์นั้น

เราสามารถวนลูปผ่านคู่คีย์-ค่า (key-value pair) แต่ละคู่ในแฮชแมปได้ในลักษณะเดียวกันกับการวนลูปในเวกเตอร์ โดยใช้ลูป 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}");
    }
}

โค้ดนี้จะแสดงผลลัพธ์แต่ละคู่คีย์-ค่าในแบบที่ไม่เรียงลำดับแน่นอน (arbitrary order):

Yellow: 50
Blue: 10

การจัดการความเป็นเจ้าของในแฮชแมป (Managing Ownership in Hash Maps)

สำหรับประเภทข้อมูลที่สืบทอด (implement) ทริต Copy เช่น i32 ค่าต่าง ๆ จะถูกคัดลอก (copy) เข้าไปยังแฮชแมป สำหรับข้อมูลที่เป็นเจ้าของตัวเองอย่าง 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 แล้ว

หากเราใส่ข้อมูลอ้างอิง (references) ของค่าต่าง ๆ เข้าไปในแฮชแมป ค่าเหล่านั้นจะไม่ถูกย้ายสิทธิ์เข้าไปในแฮชแมป แต่ทว่าค่าจริงที่ข้อมูลอ้างอิงชี้อยู่นั้นจะต้องมีอายุใช้งาน (valid) นานอย่างน้อยที่สุดเท่าที่แฮชแมปนั้นยังมีอายุใช้งานอยู่ เราจะพูดคุยประเด็นเหล่านี้เพิ่มเติมในหัวข้อ “การตรวจสอบความถูกต้องของข้อมูลอ้างอิงด้วยอายุการใช้งาน (Validating References with Lifetimes)” ของบทที่ 10

การอัปเดตข้อมูลในแฮชแมป (Updating a Hash Map)

ถึงแม้ว่าคู่คีย์และค่าจะสามารถเพิ่มจำนวนขึ้นได้เรื่อย ๆ แต่คีย์ที่มีความเป็นเอกลักษณ์ (unique key) แต่ละตัวจะมีค่าที่เชื่อมโยงอยู่ด้วยได้เพียงครั้งละหนึ่งค่าเท่านั้น (แต่ในทางกลับกันไม่ใช่ เช่น ทั้งทีม Blue และทีม Yellow ต่างก็มีค่าคะแนนเป็น 10 เก็บไว้ในแฮชแมป scores ได้พร้อมกัน)

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

การเขียนทับค่าเดิม (Overwriting a Value)

หากเราใส่คีย์และค่าลงไปในแฮชแมป จากนั้นใส่คีย์เดิมซ้ำเข้าไปอีกครั้งด้วยค่าที่แตกต่างออกไป ค่าที่ผูกไว้กับคีย์ดังกล่าวจะถูกเปลี่ยนแทนที่ทันที แม้ว่าโค้ดในตัวอย่างที่ 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 ได้ถูกเขียนทับไปแล้ว

การเพิ่มคู่คีย์และค่าเฉพาะเมื่อยังไม่มีคีย์นั้นอยู่ (Adding a Key and Value Only If a Key Isn’t Present)

โดยทั่วไปเรามักจะต้องตรวจสอบก่อนว่ามีคีย์นั้น ๆ อยู่ในแฮชแมปแล้วหรือไม่ แล้วจึงดำเนินการขั้นตอนถัดไปคือ: หากมีคีย์นั้นอยู่แล้วในแฮชแมป ให้คงค่าเดิมไว้ไม่เปลี่ยนแปลง แต่ถ้าไม่มีคีย์นั้นอยู่จึงค่อยเพิ่มคีย์และค่านั้น ๆ ลงไป

แฮชแมปมี 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 ถูกกำหนดมาให้ทำหน้าที่คืนค่าข้อมูลอ้างอิงแบบแก้ไขได้ (mutable reference) ไปยังค่าของคีย์ Entry นั้น ๆ หากมีอยู่จริง และถ้าไม่มี คีย์ดังกล่าวก็จะถูกกำหนดค่าใหม่ตามอาร์กิวเมนต์ที่ส่งไปและคืนข้อมูลอ้างอิงแบบแก้ไขได้ของค่านั้นกลับมา เทคนิคนี้มีความเรียบร้อยสวยงามกว่าการเขียนตรรกะเงื่อนไขขึ้นมาเอง อีกทั้งยังทำงานร่วมกับระบบตรวจสอบสิทธิ์การยืม (borrow checker) ได้อย่างราบรื่นมาก

เมื่อสั่งรันโค้ดในตัวอย่างที่ 8-24 จะได้ผลลัพธ์แสดงออกมาเป็น {"Yellow": 50, "Blue": 10} การเรียกใช้เมธอด entry รอบแรกจะใส่คีย์ของทีม Yellow พร้อมค่า 50 เนื่องจากเดิมทียังไม่มีค่าของทีม Yellow อยู่ในแฮชแมป ส่วนการเรียกใช้รอบที่สองจะไม่ทำให้แฮชแมปเปลี่ยนแปลงใด ๆ เนื่องจากทีม Blue มีค่า 10 อยู่แล้วก่อนหน้านี้

การอัปเดตค่าโดยอิงจากค่าเดิม (Updating a Value Based on the Old Value)

การใช้งานแฮชแมปยอดนิยมอีกกรณีหนึ่งคือการค้นหาค่าของคีย์เดิมแล้วทำการอัปเดตค่านั้นโดยอ้างอิงจากค่าเดิม ตัวอย่างเช่น ตัวอย่างที่ 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} คุณอาจจะเห็นคู่คีย์-ค่าคู่เดียวกันนี้แสดงเรียงลำดับสลับที่กันได้: โปรดจำกฎจากหัวข้อ “การเข้าถึงค่าต่าง ๆ ในแฮชแมป (Accessing Values in a Hash Map)” ที่ระบุว่าการวนลูปผ่านแฮชแมปจะสุ่มผลลัพธ์แบบไม่เรียงลำดับแน่นอน

เมธอด split_whitespace จะคืนค่าตัววนลูป (iterator) ของสตริงย่อย (subslices) ที่คั่นด้วยช่องว่างของข้อความในตัวแปร text เมธอด or_insert จะคืนค่าข้อมูลอ้างอิงแบบแก้ไขได้ (&mut V) ไปยังค่าที่เก็บไว้สำหรับคีย์ที่กำหนด ซึ่งที่นี่เราจะจัดเก็บข้อมูลอ้างอิงแบบแก้ไขได้นี้ไว้ในตัวแปร count ดังนั้นในการแก้ไขค่าดังกล่าว เราต้องทำการเข้าถึงค่าจริงจากข้อมูลอ้างอิง (dereference) ของตัวแปร count เสียก่อนด้วยการใส่เครื่องหมายดอกจัน (*) โดยข้อมูลอ้างอิงแบบแก้ไขได้จะหลุดออกนอกขอบเขตการใช้งาน (out of scope) เมื่อสิ้นสุดแต่ละรอบของลูป for ดังนั้นการเปลี่ยนแปลงทั้งหมดนี้จึงมีความปลอดภัยและเป็นไปตามกฎระบบตรวจสอบสิทธิ์การยืม

ฟังก์ชันแฮช (Hashing Functions)

ตามพฤติกรรมเริ่มต้น ตัวแปรแฮชแมป HashMap จะใช้ฟังก์ชันแฮชที่มีชื่อว่า SipHash ซึ่งมีประสิทธิภาพในการป้องกันการโจมตีแบบปฏิเสธการให้บริการ (Denial-of-Service หรือ DoS) ที่พุ่งเป้ามายังตารางแฮช¹ ซึ่งนี่อาจจะไม่ใช่รูทีนอัลกอริทึมแฮชที่เร็วที่สุดเท่าที่มีอยู่ แต่การแลกประสิทธิภาพที่ลดลงไปเพียงเล็กน้อยเพื่อให้ได้ความปลอดภัยที่ดียิ่งขึ้นนั้นถือว่าคุ้มค่า หากคุณลองวิเคราะห์ประสิทธิภาพโค้ด (profile) แล้วพบว่าฟังก์ชันแฮชเริ่มต้นนี้ทำงานช้าเกินไปสำหรับการใช้งานของคุณ คุณสามารถเปลี่ยนไปใช้ฟังก์ชันแฮชตัวอื่นได้โดยระบุตัวคำนวณแฮช (hasher) แบบอื่น ซึ่ง hasher คือประเภทข้อมูลใด ๆ ที่สืบทอดทริต BuildHasher เราจะพูดคุยเรื่องทริตและการนำไปใช้งานต่อใน บทที่ 10 ทั้งนี้คุณไม่จำเป็นต้องสร้าง hasher ของคุณเองใหม่ทั้งหมดตั้งแต่เริ่มต้น เนื่องจากบนเว็บไซต์ crates.io มีไลบรารีที่นักพัฒนาภาษา Rust คนอื่นแบ่งปันไว้ซึ่งมี hasher ที่ใช้อัลกอริทึมแฮชยอดนิยมแบบต่าง ๆ ให้พร้อมใช้งาน

สรุป (Summary)

เวกเตอร์, สตริง และแฮชแมป มอบความสามารถที่หลากหลายและจำเป็นอย่างยิ่งสำหรับโปรแกรมต่าง ๆ เมื่อคุณต้องจัดเก็บ เข้าถึง หรือแก้ไขข้อมูล และนี่คือแบบฝึกหัดที่คุณควรจะพร้อมทำเพื่อท้าทายตนเองในตอนนี้แล้ว:

1. กำหนดรายการตัวเลขจำนวนเต็มมาให้ ให้ใช้เวกเตอร์เพื่อค้นหาและส่งค่ามัธยฐาน (median - ค่าที่อยู่ตำแหน่งตรงกลางเมื่อทำการเรียงลำดับแล้ว) และฐานนิยม (mode - ค่าที่ปรากฏขึ้นบ่อยครั้งที่สุด โดยการใช้แฮชแมปจะช่วยในโจทย์ข้อนี้นะครับ) ของรายการข้อมูลนั้น
2. แปลงสตริงให้กลายเป็น Pig Latin โดยตัวพยัญชนะตัวแรกของคำจะถูกย้ายไปไว้ที่ท้ายคำแล้วตามด้วยคำว่า ay เช่น คำว่า first จะเปลี่ยนเป็น irst-fay ส่วนคำศัพท์ใดที่เริ่มต้นด้วยสระจะนำคำว่า hay ไปเติมไว้ที่ท้ายคำแทน (เช่น apple จะเปลี่ยนเป็น apple-hay) ทั้งนี้อย่าลืมคำนึงถึงรายละเอียดเกี่ยวกับการเข้ารหัส UTF-8 ด้วยนะครับ!
3. ใช้แฮชแมปและเวกเตอร์เพื่อสร้างอินเทอร์เฟซแบบข้อความ (text interface) ที่อนุญาตให้ผู้ใช้เพิ่มรายชื่อพนักงานเข้าสู่แผนกต่าง ๆ ของบริษัท เช่น “Add Sally to Engineering” หรือ “Add Amir to Sales” จากนั้นให้ระบบดึงรายชื่อพนักงานทั้งหมดของแผนกนั้น ๆ หรือรายชื่อทุกคนในบริษัทแยกตามแผนกออกมาแสดงผลโดยเรียงลำดับตามตัวอักษร

ข้อมูลเอกสารอ้างอิง API ของไลบรารีมาตรฐานมีคำอธิบายเมธอดต่าง ๆ ของเวกเตอร์ สตริง และแฮชแมป ซึ่งจะมีประโยชน์อย่างมากในการช่วยทำแบบฝึกหัดเหล่านี้!

เรากำลังจะก้าวเข้าสู่โปรแกรมที่มีความซับซ้อนมากยิ่งขึ้นซึ่งขั้นตอนการทำงานบางอย่างอาจเกิดความล้มเหลวได้ ดังนั้นจึงเป็นจังหวะที่เหมาะสมอย่างยิ่งที่จะเรียนรู้เรื่องการจัดการกับข้อผิดพลาด (error handling) มาดูกันต่อในหัวข้อถัดไปเลยครับ!

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