การแฮช (Hashing)

การหาแถวหนึ่งในห้าสิบล้านโดยไม่ดู

• registers ห้างสรรพสินค้าสแกน barcode และราคาปรากฏก่อนมือคุณออกจากสินค้า ไฟล์ผลิตภัณฑ์มีห้าสิบล้านบรรทัด
• ไม่มีใครค้นหาพวกมัน หมายเลขบาร์โค้ดผ่านการคำนวณสั้นๆ ที่สร้างตำแหน่งขึ้น และคอมพิวเตอร์อ่านตำแหน่งนั้น: อ่านครั้งเดียว เปรียบเทียบไม่ได้ ใช้เวลาเท่าเดิมไม่ว่าไฟล์จะมีแถวห้าสิบแถวหรือห้าสิบล้านแถว
• การคำนวณนี้คือ hash function และแนวคิดทั้งหมดขึ้นอยู่กับมัน: อย่าเก็บข้อมูลในที่它将 fit, เก็บมันในที่ key ของมันบอกว่าเป็นเจ้าของ
• บทเรียนนี้คือ algorithms hashing, เกิดอะไรขึ้นเมื่อสอง keys ต้องการ slot เดียวกัน,以及如何 search และ insert

Hash function

• Hash function หรือ hashing algorithm รับ key ของเรคอร์ดและผลิต address ที่เรคอร์ดถูกจัดเก็บ
• ตัวที่ดีควร fast, deterministic (key เดียวกันให้ address เหมือนกันเสมอ) และกระจาย keys evenlyAcross the available slots
• สำหรับช่อง $N$ หลักสูตรคาดหวัง 3 วิธี: โมดูลัส (modulo), address ← key MOD N; การพับ (folding), แบ่งคีย์เป็นส่วน แล้วบวกกัน จากนั้น MOD $N$; แฮชสตริง (string hash), บวกค่าโค้ดของตัวอักษรทั้งหมด แล้ว MOD $N$

ตัวอย่างทำแบบฝึกหัด: ใช้แต่ละอัลกอริทึม

การชนกัน (Collisions)

• การชนกัน เกิดขึ้นเมื่อคีย์ที่แตกต่างกันสองตัวแฮชไปที่ ที่อยู่เดียวกัน ในระบบแฮชใดๆ และไฟล์จริงใด การชนกันเป็นเรื่องแน่นอน ดังนั้นกลยุทธ์การจัดการจึงเป็นส่วนหนึ่งของการออกแบบตั้งแต่ต้น ไม่ใช่สิ่งที่มาคิดทีหลัง
• Linear probing จะบันทึกข้อมูลลงใน ช่องว่างถัดไป โดยวนกลับไปยังจุดเริ่มต้นเมื่อถึงท้ายตาราง ทำง่ายแต่ข้อมูลจะ รวมกลุ่ม (cluster): พื้นที่เต็มจะขยายออก และทุกคีย์ที่ตกลงในพื้นที่นี้จะใช้เวลาค้นหานานขึ้น
• Chaining ทำให้แต่ละช่องเป็นหัวของ ลิสต์เชื่อมโยง (linked list) ของบันทึกทั้งหมดที่แฮชมาที่ช่องนั้น ไม่มีการรวมกลุ่ม แต่ใช้หน่วยความจำเพิ่มสำหรับพอยน์เตอร์และต้องเดินตามลิสต์เล็กน้อย
• Rehashing ใช้ฟังก์ชันแฮชที่สองเพื่อหาช่องอื่น กระจายคีย์ได้ดีขึ้นแต่เสียเวลาในการคำนวณมากขึ้น

การค้นหาและการแทรก

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

ตัวอย่างทำแบบฝึกหัด: ติดตามการชนกัน

ปัจจัยโหลด (Load factor)

• ปัจจัยโหลด คือจำนวนบันทึกหารด้วยจำนวนช่อง เป็นตัวเลขเดียวที่ใช้ทำนายประสิทธิภาพของตาราง
• ต่ำกว่าประมาณ 70% การค้นหาค่าเฉลี่ยจะอยู่ใกล้การอ่านเพียงครั้งเดียว เหนือจากนี้ ลำดับการ probe จะยาวขึ้นอย่างมากและประสิทธิภาพจะลดลงสู่การค้นหาแบบเชิงเส้น
• ทางแก้คือทำให้ตารางใหญ่ขึ้นและ rehash บันทึกทุกอย่างเข้าไปใหม่ นี่คือเหตุผลที่ตารางแฮชถูกกำหนดขนาดตามข้อมูลที่มันจะรองรับในอนาคต ไม่ใช่ข้อมูลที่มีอยู่ในปัจจุบัน

คะแนนที่หลุดหายไป

คุณเข้าใจแล้ว