แถวลำดับแบบจับคู่

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

แถวลำดับแบบจับคู่ (อังกฤษ: 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)

ดูเพิ่ม

• ฟังก์ชันแฮช