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

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

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

ดูเพิ่ม[แก้]