แถวลำดับแบบจับคู่
 | บทความนี้ไม่มีการอ้างอิงจากแหล่งที่มาใด |
| แถวลำดับแบบจับคู่ | |
|---|---|
| ความสำคัญของลำดับ | ไม่เรียงลำดับความสำคัญ |
| การซ้ำกันของสมาชิก | ไม่อนุญาตให้ซ้ำ |
| เวลาที่ใช้ในการเข้าถึง | การใช้คีย์เข้าถึงข้อมูล |
| โครงสร้างที่นำไปใช้ | ตารางแฮช |
แถวลำดับแบบจับคู่ (อังกฤษ: Associative array) หรือที่เรีบกว่า แผนที่ (อังกฤษ: map), ตารางสัญลักษณ์ (อังกฤษ: symbol table), หรือ พจนานุกรม (อังกฤษ: dictionary) หมายถึง กลุ่มโครงสร้างข้อมูลหรือแบบชนิดข้อมูลนามธรรม ที่สามารถเข้าถึงข้อมูลได้โดยผ่านข้อมูลอีกตัว เรียกว่า คีย์ (key) โดยเป็นการจับคู่คีย์เข้ากับค่าข้อมูล (value) เป็นคู่ ๆ ไป
ในภาษาโปรแกรมหลายภาษา แถวลำดับแบบจับคู่ ถือเป็นประเภทข้อมูลประเภทหนึ่งที่สำคัญมากและมีใช้หลากหลายรูปแบบ อาทิ ใช้ในการจัดการข้อมูลในฐานข้อมูล ใช้เป็นโครงสร้างข้อมูลเบื้องต้น เป็นต้น
จุดเด่นของแถวลำดับแบบจับคู่
[แก้]จุดเด่นของแถวลำดับแบบจับคู่ คือบริการที่ไม่เหมือนใคร โดยการเข้าถึงข้อมูลตัวหนึ่ง โดยใช้ข้อมูลอีกตัวที่เรียกว่าคีย์ คล้ายกับฟังก์ชันในคณิตศาสตร์ ซึ่งเมื่อใส่คีย์เข้าไป จะได้คำตอบออกมา
ตัวอย่างของแถวลำดับแบบจับคู่ ที่มักกล่าวถึงคือสมุดโทรศัพท์ เมื่อเรารู้ชื่อของผู้ที่เราจะคุยด้วย เราก็สามารถเปิดสมุดโทรศัพท์เพื่อหาหมายเลขโทรศัพท์ได้ทันที
บริการที่มักจะมี
[แก้]- การเพิ่ม ลบข้อมูล
- การค้นหาตามคีย์
ความเร็วที่ใช้ในการทำงาน
[แก้]เราสามารถใช้ฟังก์ชันแฮชในการช่วยจัดเก็บข้อมูลแบบนี้ เราจะเรียก Associative Array ที่ใช้ฟังก์ชันแฮชว่า ตารางแฮช ซึ่งจากสมบัติของฟังก์ชันแฮชจะได้ว่าการเข้าถึงมีความเร็วคงที่ (O(1))
แต่ถึงอย่างไรก็ตามเราสามารถใช้โครงสร้างข้อมูลอื่น เช่น แถวลำดับสองอัน และเก็บคีย์และข้อมูลไว้ที่ดัชนีเดียวกัน แต่การไล่หาข้อมูลต้องไล่หาทั้งหมด จึงอาจใช้เวลาเป็น (O(n)) หรือใช้ต้นไม้ค้นหาเข้าช่วย
โครงสร้างข้อมูลที่เป็นแถวลำดับแบบจับคู่
[แก้]- ตารางแฮช
- ต้นไม้ค้นหา
- แถวลำดับสองอัน
ชื่อเรียก
[แก้]ชื่อเรียกของแถวลำดับแบบจับคู่ ตามภาษาต่าง ๆ มีหลากหลายมากสามารถแจกแจงออกมาเป็นตารางดังนี้
| ชื่อเรียก | ภาษาที่ใช้ |
|---|---|
| Associative array | Snobol4, tcl, Javascript |
| map | Java, C++ |
| hash | Perl, Ruby |
| hashmap | Lisp, Windows PowerShell |
| dictionary | Smalltalk, Objective-C, .NET, Python |
| table | Lua |
นอกจากนี้ยังมีชื่ออื่น ๆ เช่น associative container, mapping, finite map, lookup table, Index file
การใช้งาน
[แก้]นอกจากชื่อแล้ว แถวลำดับแบบจับคู่ ในแต่ละภาษายังมีการใช้งานที่แตกต่างกัน บางภาษา อาทิ ใน PHP แถวลำดับทุกตัวจะสามารถเป็น แถวลำดับแบบจับคู่ ได้ ในภาษาสคริปต์ Lua จะใช้ Associated Array เป็นตัวเริ่มต้นในการสร้างโครงสร้างข้อมูล ทั้งหมดอีกด้วย
โครงสร้างข้อมูลที่ใช้
[แก้]ใน MUMPS แถวลำดับแบบจับคู่สร้างโดยใช้ ต้นไม้แบบบี ในจาวามีให้เลือกระหว่างการใช้ ตารางแฮช (HashMap) หรือ ตารางแฮชผสมรายการโยง (ListHashMap)