ข้ามไปยังเนื้อหา
Rust Deep Dive

HashMap

HashMap<K, V>

หัวข้อที่มีชื่อว่า “HashMap<K, V>”

HashMap<K, V> แม็ป key ชนิด K ไปยัง value ชนิด V มันใช้ hash function ภายในเพื่อให้ insert และ lookup เป็น O(1) โดยเฉลี่ย

use std::collections::HashMap;


let mut scores: HashMap<String, u32> = HashMap::new();

key ต้อง implement Eq และ Hash ชนิด key ที่พบบ่อย — String, &str, จำนวนเต็ม — implement ไว้อยู่แล้ว

Insert และอ่านค่า

หัวข้อที่มีชื่อว่า “Insert และอ่านค่า”
use std::collections::HashMap;


let mut scores: HashMap<String, u32> = HashMap::new();
scores.insert(String::from("Alice"), 100);
scores.insert(String::from("Bob"), 85);


// get returns Option<&V>
if let Some(score) = scores.get("Alice") {
    println!("Alice: {}", score);
}


// index syntax — panics if key is missing
let bob_score = scores["Bob"];

ให้ใช้ .get(key) ในโค้ด production เพื่อจัดการกรณี key หายไปอย่างปลอดภัย

ค้นหา key แบบ String ด้วย &str — Borrow ทำงานอยู่เบื้องหลัง

หัวข้อที่มีชื่อว่า “ค้นหา key แบบ String ด้วย &str — Borrow ทำงานอยู่เบื้องหลัง”

scores.get("Alice") ข้างบนส่ง &str literal เข้าไปค้นหา HashMap<String, u32> — ไม่ต้อง allocate String เพื่อค้นหาเลย ที่เป็นแบบนี้ได้เพราะ HashMap::get เป็น generic เหนือชนิดใดก็ตามที่ key ที่เก็บไว้ยืมเป็นได้ ผ่าน trait Borrow ของไลบรารีมาตรฐาน: String implement Borrow<str> ดังนั้น method ใดก็ตามที่แค่ต้องเปรียบเทียบ/hash key (get, contains_key, remove) จึงรับ &str ได้โดยตรง แทนที่จะบังคับให้คุณสร้าง String ที่เป็นเจ้าของแค่เพื่อถามคำถาม

use std::collections::HashMap;


fn main() {
    let mut scores: HashMap<String, u32> = HashMap::new();
    scores.insert(String::from("alice"), 100);
    let key: &str = "alice"; // borrowed, no allocation
    println!("lookup by &str: {:?}", scores.get(key));
}

คอมไพเลอร์พูดว่าอะไร: ไม่ใช่ทุกชนิดจะเป็น Key ได้

หัวข้อที่มีชื่อว่า “คอมไพเลอร์พูดว่าอะไร: ไม่ใช่ทุกชนิดจะเป็น Key ได้”

key ของ HashMap ต้อง implement Eq (ความเท่ากันแบบ total ที่ reflexive) และ Hash (ค่าที่เท่ากันต้อง hash เหมือนกัน) f64 ไม่ implement ทั้งสองอย่างโดยตั้งใจ — NaN != NaN ทำลาย reflexivity ของ Eq และการปัดเศษทำให้ hash ไม่เสถียร — ดังนั้นคอมไพเลอร์จึงปฏิเสธที่จุดเรียก method ไม่ใช่ที่จุดประกาศ HashMap:

// @expect-error E0599
use std::collections::HashMap;


fn main() {
    let mut m: HashMap<f64, &str> = HashMap::new();
    m.insert(1.5, "one and a half");
    println!("{:?}", m.get(&1.5));
}
error[E0599]: the method `insert` exists for struct `HashMap<f64, &str>`, but its trait bounds were not satisfied
 --> src/main.rs:5:7
  |
5 |     m.insert(1.5, "one and a half");
  |       ^^^^^^
  |
  = note: the following trait bounds were not satisfied:
          `f64: Eq`
          `f64: Hash`


error[E0599]: the method `get` exists for struct `HashMap<f64, &str>`, but its trait bounds were not satisfied
 --> src/main.rs:6:24
  |
6 |     println!("{:?}", m.get(&1.5));
  |                        ^^^ method cannot be called on `HashMap<f64, &str>` due to unsatisfied trait bounds
  |
  = note: the following trait bounds were not satisfied:
          `f64: Eq`
          `f64: Hash`


error: aborting due to 2 previous errors


For more information about this error, try `rustc --explain E0599`.

HashMap<f64, V> คอมไพล์ผ่านในฐานะ type — error จะปรากฏก็ต่อเมื่อคุณเรียก method (insert, get) ที่ต้องการ Eq/Hash จริงๆ เท่านั้น ถ้าคุณต้องการ key ด้วยค่าคล้าย floating-point ให้ key ด้วยชนิดที่มีความเท่ากันจริงแทน: ปัดเป็นค่า integer representation (สตางค์แทนบาท เช่น) หรือห่อมันด้วย newtype ที่มี Eq/Hash แบบกำหนดเองที่บันทึกไว้ว่าคุณนิยาม “เท่ากัน” สำหรับ use case ของคุณอย่างไร

Entry API

หัวข้อที่มีชื่อว่า “Entry API”

entry API ให้วิธีที่สะอาดในการ insert value เฉพาะเมื่อ key ยังไม่มี โดยหลีกเลี่ยงการ lookup สองครั้ง:

use std::collections::HashMap;


let mut scores: HashMap<String, u32> = HashMap::new();
scores.insert(String::from("Alice"), 100);
scores.insert(String::from("Bob"), 85);


// Insert 70 for "Dave" if "Dave" is not yet present
scores.entry(String::from("Dave")).or_insert(70);


// Increment a counter — insert 0 first if absent, then add 1
let count = scores.entry(String::from("Eve")).or_insert(0);
*count += 1;

or_insert คืนค่า &mut V ที่ชี้ไปยัง value นั้น คุณจึงอัปเดตมันในที่ได้

or_insert_with — ค่า Default แบบ Lazy

หัวข้อที่มีชื่อว่า “or_insert_with — ค่า Default แบบ Lazy”

or_insert(v) จะ evaluate v เสมอ แม้ว่า key จะมีอยู่แล้วและ v จะถูกทิ้งไป or_insert_with(f) รับ closure และเรียกมันก็ต่อเมื่อ key ไม่มีอยู่จริงๆ เท่านั้น — จำเป็นเมื่อค่า default สร้างขึ้นแพง (การ allocate, Vec ใหม่, ค่าที่คำนวณ):

use std::collections::HashMap;


fn main() {
    // or_insert_with(f): f only runs if the key is absent (lazy default)
    let mut groups: HashMap<String, Vec<i32>> = HashMap::new();
    for n in [1, 2, 3, 4, 5, 6] {
        let key = if n % 2 == 0 { "even" } else { "odd" };
        groups
            .entry(key.to_string())
            .or_insert_with(Vec::new)
            .push(n);
    }
    let mut keys: Vec<&String> = groups.keys().collect();
    keys.sort();
    for k in keys {
        println!("{}: {:?}", k, groups[k]);
    }
}
even: [2, 4, 6]
odd: [1, 3, 5]

การจัดกลุ่มแบบนี้ — entry(key).or_insert_with(Vec::new).push(item) — เป็นหนึ่งใน use case จริงที่พบบ่อยที่สุดของ entry API: สร้าง HashMap<K, Vec<V>> ใน pass เดียวโดยไม่ต้องมี branch แยก “key นี้มีอยู่แล้วหรือยัง”

ลำดับการวนซ้ำสุ่มจริง — พิสูจน์แล้ว ไม่ใช่แค่บอก

หัวข้อที่มีชื่อว่า “ลำดับการวนซ้ำสุ่มจริง — พิสูจน์แล้ว ไม่ใช่แค่บอก”

HashMap ไม่ รับประกันลำดับการวนซ้ำใดๆ เลย และมันไม่ใช่แค่ “ลำดับการ insert ที่ดูสับสน” — Rust สุ่ม seed ของ hasher เริ่มต้น (SipHash) ต่อ process โดยเฉพาะเพื่อทำให้การโจมตีแบบ hash-flooding denial-of-service ทำไม่ได้จริง โปรแกรมเดียวกัน คอมไพล์ครั้งเดียว พิมพ์ลำดับต่างกันแทบทุกครั้งที่รัน:

use std::collections::HashMap;


fn main() {
    let mut m: HashMap<&str, i32> = HashMap::new();
    m.insert("alpha", 1);
    m.insert("bravo", 2);
    m.insert("charlie", 3);
    m.insert("delta", 4);
    for (k, v) in &m {
        print!("{}:{} ", k, v);
    }
    println!();
}

การรันจริงสองครั้งของ binary ที่คอมไพล์ตัวเดียวกันเป๊ะๆ — ไม่ใช่สองโปรแกรมที่ต่างกัน:

$ ./a.bin
alpha:1 delta:4 bravo:2 charlie:3


$ ./a.bin
charlie:3 delta:4 alpha:1 bravo:2

เมื่อลำดับ output สำคัญ (test, playground ที่ใช้เรียน, log output) ให้ sort key ก่อน:

use std::collections::HashMap;


let mut scores: HashMap<String, u32> = HashMap::new();
scores.insert(String::from("Alice"), 100);
scores.insert(String::from("Bob"), 85);


let mut keys: Vec<&String> = scores.keys().collect();
keys.sort();
for k in keys {
    println!("{}: {}", k, scores[k]);
}

BTreeMap<K, V> — เมื่อคุณต้องการลำดับแบบไม่ต้องทำอะไร

หัวข้อที่มีชื่อว่า “BTreeMap<K, V> — เมื่อคุณต้องการลำดับแบบไม่ต้องทำอะไร”

ถ้าคุณต้องการการวนซ้ำแบบเรียงลำดับทุกครั้ง ให้ใช้ BTreeMap<K, V> แทนการ sort key ของ HashMap เอง มันเก็บ entry ใน tree ที่สมดุลและเรียงตาม key (ต้องการ K: Ord) ดังนั้นการวนซ้ำจึงเรียงลำดับเสมอโดยไม่ต้องมีขั้นตอนเพิ่ม — แลกกับการดำเนินการ O(log n) แทน O(1) โดยเฉลี่ยของ HashMap:

use std::collections::BTreeMap;


fn main() {
    let mut m: BTreeMap<&str, i32> = BTreeMap::new();
    m.insert("delta", 4);
    m.insert("alpha", 1);
    m.insert("charlie", 3);
    m.insert("bravo", 2);
    // BTreeMap iterates in sorted key order, always, no sorting needed
    for (k, v) in &m {
        print!("{}:{} ", k, v);
    }
    println!();
}
alpha:1 bravo:2 charlie:3 delta:4

ทุกการรันของโปรแกรมนี้พิมพ์ลำดับเดียวกัน — เรียงตาม key — เพราะ BTreeMap ไม่ใช้ hashing เลย

การลบ Entry

หัวข้อที่มีชื่อว่า “การลบ Entry”
use std::collections::HashMap;


let mut scores: HashMap<String, u32> = HashMap::new();
scores.insert(String::from("Alice"), 100);
scores.insert(String::from("Bob"), 85);


scores.remove("Bob");
println!("Bob present: {}", scores.contains_key("Bob"));
flowchart TD
  A["entry(key)"] --> B{Key already present?}
  B -->|Yes| C["or_insert / or_insert_with: return &mut V to the existing value, default not evaluated"]
  B -->|No| D["or_insert_with(f): call f() now, insert result"]
  D --> E["or_insert(v): v was already evaluated eagerly, insert it"]
  C --> F[Caller mutates *value in place]
  E --> F
เส้นทางการตัดสินใจของ entry API
Open in Rust Playground 
use std::collections::HashMap;


fn main() {
    let mut scores: HashMap<String, u32> = HashMap::new();
    scores.insert(String::from("Alice"), 100);
    scores.insert(String::from("Bob"), 85);
    scores.insert(String::from("Carol"), 92);


    // entry API: insert if absent
    scores.entry(String::from("Dave")).or_insert(70);
    // Alice already exists — or_insert does nothing
    scores.entry(String::from("Alice")).or_insert(0);


    // get returns Option<&V>
    if let Some(score) = scores.get("Alice") {
        println!("Alice scored {}", score);
    }


    // deterministic iteration: sort keys
    let mut keys: Vec<&String> = scores.keys().collect();
    keys.sort();
    for k in keys {
        println!("{}: {}", k, scores[k]);
    }


    // remove
    scores.remove("Bob");
    println!("Bob present: {}", scores.contains_key("Bob"));
}

แบบจำลองความคิด

หัวข้อที่มีชื่อว่า “แบบจำลองความคิด”

HashMap คือ bucket array บวก hash function: insert/get/remove ทั้งหมดเริ่มจากการ hash key เพื่อเลือก bucket ดังนั้นต้นทุนของมันจึงไม่โตตามจำนวน entry (โดยเฉลี่ย) — แต่ layout ของ bucket ไม่มีความเกี่ยวข้องกับลำดับการ insert เลย ดังนั้น “วนซ้ำ bucket ตามลำดับ” จึงให้ลำดับที่ hash function บังเอิญกระจาย key เข้าไป ซึ่งถูกสุ่มใหม่ทุกครั้งที่ process เริ่ม BTreeMap เป็นโครงสร้างข้อมูลที่ต่างไปโดยสิ้นเชิงพร้อมการรับประกันที่ต่างไปโดยสิ้นเชิง: มันคือ tree ที่สมดุล ดังนั้น “วนซ้ำตามลำดับ” คือ “วนซ้ำ tree แบบ in-order traversal” — การเรียงลำดับเป็นเชิงโครงสร้าง ไม่ใช่เรื่องบังเอิญ

ข้อแลกเปลี่ยน

หัวข้อที่มีชื่อว่า “ข้อแลกเปลี่ยน”

HashMap ชนะที่ความเร็วในการ lookup ดิบ (O(1) โดยเฉลี่ย) และไม่มีข้อกำหนดอะไรนอกจาก Eq + Hash บน key BTreeMap ให้การวนซ้ำแบบเรียงลำดับและ range query (.range(a..b)) ได้ฟรี แลกกับ O(log n) ต่อการดำเนินการและข้อกำหนด Ord เพิ่มเติม entry(k).or_insert(v) เขียนง่ายกว่าแต่ evaluate v เสมอ; entry(k).or_insert_with(f) เสียค่าเรียก closure เพิ่มหนึ่งครั้งแต่ไม่เคยสร้างค่า default ที่คุณกำลังจะทิ้งไป

ความเข้าใจผิดที่พบบ่อย

หัวข้อที่มีชื่อว่า “ความเข้าใจผิดที่พบบ่อย”
  • “ลำดับการวนซ้ำ HashMap คือลำดับการ insert แค่ไม่ชัดเจน” ไม่ใช่ลำดับการ insert เลย — มันมาจาก hash seed ที่สุ่มใหม่ทุกครั้งที่ process เริ่ม โดยเฉพาะเพื่อป้องกันการโจมตีแบบ hash-flooding source code เดียวกัน แค่ compile ใหม่หรือรันใหม่ ก็ให้ลำดับที่ต่างกัน
  • “คุณใส่ f64 เป็น key ของ HashMap ได้ตราบใดที่ระวังเรื่อง NaN” คอมไพเลอร์ไม่ปล่อยให้คุณลองเลย — f64 ไม่ implement ทั้ง Eq และ Hash เลย (แม้แต่ Eq สำหรับกรณีที่ “ระวังแล้ว”) ดังนั้น HashMap<f64, V> จึงล้มเหลวที่การเรียก method ครั้งแรกที่ต้องการ bound เหล่านั้น ไม่ใช่ที่ edge case ตอน runtime
  • “BTreeMap ช้ากว่าเสมอ ดังนั้นใช้แค่สำหรับ output ตอน debug” มันเป็นตัวเลือกที่ใช้ใน production ได้จริงเมื่อคุณต้องการ range query (.range(low..high)) หรือลำดับที่คาดเดาได้เป็นข้อกำหนดด้านความถูกต้อง ไม่ใช่แค่ความสะดวกตอน debug — ต้นทุน O(log n) คือราคาของฟีเจอร์จริง ไม่ใช่ overhead ที่จ่ายไปเปล่าๆ

อ่านโค้ดที่ AI เขียน

หัวข้อที่มีชื่อว่า “อ่านโค้ดที่ AI เขียน”

โค้ดที่ AI สร้างมักจะวนซ้ำ HashMap โดยตรงในโค้ดที่ไวต่อ output — report, test assertion, snapshot — โดยไม่เคยพิจารณาเลยว่าลำดับไม่เสถียร

🐛 หา bug ในโค้ดนี้

fn format_report(scores: &std::collections::HashMap<String, u32>) -> String {
  let mut out = String::new();
  for (name, score) in scores {
      out.push_str(&format!("{}: {}\n", name, score));
  }
  out
}
เฉลย

output order ของฟังก์ชันนี้ขึ้นอยู่กับ hash seed แบบสุ่มของ HashMap — การรันโปรแกรมเดียวกันเป๊ะๆ ด้วยข้อมูลเดียวกันเป๊ะๆ สองครั้ง สามารถพิมพ์ scores ในลำดับที่ต่างกันได้ test ใดก็ตามที่ทำ assert_eq!(format_report(&scores), "alice: 100\nbob: 85\n") จะผ่านหรือไม่ผ่านขึ้นอยู่กับ random seed ของการรันครั้งนั้น ซึ่งทำให้ test นั้น flaky ไม่ใช่แค่ผิด วิธีแก้: sort key ก่อน format (let mut names: Vec<_> = scores.keys().collect(); names.sort();) หรือเปลี่ยน map ข้างใต้เป็น BTreeMap ถ้าผู้เรียกต้องการ output ที่เรียงแล้วเสมอ

scores.get("Alice") คืนอะไรเมื่อ Alice ไม่มีใน map?
entry(key).or_insert(v) ทำอะไรเมื่อ key มีอยู่แล้ว?
ทำไมลำดับการวนซ้ำ HashMap ใน Rust จึงไม่แน่นอน?
ชนิดหนึ่งต้อง implement trait bound ไหนบ้างเพื่อใช้เป็น key ของ HashMap ได้?
โค้ดนี้เกิดอะไรขึ้น?
use std::collections::HashMap;
fn main() {
    let mut m: HashMap<f64, &str> = HashMap::new();
    m.insert(1.5, "x");
}
or_insert_with(Vec::new) มีข้อได้เปรียบอะไรเหนือ or_insert(Vec::new())?
เทียบกับ HashMap แล้ว BTreeMap ต้องการอะไรจาก key type และให้อะไรกลับมา?