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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 1: แถว 1:
 
คณะผู้จัดทำ
 
คณะผู้จัดทำ
  
น.ส.ปนัดดา ชุมกระโทก
+
g5314550016 น.ส.กนกวรรณ เลิศประเสริฐพันธ์
น.ส.เบญจวรรณ เจริญพร
+
g5314550121 น.ส.ปนัดดา ชุมกระโทก       
น.ส.กนกวรรณ เลิศประเสริฐพันธ์
+
g5314552281 น.ส.เบญจวรรณ เจริญพร     
  
 
----
 
----

รุ่นแก้ไขเมื่อ 05:01, 20 สิงหาคม 2553

คณะผู้จัดทำ

g5314550016 น.ส.กนกวรรณ เลิศประเสริฐพันธ์ g5314550121 น.ส.ปนัดดา ชุมกระโทก g5314552281 น.ส.เบญจวรรณ เจริญพร



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