แอสโซซิเอทีฟอาเรย์

จากวิกิพีเดีย สารานุกรมเสรี
ข้ามไปที่การนำทาง ข้ามไปที่การค้นหา

ในวิทยาการคอมพิวเตอร์แอส โซซิเอทีฟ อาเรย์ , แผนที่ , ตารางสัญลักษณ์หรือพจนานุกรมเป็นประเภทข้อมูลนามธรรมที่เก็บคอลเล็กชันของคู่ (คีย์ ค่า)โดยที่แต่ละคีย์ที่เป็นไปได้จะปรากฏอย่างมากที่สุดครั้งเดียวในคอลเล็กชัน ในทางคณิตศาสตร์ associative array เป็นฟังก์ชันที่มีขอบเขต จำกัด [1]รองรับการดำเนินการ 'ค้นหา', 'ลบ' และ 'แทรก'

ปัญหาพจนานุกรมเป็นปัญหาคลาสสิกของการออกแบบโครงสร้างข้อมูลที่ มีประสิทธิภาพ ซึ่งใช้อาร์เรย์ที่เชื่อมโยง [2] วิธีแก้ปัญหาหลักสองประการสำหรับปัญหาพจนานุกรมคือตารางแฮชและ แผนผัง การค้นหา [3] [4] [5] [6] ในบางกรณีก็เป็นไปได้ที่จะแก้ปัญหาโดยใช้อาร์เรย์ ที่กล่าวถึงโดยตรง ต้นไม้การค้นหา แบบไบนารีหรือโครงสร้างเฉพาะอื่นๆ

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

แอสโซซิเอทีฟอาเรย์มีแอปพลิเคชันมากมายรวมถึง รูปแบบการเขียนโปรแกรมพื้นฐาน เช่นการท่องจำและรูปแบบมัณฑนากร [7]

ชื่อไม่ได้มาจากคุณสมบัติเชื่อมโยงที่รู้จักในวิชาคณิตศาสตร์ แต่เกิดจากการที่เราเชื่อมโยงคุณค่ากับกุญแจ ไม่ต้องสับสนกับตัวประมวลผลที่เชื่อมโยง

ปฏิบัติการ

ในอาเรย์ที่เชื่อมโยง การเชื่อมโยงระหว่างคีย์กับค่ามักจะเรียกว่า "การแมป" และอาจใช้การแมปคำเดียวกันเพื่ออ้างถึงกระบวนการสร้างการเชื่อมโยงใหม่

การดำเนินการที่มักจะกำหนดไว้สำหรับอาเรย์ที่เชื่อมโยงคือ: [3] [4] [8]

  • ใส่หรือใส่ : เพิ่มใหม่จับคู่กับคอลเล็กชัน จับคู่คีย์กับค่าใหม่ การแมปที่มีอยู่จะถูกเขียนทับ อาร์กิวเมนต์ของการดำเนินการนี้คือคีย์และค่า
  • ลบหรือลบ : ลบ aจับคู่จากคอลเล็กชัน ยกเลิกการแมปคีย์ที่กำหนดจากค่าของคีย์นั้น อาร์กิวเมนต์ของการดำเนินการนี้เป็นกุญแจสำคัญ
  • Lookup , findหรือget : ค้นหาค่า (ถ้ามี) ที่ผูกกับคีย์ที่กำหนด อาร์กิวเมนต์ของการดำเนินการนี้คือคีย์ และค่าจะถูกส่งกลับจากการดำเนินการ หากไม่พบค่าใดๆ การใช้งานอาร์เรย์ที่เชื่อมโยงกันบางตัวจะทำให้เกิดข้อยกเว้นในขณะที่บางค่าจะคืนค่าดีฟอลต์ (ศูนย์, null, ค่าเฉพาะที่ส่งผ่านไปยังตัวสร้าง, ...)

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

มัลติแมป ทำให้อาร์เรย์ เชื่อมโยงโดยทั่วไปโดยอนุญาตให้หลายค่าเชื่อมโยงกับคีย์เดียว [9] แผนที่ แบบสองทิศทางเป็นประเภทข้อมูลนามธรรมที่เกี่ยวข้องซึ่งการแมปดำเนินการในทั้งสองทิศทาง: แต่ละค่าจะต้องเชื่อมโยงกับคีย์ที่ไม่ซ้ำกัน และการดำเนินการค้นหาครั้งที่สองจะใช้ค่าเป็นอาร์กิวเมนต์และค้นหาคีย์ที่เกี่ยวข้องกับสิ่งนั้น ค่า.

คุณสมบัติ

การทำงานของ associative array ควรเป็นไปตามคุณสมบัติต่างๆ: [8]

  • lookup(k, insert(j, v, D)) = if k == j then v else lookup(k, D)
  • lookup(k, new()) = failfailข้อยกเว้นหรือค่าเริ่มต้นอยู่ที่ไหน
  • remove(k, insert(j, v, D)) = if k == j then remove(k, D) else insert(j, v, remove(k, D))
  • remove(k, new()) = new()

โดยที่kและjเป็นคีย์vเป็นค่าDเป็นอาร์เรย์ที่เชื่อมโยง และnew()สร้างอาร์เรย์ที่เชื่อมโยงที่ว่างเปล่าขึ้นใหม่

ตัวอย่าง

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

{ 
    "ความภาคภูมิใจและความอยุติธรรม" :  "Alice" , 
    "Wuthering Heights" :  "Alice" , 
    "Great Expectations" :  "John" 
}

การดำเนินการค้นหาคีย์ "Great Expectations" จะส่งคืน "John" หาก John คืนหนังสือของเขา จะทำให้การดำเนินการลบ และหาก Pat เช็คเอาท์หนังสือ ก็จะทำให้เกิดการดำเนินการแทรก ซึ่งจะนำไปสู่สถานะอื่น:

{ 
    "ความภาคภูมิใจและความอยุติธรรม" :  "Alice" , 
    "The Brothers Karamazov" :  "Pat" , 
    "Wuthering Heights" :  "Alice" 
}

การนำไปใช้

สำหรับพจนานุกรมที่มีการแมปจำนวนน้อย อาจเหมาะสมที่จะนำพจนานุกรมไปใช้โดยใช้รายการ เชื่อมโยง ซึ่งเป็นรายการที่เชื่อมโยงของการแมป ด้วยการใช้งานนี้ เวลาในการดำเนินการตามพจนานุกรมพื้นฐานจะเป็นเส้นตรงในจำนวนการแมปทั้งหมด อย่างไรก็ตาม มันใช้งานง่ายและปัจจัยคงที่ของเวลาทำงานนั้นน้อย [3] [10]

เทคนิคการปรับใช้ที่ง่ายมาก อีกวิธีหนึ่ง ใช้งานได้เมื่อคีย์ถูกจำกัดให้อยู่ในช่วงแคบ ๆ คือการกำหนดแอดเดรสโดยตรงในอาร์เรย์: ค่าสำหรับคีย์ที่กำหนดkจะถูกเก็บไว้ที่เซลล์อาร์เรย์A [ k ] หรือหากไม่มีการแมปสำหรับkจากนั้นเซลล์จะเก็บค่ารักษาการณ์ พิเศษ ซึ่งบ่งชี้ว่าไม่มีการแมป นอกจากความง่ายแล้ว เทคนิคนี้ยังรวดเร็ว: การดำเนินการพจนานุกรมแต่ละครั้งใช้เวลาคงที่ อย่างไรก็ตาม ความต้องการพื้นที่สำหรับโครงสร้างนี้คือขนาดของคีย์สเปซทั้งหมด ทำให้ไม่สามารถใช้งานได้เว้นแต่คีย์สเปซมีขนาดเล็ก [5]

แนวทางหลักสองประการในการปรับใช้พจนานุกรมคือตารางแฮชหรือ แผนผัง การค้นหา [3] [4] [5] [6]

การใช้งานตารางแฮช

กราฟนี้เปรียบเทียบจำนวนเฉลี่ยของแคช CPUที่ขาดหายไปที่จำเป็นในการค้นหาองค์ประกอบในตารางแฮชขนาดใหญ่ (เกินขนาดของแคชมาก) ด้วยการต่อสายและการตรวจสอบเชิงเส้น การตรวจสอบเชิงเส้นทำงานได้ดีขึ้นเนื่องจาก ตำแหน่ง อ้างอิง ที่ดีขึ้น แม้ว่าเมื่อตารางเต็ม ประสิทธิภาพจะลดลงอย่างมาก

การใช้งานทั่วไปของ associative array ที่ใช้บ่อยที่สุดคือกับhash table : อาร์เรย์ที่รวมกับฟังก์ชัน hashที่แยกแต่ละคีย์ออกเป็น "bucket" ที่แยกจากกันของอาร์เรย์ แนวคิดพื้นฐานเบื้องหลังตารางแฮชคือการเข้าถึงองค์ประกอบของอาร์เรย์ผ่านดัชนีเป็นการดำเนินการที่เรียบง่ายและใช้เวลาคงที่ ดังนั้น โอเวอร์เฮดเฉลี่ยของการดำเนินการสำหรับตารางแฮชจึงเป็นเพียงการคำนวณแฮชของคีย์ รวมกับการเข้าถึงบัคเก็ตที่เกี่ยวข้องภายในอาร์เรย์ ดังนั้น ตารางแฮชมักจะทำงานในเวลา O(1) และดีกว่าทางเลือกอื่นในสถานการณ์ส่วนใหญ่

ตารางแฮชต้องสามารถจัดการกับการชนกันได้ เมื่อฟังก์ชันแฮชแมปคีย์ที่แตกต่างกันสองคีย์กับบัคเก็ตเดียวกันของอาร์เรย์ แนวทางที่แพร่หลายที่สุดสองวิธีในการแก้ไขปัญหานี้คือ การโยงแบบ แยกจากกันและ การระบุที่อยู่ แบบเปิด [3] [4] [5] [11]ในการโยงที่แยกจากกัน อาร์เรย์จะไม่เก็บค่าของตัวเอง แต่เก็บตัวชี้ไปยังคอนเทนเนอร์อื่น ซึ่งมักจะเป็นรายการความสัมพันธ์ที่เก็บค่าทั้งหมดที่ตรงกับแฮช ในทางกลับกัน ในการระบุที่อยู่แบบเปิด หากพบการชนกันของแฮช ตารางจะค้นหาจุดว่างในอาร์เรย์เพื่อเก็บค่าในลักษณะที่กำหนด โดยปกติแล้วจะดูที่ตำแหน่งถัดไปในอาร์เรย์

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

การใช้งานต้นไม้

ต้นไม้การค้นหาไบนารีที่สมดุลในตัวเอง

แนวทางทั่วไปอีกวิธีหนึ่งคือการใช้อาร์เรย์ที่เชื่อมโยงกับโครงสร้างการค้นหาไบนารีที่ปรับสมดุลในตัวเองเช่นต้นไม้ AVLหรือ ต้นไม้ สีแดง-ดำ (12)

เมื่อเทียบกับตารางแฮช โครงสร้างเหล่านี้มีทั้งข้อดีและข้อเสีย ประสิทธิภาพในกรณีที่แย่ที่สุดของทรีการค้นหาไบนารีที่ปรับสมดุลตัวเองนั้นดีกว่าของตารางแฮชอย่างมีนัยสำคัญ โดยที่เวลาซับซ้อนในสัญกรณ์ O ขนาดใหญ่ของ O(log n ) ซึ่งตรงกันข้ามกับตารางแฮชซึ่งประสิทธิภาพในกรณีที่แย่ที่สุดเกี่ยวข้องกับองค์ประกอบทั้งหมดที่แชร์ที่ฝากข้อมูลเดียว ส่งผลให้ O( n) ความซับซ้อนของเวลา นอกจากนี้ และเช่นเดียวกับทรีการค้นหาแบบไบนารีทั้งหมด ต้นไม้การค้นหาแบบไบนารีที่ปรับสมดุลในตัวเองจะรักษาองค์ประกอบตามลำดับ ดังนั้น การสำรวจองค์ประกอบของมันเป็นไปตามรูปแบบที่น้อยไปหามาก ในขณะที่การสำรวจตารางแฮชอาจส่งผลให้องค์ประกอบต่างๆ อยู่ในลำดับที่ดูเหมือนสุ่ม อย่างไรก็ตาม ตารางแฮชมีความซับซ้อนของเวลาเฉลี่ยกรณีดีกว่ามาก กว่าทรีการค้นหาไบนารีแบบสมดุลในตัวเองของ O(1) และประสิทธิภาพในกรณีที่แย่ที่สุดนั้นไม่น่าเป็นไปได้อย่างมากเมื่อใช้ฟังก์ชัน แฮช ที่ดี

เป็นที่น่าสังเกตว่าสามารถใช้แผนผังการค้นหาแบบไบนารีที่ปรับสมดุลในตัวเองเพื่อใช้งานบัคเก็ตสำหรับตารางแฮชที่ใช้การโยงแยกกัน ซึ่งช่วยให้สามารถค้นหาค่าคงที่ตัวพิมพ์เฉลี่ยได้ แต่รับรองประสิทธิภาพกรณีที่เลวร้ายที่สุดของ O(log n ) อย่างไรก็ตาม สิ่งนี้ทำให้เกิดความซับซ้อนเป็นพิเศษในการนำไปใช้ และอาจทำให้ประสิทธิภาพการทำงานที่แย่ลงสำหรับตารางแฮชที่มีขนาดเล็กกว่า ซึ่งเวลาที่ใช้ในการแทรกและปรับสมดุลทรีมีมากกว่าเวลาที่จำเป็นในการค้นหาเชิงเส้นในองค์ประกอบทั้งหมดของลิงค์ รายการหรือโครงสร้างข้อมูลที่คล้ายกัน [13] [14]

ต้นไม้อื่นๆ

แอสโซซิเอทีฟอาเรย์อาจถูกจัดเก็บไว้ในทรีการค้นหาแบบไบนารีที่ ไม่สมดุล หรือในโครงสร้างข้อมูลเฉพาะสำหรับคีย์บางประเภท เช่นต้นฐาน , พยายาม , อาร์เรย์จูดี้หรือแวน เอ็มเด โบอาสทรี แม้ว่าความสามารถของวิธีการนำไปใช้เหล่านี้ในการเปรียบเทียบกับตารางแฮช แตกต่างกันไป; ตัวอย่างเช่น ต้นไม้ Judy ยังคงระบุให้ทำงานด้วยปริมาณประสิทธิภาพที่น้อยกว่าตารางแฮช ในขณะที่ตารางแฮชที่คัดเลือกมาอย่างดีมักจะมีประสิทธิภาพเพิ่มขึ้นเมื่อเปรียบเทียบกับแผนผังเรดิกซ์แบบปรับได้ โดยอาจมีข้อจำกัดมากกว่าเกี่ยวกับประเภทของข้อมูลที่สามารถจัดการได้ [15]ข้อดีของโครงสร้างทางเลือกเหล่านี้มาจากความสามารถในการจัดการการดำเนินการที่นอกเหนือไปจากโครงสร้างพื้นฐานของอาร์เรย์ที่เชื่อมโยง เช่น การค้นหาการแมปที่มีคีย์ซึ่งใกล้เคียงกับคีย์ที่สอบถามมากที่สุด เมื่อคิวรีไม่มีอยู่ในชุดของการแมป

เปรียบเทียบ

โครงสร้างข้อมูลพื้นฐาน ค้นหาหรือลบ การแทรก สั่งซื้อ
เฉลี่ย กรณีที่เลวร้ายที่สุด เฉลี่ย กรณีที่เลวร้ายที่สุด
ตารางแฮช โอ(1) โอ( ) โอ(1) โอ( ) ไม่
ต้นไม้การค้นหาไบนารีที่สมดุลในตัวเอง O(ล็อกn ) O(ล็อกn ) O(ล็อกn ) O(ล็อกn ) ใช่
ต้นไม้ค้นหาไบนารีที่ไม่สมดุล O(ล็อกn ) โอ( ) O(ล็อกn ) โอ( ) ใช่
คอนเทนเนอร์ตามลำดับของคู่คีย์-ค่า
(เช่นรายการการเชื่อมโยง )
โอ( ) โอ( ) โอ(1) โอ(1) ไม่

พจนานุกรมสั่งการ

คำจำกัดความพื้นฐานของพจนานุกรมไม่ได้กำหนดให้มีคำสั่ง เพื่อรับประกันลำดับการแจงนับแบบตายตัว มักจะใช้เวอร์ชันที่เรียงลำดับของ associative array พจนานุกรมสั่งการมีสองสัมผัส:

  • ลำดับของการแจงนับกำหนดได้เสมอสำหรับชุดคีย์ที่กำหนดโดยการเรียงลำดับ นี่เป็นกรณีสำหรับการใช้งานแบบทรี ตัวแทนหนึ่งรายคือ<map>คอนเทนเนอร์ของ C++ [16]
  • ลำดับของการแจงนับไม่ขึ้นกับคีย์และขึ้นอยู่กับลำดับของการแทรกแทน นี่เป็นกรณีของ "พจนานุกรมที่สั่ง" ใน. NET FrameworkและPython [17] [18]

ความรู้สึกหลังของพจนานุกรมที่ได้รับคำสั่งมักพบบ่อยกว่า สามารถใช้งานได้โดยใช้รายการเชื่อมโยงหรือโดยการวางรายการที่เชื่อมโยง เป็นสองเท่า ที่ด้านบนของพจนานุกรมปกติ วิธีหลัง ซึ่งใช้โดย CPython ก่อนเวอร์ชัน 3.6 มีข้อได้เปรียบในการรักษาความซับซ้อนที่อาจดีขึ้นของการนำไปใช้งานอื่น [19] CPython 3.6+ สร้างพจนานุกรมโดยแยกตารางแฮชออกเป็นอาร์เรย์ที่เรียงลำดับการแทรกของคู่ kv และอาร์เรย์แบบกระจัดกระจาย ("ตารางแฮช") ของดัชนี (20)

รองรับภาษา

แอสโซซิเอทีฟอาเรย์สามารถนำไปใช้ในภาษาการเขียนโปรแกรมใดๆ ก็ได้ในรูปแบบแพ็คเกจ และระบบภาษาจำนวนมากจัดเตรียมไว้เป็นส่วนหนึ่งของไลบรารีมาตรฐาน ในบางภาษา ภาษาเหล่านี้ไม่เพียงแต่สร้างไว้ในระบบมาตรฐานเท่านั้น แต่ยังมีไวยากรณ์พิเศษ ซึ่งมักใช้การห้อยคล้ายอาร์เรย์

การสนับสนุน syntax ในตัวสำหรับ associative arrays ถูกนำมาใช้ในปี 1969 โดยSNOBOL4ภายใต้ชื่อ "table" TMGเสนอตารางที่มีคีย์สตริงและค่าจำนวนเต็ม คางทูมสร้างอาร์เรย์ที่เชื่อมโยงหลายมิติ สามารถเลือกแบบถาวร โครงสร้างข้อมูลหลัก SETLสนับสนุนพวกเขาด้วยการใช้ชุดและแผนที่ที่เป็นไปได้ ภาษาสคริปต์ที่ทันสมัยที่สุด เริ่มต้นด้วยAWKและรวมถึงRexx , Perl , PHP , Tcl , JavaScript , Maple , Python , Ruby , Wolfram Language ,GoและLuaสนับสนุน associative arrays เป็นประเภทคอนเทนเนอร์หลัก ในภาษาอื่นๆ อีกมากมาย ฟังก์ชันเหล่านี้พร้อมใช้งานเป็นฟังก์ชันไลบรารีที่ไม่มีรูปแบบพิเศษ

ในSmalltalk , Objective-C , .NET , [21] Python , REALbasic , Swift , VBAและDelphi [22]จะถูกเรียกว่าพจนานุกรม ในPerl , RubyและSeed7พวกเขาถูกเรียกว่าแฮช ; ในC++ , Java , Go , Clojure , Scala , OCaml , Haskellเรียกว่าmap (ดูแผนที่ (C++) ,unordered_map (C++)และMap); ในCommon LispและWindows PowerShellจะเรียกว่าตารางแฮช (เนื่องจากโดยทั่วไปแล้วทั้งคู่จะใช้การใช้งานนี้); ในMapleและ Lua เรียกว่าtable ในPHPอาร์เรย์ทั้งหมดสามารถเชื่อมโยงกันได้ ยกเว้นว่าคีย์จะจำกัดอยู่ที่จำนวนเต็มและสตริง ใน JavaScript (ดูJSON เพิ่มเติมด้วย ) ออบเจ็กต์ทั้งหมดทำหน้าที่เป็นอาร์เรย์ที่เชื่อมโยงด้วยคีย์ที่มีค่าสตริง ในขณะที่ประเภทแผนที่และ WeakMap จะใช้อ็อบเจ็กต์ตามอำเภอใจเป็นคีย์ ใน Lua พวกมันถูกใช้เป็นส่วนประกอบพื้นฐานสำหรับโครงสร้างข้อมูลทั้งหมด ในVisual FoxProจะเรียกว่าCollections ดิภาษา Dยังรองรับอาร์เรย์ที่เชื่อมโยง [23]

ที่เก็บข้อมูลถาวร

หลายๆ โปรแกรมที่ใช้ associative arrays จำเป็นต้องจัดเก็บข้อมูลนั้นในรูปแบบที่ถาวรกว่าในบางครั้ง เช่น ในไฟล์คอมพิวเตอร์ วิธีแก้ปัญหาทั่วไปสำหรับปัญหานี้คือแนวคิดทั่วไปที่เรียกว่าarchiveหรือserializationซึ่งสร้างข้อความหรือการแสดงไบนารีของอ็อบเจ็กต์ดั้งเดิมที่สามารถเขียนโดยตรงไปยังไฟล์ โดยทั่วไปจะใช้ในรูปแบบอ็อบเจ็กต์พื้นฐาน เช่น .Net หรือ Cocoa ซึ่งรวมถึงฟังก์ชันมาตรฐานที่แปลงข้อมูลภายในเป็นรูปแบบข้อความ โปรแกรมสามารถสร้างการแสดงข้อความที่สมบูรณ์ของกลุ่มวัตถุใดๆ ได้โดยการเรียกใช้เมธอดเหล่านี้ ซึ่งมักจะนำไปใช้งานในคลาสอาร์เรย์ที่เชื่อมโยงฐานเกือบทุกครั้ง [24]

สำหรับโปรแกรมที่ใช้ชุดข้อมูลขนาดใหญ่ พื้นที่จัดเก็บไฟล์ประเภทนี้ไม่เหมาะสม และจำเป็นต้องมีระบบจัดการฐานข้อมูล (DB) ระบบ DB บางระบบจะจัดเก็บอาร์เรย์ที่เชื่อมโยงโดยกำเนิดโดยการทำให้ข้อมูลเป็นอนุกรม จากนั้นจึงจัดเก็บข้อมูลที่จัดลำดับและคีย์ไว้ อาร์เรย์แต่ละรายการสามารถโหลดหรือบันทึกจากฐานข้อมูลได้โดยใช้คีย์เพื่ออ้างอิง ที่เก็บคีย์-ค่าเหล่านี้ถูกใช้มาหลายปีแล้วและมีประวัติตราบเท่าที่ฐานข้อมูลเชิงสัมพันธ์ ทั่วไป (RDB) แต่ขาดมาตรฐาน ด้วยเหตุผลอื่น ๆ ทำให้การใช้งานเฉพาะบางบทบาทเท่านั้น RDB ถูกใช้สำหรับบทบาทเหล่านี้ในกรณีส่วนใหญ่ แม้ว่าการบันทึกอ็อบเจ็กต์ไปยัง RDB อาจมีความซับซ้อน ปัญหาที่เรียกว่าอิมพีแดนซ์อิมพีแดนซ์เชิงวัตถุไม่ตรงกัน.

หลังค.  2010ความต้องการฐานข้อมูลที่มีประสิทธิภาพสูงซึ่งเหมาะสำหรับการประมวลผลแบบคลาวด์และการจับคู่โครงสร้างภายในของโปรแกรมที่ใกล้เคียงกันมากขึ้นซึ่งนำไปสู่ยุคฟื้นฟูศิลปวิทยาในตลาดการจัดเก็บคีย์-ค่า ระบบเหล่านี้สามารถจัดเก็บและดึงข้อมูลอาร์เรย์ที่เชื่อมโยงกันในลักษณะดั้งเดิม ซึ่งสามารถปรับปรุงประสิทธิภาพในเวิร์กโฟลว์ทั่วไปที่เกี่ยวข้องกับเว็บได้อย่างมาก

ดูเพิ่มเติม

อ้างอิง

  1. ^ คอลลินส์ เกรแฮม; ไซม์, โดนัลด์ (1995). "ทฤษฎีแผนที่จำกัด". การพิสูจน์ทฤษฎีบทลอจิกระดับสูงและการประยุกต์ หมายเหตุบรรยายในวิทยาการคอมพิวเตอร์. 971 : 122–137. ดอย : 10.1007/3-540-60275-5_61 . ISBN 978-3-540-60275-0.
  2. แอนเดอร์สสัน, อาร์น (1989). "ขอบเขตที่เหมาะสมที่สุดในปัญหาพจนานุกรม" Proc. การประชุมวิชาการเกี่ยวกับอัลกอริทึมที่เหมาะสมที่สุด หมายเหตุบรรยายในวิทยาการคอมพิวเตอร์. สปริงเกอร์ เวอร์แล็ก. 401 : 106–114. ดอย : 10.1007/3-540-51859-2_10 . ISBN 978-3-540-51859-4.
  3. อรรถa b c d e Goodrich, Michael T. ; Tamassia, Roberto (2006), "9.1 The Map Abstract Data Type", โครงสร้างข้อมูล & อัลกอริธึมใน Java (ฉบับที่ 4), Wiley, pp. 368–371
  4. อรรถa b c d เมห์ลฮอร์น เคิร์ต ; Sanders, Peter (2008), "4 Hash Tables and Associative Arrays", อัลกอริทึมและโครงสร้างข้อมูล: The Basic Toolbox (PDF) , Springer, pp. 81–98
  5. อรรถa b c d Cormen, Thomas H. ; ไลเซอร์สัน, ชาร์ลส์ อี. ; ริเวสต์, โรนัลด์ แอล. ; Stein, Clifford (2001), "11 Hash Tables", Introduction to Algorithms (ฉบับที่ 2), MIT PressและMcGraw-Hill , pp. 221–252, ISBN 0-262-03293-7.
  6. ↑ a b Dietzfelbinger , M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, RE 1994. "Dynamic Perfect Hashing: Upper and Lower Bounds" Archived 2016- 03-04 ที่เครื่องWayback สยาม เจ. คอมพิวเตอร์. 23, 4 (ส.ค. 1994), 738-761 http://portal.acm.org/citation.cfm?id=182370 ดอย : 10.1137/S0097539791194094
  7. ^ Goodrich & Tamassia (2006) , pp. 597–599.
  8. อรรถเป็น สีดำ พอล อี.; สจ๊วต, ร็อบ (2 พฤศจิกายน 2020). "พจนานุกรม" . พจนานุกรมอัลกอริทึมและโครงสร้างข้อมูล สืบค้นเมื่อ26 มกราคม 2022 .
  9. ^ Goodrich & Tamassia (2006) , pp. 389–397.
  10. ^ "ฉันควรใช้ตารางแฮชแทนรายการการเชื่อมโยงเมื่อใด" . กระเพื่อม-คำถามที่พบบ่อย/part2. 1996-02-20.
  11. ^ แคลมเมอร์, เอฟ ; Mazzolini, L. (2006), "ผู้บุกเบิกแผนที่ที่เชื่อมโยง", ต่อ บทคัดย่อ GIS-l 2006 , GIS-I, หน้า 71–74.
  12. โจเอล อดัมส์และแลร์รี ไนฮอฟฟ์ "ต้นไม้ใน STL" . ข้อความอ้างอิง: "ไลบรารีเทมเพลตมาตรฐาน ... คอนเทนเนอร์บางส่วน -- เทมเพลต set<T>, map<T1, T2>, multiset<T> และ multimap<T1, T2> - โดยทั่วไปแล้วจะสร้างขึ้นโดยใช้เทมเพลตพิเศษต้นไม้การค้นหาไบนารีแบบสมดุลในตัวเอง ที่เรียกว่า ต้นไม้ สีแดง-ดำ "
  13. ^ คนุธ โดนัลด์ (1998). ศิลปะแห่งการเขียนโปรแกรมคอมพิวเตอร์ . ฉบับที่ 3: การเรียงลำดับและการค้นหา (ฉบับที่ 2) แอดดิสัน-เวสลีย์. น. 513–558. ISBN 0-201-89685-0.
  14. ^ โพรบสท์ มาร์ก (2010-04-30) "การค้นหาเชิงเส้นเทียบกับไบนารี" สืบค้นเมื่อ2016-11-20 .
  15. อัลวาเรซ วิกเตอร์; ริกเตอร์, สเตฟาน; เฉิน เซียว; Dittrich, Jens (เมษายน 2015). "การเปรียบเทียบระหว่างต้น Radix Tree และตารางแฮช" 2015 IEEE การประชุมนานาชาติครั้งที่ 31 ด้านวิศวกรรมข้อมูล โซล เกาหลีใต้: IEEE: 1227–1238 ดอย : 10.1109/ICDE.2015.7113370 . ISBN 978-1-4799-7964-6. S2CID  17170456 .
  16. ^ "std::map" . th.cppreference.com .
  17. ^ "OrderedDictionary Class (System.Collections.Specialized)" . เอกสาร MS .
  18. ^ "คอลเลกชัน — ประเภทข้อมูลคอนเทนเนอร์ — เอกสาร Python 3.9.0a3 " docs.python.org .
  19. ดิมิทริส ฟาซาราคิส ฮิลเลียร์ด. "พจนานุกรม - OrderedDict ของ Python จำองค์ประกอบได้อย่างไร" . กองล้น
  20. ดิมิทริส ฟาซาราคิส ฮิลเลียร์ด. "พจนานุกรมสั่งเป็น Python 3.6+ หรือไม่" . กองล้น
  21. ^ "พจนานุกรม<TKey, TValue> คลาส" . เอ็มเอสดีเอ็น
  22. ^ "System.Generics.Collections.TDictionary - เอกสาร ประกอบRAD Studio API" docwiki.embarcadero.com . สืบค้นเมื่อ2017-04-18 .
  23. ^ "Associative Arrays ภาษาการเขียนโปรแกรม D " ดาวอังคารดิจิตอล
  24. ^ "Archives and Serializations Programming Guide" , Apple Inc., 2012

ลิงค์ภายนอก