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