ผลต่างระหว่างรุ่นของ "204512-53/lecture5"
ไปยังการนำทาง
ไปยังการค้นหา
Deltanulls (คุย | มีส่วนร่วม) |
Deltanulls (คุย | มีส่วนร่วม) |
||
| แถว 2: | แถว 2: | ||
''Hash Table'' เป็นโครงสร้างข้อมูลในรูปแบบตาราง ซึ่งอาจใช้แถวลำดับในการทำ ใช้ในการเก็บข้อมูลจำนวนมาก เพื่อสะดวกต่อการเก็บและค้นหา โดยการผ่านฟังก์ชันแฮช | ''Hash Table'' เป็นโครงสร้างข้อมูลในรูปแบบตาราง ซึ่งอาจใช้แถวลำดับในการทำ ใช้ในการเก็บข้อมูลจำนวนมาก เพื่อสะดวกต่อการเก็บและค้นหา โดยการผ่านฟังก์ชันแฮช | ||
| − | |||
| − | |||
== ลักษณะของ Hash Table == | == ลักษณะของ Hash Table == | ||
| แถว 9: | แถว 7: | ||
''Hash Table'' มักใช้แถวลำดับหรือ Map ขนาดใหญ่เพื่อใช้ในการจัดการเก็บข้อมูลจำนวนมาก โดยมีลักษณะการเก็บแบบดัชนีได้ (Indexing) วิธีการเก็บนั้นจะนำข้อมูลที่จะนำมาเก็บผ่านฟังก์ชันฟังก์ชันหนึ่ง(เราจะเรียกข้อมูลที่ผ่านฟังก์ชันนั้นว่า key) ซึ่งเรียกว่าฟังก์ชันแฮชจะได้เลขซึ่งจำเพาะกับข้อมูลนั้น กล่าวคือ ข้อมูลแต่ละตัวเมื่อผ่านฟังก์ชันแฮชแล้ว จะได้เลขที่แตกต่างกัน แล้วจึงนำข้อมูลไปเก็บไว้ในตาราง แถวลำดับ หรือ Map ที่กำหนดไว้ | ''Hash Table'' มักใช้แถวลำดับหรือ Map ขนาดใหญ่เพื่อใช้ในการจัดการเก็บข้อมูลจำนวนมาก โดยมีลักษณะการเก็บแบบดัชนีได้ (Indexing) วิธีการเก็บนั้นจะนำข้อมูลที่จะนำมาเก็บผ่านฟังก์ชันฟังก์ชันหนึ่ง(เราจะเรียกข้อมูลที่ผ่านฟังก์ชันนั้นว่า key) ซึ่งเรียกว่าฟังก์ชันแฮชจะได้เลขซึ่งจำเพาะกับข้อมูลนั้น กล่าวคือ ข้อมูลแต่ละตัวเมื่อผ่านฟังก์ชันแฮชแล้ว จะได้เลขที่แตกต่างกัน แล้วจึงนำข้อมูลไปเก็บไว้ในตาราง แถวลำดับ หรือ Map ที่กำหนดไว้ | ||
| − | [[ไฟล์:1.jpg]] | + | [[ไฟล์: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 == | |
| − | |||
| − | |||
| − | |||
รุ่นแก้ไขเมื่อ 04:06, 20 สิงหาคม 2553
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]
