204512-53/lecture5

จาก Theory Wiki
รุ่นแก้ไขเมื่อ 13:07, 5 ตุลาคม 2553 โดย Deltanulls (คุย | มีส่วนร่วม)
(ต่าง) ←รุ่นแก้ไขก่อนหน้า | รุ่นแก้ไขล่าสุด (ต่าง) | รุ่นแก้ไขถัดไป→ (ต่าง)
ไปยังการนำทาง ไปยังการค้นหา

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

g5314550016 น.ส.กนกวรรณ เลิศประเสริฐพันธ์

g5314550121 น.ส.ปนัดดา ชุมกระโทก

g5314552281 น.ส.เบญจวรรณ เจริญพร

g5314550172 นายวีระยุทธ วิชัยดิษฐ์



Hash Table

Hash Table เป็นโครงสร้างข้อมูลในรูปแบบตาราง ซึ่งอาจใช้แถวลำดับในการทำ ใช้ในการเก็บข้อมูลจำนวนมาก เพื่อสะดวกต่อการเก็บและค้นหา โดยการผ่านฟังก์ชันแฮช

ลักษณะของ Hash Table

Hash Table มักใช้แถวลำดับหรือ Map ขนาดใหญ่เพื่อใช้ในการจัดการเก็บข้อมูลจำนวนมาก โดยมีลักษณะการเก็บแบบดัชนีได้ (Indexing) วิธีการเก็บนั้นจะนำข้อมูลที่จะนำมาเก็บผ่านฟังก์ชัน ฟังก์ชันหนึ่ง(เราจะเรียกข้อมูลที่ผ่านฟังก์ชันนั้นว่า key) ซึ่งเรียกว่าฟังก์ชันแฮชจะได้เลขซึ่งจำเพาะกับข้อมูลนั้น กล่าวคือ ข้อมูลแต่ละตัวเมื่อผ่านฟังก์ชันแฮชแล้ว จะได้เลขที่แตกต่างกัน แล้วจึงนำข้อมูลไปเก็บไว้ในตารางแถวลำดับ หรือ Map ที่กำหนดไว้

1.jpg

ให้ Hash Table มีจำนวนช่องทั้งหมด m ช่อง และ มี key เท่ากับ n kay

  h : µ -> {0,1,2,…,m-1}  
  ต้องการหาข้อมูลที่มีค่าเท่ากับ X
  สำหรับWorst case คือกรณีที่ข้อมูลลงช่องเดียวกัน

Chaining

2.jpg

กำหนด Assumption สำหรับ key x ≠ y , i <- h(x)

  Pr[h(x) = h(y)]

เวลาที่ใช้ในการค้นหา -> O (1+α) 1. คำนวน h(x) -> O(1) 2. คำนวน chain -> O(α) ให้ L เป็นตัวแปรสุ่มแทนความยาวของ chain ที่ตำแหน่ง h(x) Goal : หา Expectation m,L E[L] 3.jpg

Open Addessing

จำนวนช่องควรจะใช้เป็นจำนวนเฉพาะ 4.jpg

ตัวอย่างวิธีการหาข้อมูลใน Open Addessing

1.Linear Probing

  h : u->[0,1,…,m-1]
  h[x]
  h[x+1]
  .
  .
  .

2. Linear ยกกำลัง 2

  h[x]
  5.jpg
  6.jpg


Hash Function

7.jpg

8.jpg


9.jpg

10.jpg

11.jpg

Definition : จะเรียก H ว่าเป็น 2 – Universal hash family ถ้า

12.jpg

13.jpg

14.jpg

Hash Function (Continues)

15.jpg

16.jpg

17.jpg