ผลต่างระหว่างรุ่นของ "204512-53/lecture5"
Deltanulls (คุย | มีส่วนร่วม) |
Deltanulls (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 19 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 1: | แถว 1: | ||
| − | + | จดบันทึกคำบรรยายโดย: | |
| + | |||
| + | 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} | h : µ -> {0,1,2,…,m-1} | ||
ต้องการหาข้อมูลที่มีค่าเท่ากับ X | ต้องการหาข้อมูลที่มีค่าเท่ากับ X | ||
สำหรับWorst case คือกรณีที่ข้อมูลลงช่องเดียวกัน | สำหรับ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]] | ||
| + | |||
| + | |||
| + | ---- | ||
รุ่นแก้ไขปัจจุบันเมื่อ 13:07, 5 ตุลาคม 2553
จดบันทึกคำบรรยายโดย:
g5314550016 น.ส.กนกวรรณ เลิศประเสริฐพันธ์
g5314550121 น.ส.ปนัดดา ชุมกระโทก
g5314552281 น.ส.เบญจวรรณ เจริญพร
g5314550172 นายวีระยุทธ วิชัยดิษฐ์
Hash Table
Hash Table เป็นโครงสร้างข้อมูลในรูปแบบตาราง ซึ่งอาจใช้แถวลำดับในการทำ ใช้ในการเก็บข้อมูลจำนวนมาก เพื่อสะดวกต่อการเก็บและค้นหา โดยการผ่านฟังก์ชันแฮช
ลักษณะของ Hash Table
Hash Table มักใช้แถวลำดับหรือ Map ขนาดใหญ่เพื่อใช้ในการจัดการเก็บข้อมูลจำนวนมาก โดยมีลักษณะการเก็บแบบดัชนีได้ (Indexing) วิธีการเก็บนั้นจะนำข้อมูลที่จะนำมาเก็บผ่านฟังก์ชัน ฟังก์ชันหนึ่ง(เราจะเรียกข้อมูลที่ผ่านฟังก์ชันนั้นว่า key) ซึ่งเรียกว่าฟังก์ชันแฮชจะได้เลขซึ่งจำเพาะกับข้อมูลนั้น กล่าวคือ ข้อมูลแต่ละตัวเมื่อผ่านฟังก์ชันแฮชแล้ว จะได้เลขที่แตกต่างกัน แล้วจึงนำข้อมูลไปเก็บไว้ในตารางแถวลำดับ หรือ Map ที่กำหนดไว้
ให้ Hash Table มีจำนวนช่องทั้งหมด m ช่อง และ มี key เท่ากับ n kay
h : µ -> {0,1,2,…,m-1}
ต้องการหาข้อมูลที่มีค่าเท่ากับ X
สำหรับWorst case คือกรณีที่ข้อมูลลงช่องเดียวกัน
Chaining
กำหนด 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]
Open Addessing
จำนวนช่องควรจะใช้เป็นจำนวนเฉพาะ
ตัวอย่างวิธีการหาข้อมูลใน Open Addessing
1.Linear Probing
h : u->[0,1,…,m-1] h[x] h[x+1] . . .
2. Linear ยกกำลัง 2
h[x]
Hash Function
Definition : จะเรียก H ว่าเป็น 2 – Universal hash family ถ้า
Hash Function (Continues)
