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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 49: แถว 49:
 
== Hash Function ==
 
== Hash Function ==
 
[[ไฟล์:7.jpg]]
 
[[ไฟล์:7.jpg]]
 +
 
[[ไฟล์:8.jpg]]
 
[[ไฟล์:8.jpg]]
 +
 
[[ไฟล์:9.jpg]]
 
[[ไฟล์:9.jpg]]
 +
 
[[ไฟล์:10.jpg]]
 
[[ไฟล์:10.jpg]]
 +
 
[[ไฟล์:11.jpg]]
 
[[ไฟล์:11.jpg]]
  
 
Definition : จะเรียก H ว่าเป็น 2 – Universal hash family ถ้า
 
Definition : จะเรียก H ว่าเป็น 2 – Universal hash family ถ้า
 +
 
[[ไฟล์:12.jpg]]
 
[[ไฟล์:12.jpg]]
 +
 
[[ไฟล์:13.jpg]]
 
[[ไฟล์:13.jpg]]
 +
 
[[ไฟล์:14.jpg]]
 
[[ไฟล์:14.jpg]]
 
  
 
== Hash Function (Continues) ==
 
== Hash Function (Continues) ==

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

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 ไฟล์:18.jpg