204512-53/lecture4

บันทึกคำบรรยายวิชา 204512-53 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

จดบันทึกคำบรรยายโดย:

นายกฤตกรณ์ ศรีวันนา	G5314550024
นายณัฐพล จารุพัฒนะสิริกุล	G5314550067
นายพงศกร สุระธรรม	G5314550130
นายวุฒิชัย วภักดิ์เพชร	G5314550181

Hashing

มี key กับ value K ∈{0,1,…,M-1} M มีค่าเยอะมากๆ ปกติแล้วถ้ามีข้อมูล n ตัว จะใช้ array เก็บ n ช่อง หรือ cn ช่อง (เมื่อ c เป็นค่าคงที่) ให้ m เป็นขนาดของ array หรือขนาดของ table ซึ้ง m >= n
มี hash function h ที่รับ k เข้าไปแล้วทำการ map ไป space ของ table(0,1,…,m-1) เมื่อเรารู้ค่า key เราก็จะรู้ว่าจะไปหาข้อมูลที่ ช่องไหน ถ้าข้อมูลที่แตกต่างกันลงกันคนละช่อง table ก็เปรียบเป็น array นั้นเอง เรื่องที่สนในการทำ Hashing มีสองเรื่องคือ 1. วิธีหรือฟังก์ชันที่ใช้ในการคำนวณหาค่าที่ตำแหน่งที่ใช้เก็บข้อมูล 2. การแก้ปัญหาเมื่อเกิดการชนกันเกิดขึ้น ตัวอย่างการแก้ปัญหาเมื่อเกิดการชนกันคือ การใช้วิธี chaining ในการแก้ปัญหาการชนกันโดยการใช้ link list มาใช้เก็บข้อมูลที่ชนกันตามภาพด้านล้าง หรือแก้โดยวิธี open addressing คือข้อมูลที่ชนกันจะถูกเก็บลงในช่องถัดไปที่ว่าง ตามภาพด้านล้าง

การวิเคราะห์ปัญหาการใช้ hash สิ่งแรกคือ วิเคราะห์ว่า hash function นั้นดี ซึ่งมีอยู่จริงแต่อาจไม่ดีสำหรับสำหรับทุกๆ input สำหรับ hash function ที่ดีนั้นควรจะมีการสุ่มแบบกระจาย สำหรับการวิเคราะห์จะอาศัยการวิเคราะห์ การทดลองตระกูล Ball and Bin

Ball and Bin