Skip to main content

อาร์เรย์เชื่อมโยงคืออะไร?

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

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

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

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

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

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