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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 18 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน)
แถว 1: แถว 1:
 +
จดบันทึกคำบรรยายโดย:
 +
 +
g5314550016 น.ส.กนกวรรณ เลิศประเสริฐพันธ์
 +
 +
g5314550121 น.ส.ปนัดดา ชุมกระโทก
 +
     
 +
g5314552281 น.ส.เบญจวรรณ เจริญพร     
 +
 +
g5314550172 นายวีระยุทธ วิชัยดิษฐ์
 +
 +
----
 +
 +
 
== '''Hash Table''' ==
 
== '''Hash Table''' ==
  
  ''Hash Table'' เป็นโครงสร้างข้อมูลในรูปแบบตาราง ซึ่งอาจใช้แถวลำดับในการทำ ใช้ในการเก็บข้อมูลจำนวนมาก เพื่อสะดวกต่อการเก็บและค้นหา โดยการผ่านฟังก์ชันแฮช
+
''Hash Table'' เป็นโครงสร้างข้อมูลในรูปแบบตาราง ซึ่งอาจใช้แถวลำดับในการทำ ใช้ในการเก็บข้อมูลจำนวนมาก เพื่อสะดวกต่อการเก็บและค้นหา โดยการผ่านฟังก์ชันแฮช
 
   
 
   
== ลักษณะของ Hash Table ==
+
'''ลักษณะของ Hash Table'''
  
  ''Hash Table'' มักใช้แถวลำดับหรือ Map ขนาดใหญ่เพื่อใช้ในการจัดการเก็บข้อมูลจำนวนมาก โดยมีลักษณะการเก็บแบบดัชนีได้ (Indexing) วิธีการเก็บนั้นจะนำข้อมูลที่จะนำมาเก็บผ่านฟังก์ชันฟังก์ชันหนึ่ง(เราจะเรียกข้อมูลที่ผ่านฟังก์ชันนั้นว่า key) ซึ่งเรียกว่าฟังก์ชันแฮชจะได้เลขซึ่งจำเพาะกับข้อมูลนั้น กล่าวคือ ข้อมูลแต่ละตัวเมื่อผ่านฟังก์ชันแฮชแล้ว จะได้เลขที่แตกต่างกัน แล้วจึงนำข้อมูลไปเก็บไว้ในตาราง แถวลำดับ หรือ Map ที่กำหนดไว้
+
'''Hash Table''' มักใช้แถวลำดับหรือ Map ขนาดใหญ่เพื่อใช้ในการจัดการเก็บข้อมูลจำนวนมาก โดยมีลักษณะการเก็บแบบดัชนีได้ (Indexing) วิธีการเก็บนั้นจะนำข้อมูลที่จะนำมาเก็บผ่านฟังก์ชัน ฟังก์ชันหนึ่ง(เราจะเรียกข้อมูลที่ผ่านฟังก์ชันนั้นว่า key) ซึ่งเรียกว่าฟังก์ชันแฮชจะได้เลขซึ่งจำเพาะกับข้อมูลนั้น กล่าวคือ ข้อมูลแต่ละตัวเมื่อผ่านฟังก์ชันแฮชแล้ว จะได้เลขที่แตกต่างกัน แล้วจึงนำข้อมูลไปเก็บไว้ในตารางแถวลำดับ หรือ Map ที่กำหนดไว้
  
[[ไฟล์:1.jpg]]  ให้ Hash Table มีจำนวนช่องทั้งหมด m ช่อง และ มี key เท่ากับ n kay
+
[[ไฟล์:1.jpg]]   
                  h : µ -> {0,1,2,…,m-1} 
 
                  ต้องการหาข้อมูลที่มีค่าเท่ากับ X
 
                  สำหรับWorst case คือกรณีที่ข้อมูลลงช่องเดียวกัน
 
  
 +
ให้ Hash Table มีจำนวนช่องทั้งหมด m ช่อง และ มี key เท่ากับ n kay
 +
  h : µ -> {0,1,2,…,m-1} 
 +
  ต้องการหาข้อมูลที่มีค่าเท่ากับ X
 +
  สำหรับWorst case คือกรณีที่ข้อมูลลงช่องเดียวกัน
  
 
== Chaining ==
 
== Chaining ==
แถว 25: แถว 39:
 
Goal : หา Expectation m,L E[L]
 
Goal : หา Expectation m,L E[L]
 
[[ไฟล์:3.jpg]]
 
[[ไฟล์:3.jpg]]
 
  
 
== Open Addessing ==
 
== Open Addessing ==
แถว 32: แถว 45:
  
 
ตัวอย่างวิธีการหาข้อมูลใน Open Addessing
 
ตัวอย่างวิธีการหาข้อมูลใน Open Addessing
 +
 
1.Linear Probing
 
1.Linear Probing
 
   h : u->[0,1,…,m-1]
 
   h : u->[0,1,…,m-1]
แถว 47: แถว 61:
  
 
== Hash Function ==
 
== 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]]
 +
 +
 +
----

รุ่นแก้ไขปัจจุบันเมื่อ 13:07, 5 ตุลาคม 2553

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

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