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