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

มีถัง n ถัง ลูกบอล m ลูก โยนลูกบอลไปสุ่มๆ ลงถังไหนก็ได้ด้วยความน่าจะเป็นที่เท่ากัน สิ่งที่สนใจคือ

• ถังที่มีลูกบอลมากกว่า 1 ลูก
• จำนวนถังว่าง
• จำนวนลูกบอลในถังที่มีจำนวนมากที่สุด

ในการเรียนความน่าจะเป็น หรือการทดลองแบบสุ่มจำเป็นต้องเข้าใจ ศัพท์ต่างๆ ดังนี้ Random experiment คือการทดลองแบบสุ่ม ซึ่งจะได้ผลลัพธ์ออกมาคือ outcome outcome เป็นสิ่งที่สังเกตได้ ซึ่งในการทดลองแต่ละครั้งก็จะได้ outcome ออกมาหลายๆ อัน เซตของ outcome ทั้งหมดที่เป็นไปได้ เรียกว่า sample space ตามภาพด้านล่าง