ในที่นี้เราจะพูดถึงเรื่องการแฮชกับการแบ่ง สำหรับสิ่งนี้เราใช้ฟังก์ชันแฮช -
ℎ(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚
ในการใช้ฟังก์ชันแฮชนี้ เรารักษาอาร์เรย์ A[0, … m – 1] โดยที่แต่ละองค์ประกอบของอาร์เรย์เป็นตัวชี้ไปที่ส่วนหัวของรายการที่เชื่อมโยง รายการที่เชื่อมโยง Li ชี้ไปที่องค์ประกอบอาร์เรย์ A[i] เก็บองค์ประกอบทั้งหมด x เพื่อให้ h(x) =i เทคนิคนี้เรียกว่าการแฮชด้วยการโยง
ในตารางแฮชดังกล่าว หากเราต้องการเพิ่มองค์ประกอบ x จะต้องใช้เวลา O(1) เราคำนวณดัชนี i =h(x) จากนั้นผนวกหรือเติม x ลงในรายการ Li หากเราต้องการค้นหาหรือลบองค์ประกอบ กระบวนการนั้นไม่ง่ายนัก เราต้องหาดัชนี i =h(x) จากนั้นสำรวจรายการหลี่ จนกว่าเราจะถึงค่าที่ต้องการหรือรายการหมด การดำเนินการนี้ใช้เวลาตามขนาดของรายการ Li . หากเซต S ของเรามีองค์ประกอบ 0, m, 2m, 3m, …., nm องค์ประกอบทั้งหมดที่จัดเก็บไว้ใน L0 จะใช้เวลาเชิงเส้นในการค้นหาและลบ
สถานการณ์แบบนี้หายากมาก ตัวอย่างเช่น ถ้า S มีการกระจายอย่างสม่ำเสมอและเป็นอิสระในชุดสากล U และ u เป็นจำนวนเท่าของ m ดังนั้นขนาดที่คาดไว้ของแต่ละรายการ Li เป็นเพียง n/m ในกรณีนี้ การค้นหาและการลบจะใช้เวลา O (1 + α) ระยะเวลา เพื่อหลีกเลี่ยงสถานการณ์ดังกล่าว เราต้องเลือก m อย่างชาญฉลาด โดยทั่วไป เราหลีกเลี่ยง m เป็นกำลัง 2 โดยแนะนำให้ m เป็นจำนวนเฉพาะที่ไม่เข้าใกล้กำลัง 2 มากเกินไป
