ผลต่างระหว่างรุ่นของ "204512-53/lecture4"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 11: แถว 11:
  
  
== Hashing ==
+
==Hashing ==
 
+
มี key กับ value  K ∈{0,1,…,M-1}  M มีค่าเยอะมากๆ ปกติแล้วถ้ามีข้อมูล n ตัว จะใช้ array เก็บ n ช่อง หรือ cn ช่อง (เมื่อ c เป็นค่าคงที่) ให้ m เป็นขนาดของ array หรือขนาดของ table  ซึ้ง  m >= n<br />
มี 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 function  h ที่รับ k เข้าไปแล้วทำการ map ไป space ของ table(0,1,…,m-1) เมื่อเรารู้ค่า key  เราก็จะรู้ว่าจะไปหาข้อมูลที่ ช่องไหน ถ้าข้อมูลที่แตกต่างกันลงกันคนละช่อง table ก็เปรียบเป็น array นั้นเอง เรื่องที่สนในการทำ Hashing มีสองเรื่องคือ 1. วิธีหรือฟังก์ชันที่ใช้ในการคำนวณหาค่าที่ตำแหน่งที่ใช้เก็บข้อมูล  2. การแก้ปัญหาเมื่อเกิดการชนกันเกิดขึ้น ตัวอย่างการแก้ปัญหาเมื่อเกิดการชนกันคือ การใช้วิธี chaining ในการแก้ปัญหาการชนกันโดยการใช้ link list มาใช้เก็บข้อมูลที่ชนกันตามภาพด้านล้าง  หรือแก้โดยวิธี open addressing คือข้อมูลที่ชนกันจะถูกเก็บลงในช่องถัดไปที่ว่าง ตามภาพด้านล้าง
 
[[ไฟล์:2553w04_hash01.jpg|center|700px|]]
 
[[ไฟล์:2553w04_hash01.jpg|center|700px|]]
 +
การวิเคราะห์ปัญหาการใช้ hash สิ่งแรกคือ วิเคราะห์ว่า hash function นั้นดี ซึ่งมีอยู่จริงแต่อาจไม่ดีสำหรับสำหรับทุกๆ input  สำหรับ  hash function ที่ดีนั้นควรจะมีการสุ่มแบบกระจาย สำหรับการวิเคราะห์จะอาศัยการวิเคราะห์ การทดลองตระกูล Ball and Bin
 +
 +
==Ball and Bin ==

รุ่นแก้ไขเมื่อ 17:11, 9 สิงหาคม 2553

บันทึกคำบรรยายวิชา 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 คือข้อมูลที่ชนกันจะถูกเก็บลงในช่องถัดไปที่ว่าง ตามภาพด้านล้าง

2553w04 hash01.jpg

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

Ball and Bin