ให้เรตสมาชิก: 5 / 5

ดาวใช้งานดาวใช้งานดาวใช้งานดาวใช้งานดาวใช้งาน
 

Open addressing คืออะไร ?

กระบวนการทำงานของ Open Addressing

 

Open addressing คือ การแก้ไขปัญหาการชนกันของฟังก์ชันแฮชตรงกัน ทำให้เกิดการเก็บที่เดียวกันเมื่อเกิดการชนเกิดขึ้นวิธีการของ Open addressing คือการหาช่องในตารางแฮชใหม่โดยกระโดดไปจากที่เดิมเป็นฟังก์ชันหนึ่ง จนกว่าจะหาช่องว่างเจอจึงจะใส่ค่าลงไป 

 

Open Addressing วิธีนี้เราจะค้นหาค่าตำเเหน่งถัดไปที่ช่องว่าง แล้วนำข้อมูลที่ได้มาในภายหลังไปเก็บไว้

แบ่งออกเป็น 3 ประเภท

  • Open addressing with Linear Probing
  • Open addressing with Quadratic Probing
  • Open addressing with Double Hashing

 

Linear Probing

เป็นการประยุกต์ฟังก์ชันเชิงเส้นในการหาตำเเหน่งใหม่ เช่นการเลือก F(i) = i เป็นการเสาะหาตำเเหน่งถัดจากที่เกิด Collision เพื่อใช้เป็นที่เก็บข้อมูลหากตำแหน่งถัดไปถูกจับจองโดยข้อมูลที่มีอยู่ก่อน ก็จะขยับไปตำเเหน่งถัดไปอีก 1 หนึ่งช่อง (ในลักษณะการขยับไปเรื่อย ๆ แบบเชิงเส้น) เช่นนี้เรื่อยไปจนกว่าจะเจอตำเเหน่งว่าง จึงจะเก็บข้อมูลลงในช่องดังกล่าว จะเห็นว่าวิธีการนี้ล่าช้าทั้งในระหว่างการสืบค้น เพื่อเพิ่มข้อมูล

 

Quadratic Probing

เพื่อแก้ปัญหาความล่าช้าของวิธี Linear Probing จึงมีการเลือก Collision resolution function เพื่อลดความล่าช้าในการหาตำเเหน่งใหม่หลังจากที่เกิด Collision ฟังก์ชันที่ใช้อยู่ในรูปแบบเดียวกันกับ Linear Probing

 

Double Hashing

เป็นความพยายามแก้ปัญหาของ Linear Probing และ Quadratic Probing ที่เสาะหาในตำเเหน่งที่ซ้ำ ๆ อันเป็นสาเหตุของการชนครั้งเเล้วครั้งเล่า โดยอาศัย randomness ของ hash function ในการหาตำเเหน่งใหม่หลังจากการชนกันขึ้น Collision resolution function

 

จากบทความสามารถสรุปได้ว่า Open addressing เป็นวิธีการแก้ปัญหาการชนกันของฟังก์ชันแฮชที่ตรงกัน ทำให้เกิดการเก็บค่าไว้ที่เดียวกัน โดยวิธีการของ Open addressing คือเมื่อเกิดการชนกันของฟังก์ชัน จะทำการหาช่องในตารางแฮชใหม่โดยกระโดดไปจากเดิมเป็นฟังชันหนึ่ง หรือจนกว่าจะหาช่องว่างเจอเเละใส่ค่าลงไป 

 

ช่องทางการศึกษาเพิ่มเติมข่าวสารที่น่าสนใจเกี่ยวกับ : ความหมายคำ คืออะไร

กระทู้ล่าสุดจากเว็บบอร์ด
หัวข้อกระทู้
ตอบ
เปิดดู
ล่าสุด
อยากทราบวิธีการแก้ไข ภาษาไทยกลายอักษรแปลกๆ
โดย Ittichai_chupol จ 25 พฤษภาคม 2020 4:35 pm บอร์ด Programming - PHP
1
19
จ 25 พฤษภาคม 2020 5:43 pm โดย thatsawan
อยากทราบวิธีการ แบบคอลัมเป็น 3 คอลีม โดยใช้ tag <dl>
โดย Ittichai_chupol จ 25 พฤษภาคม 2020 11:56 am บอร์ด HTML CSS
1
26
จ 25 พฤษภาคม 2020 2:42 pm โดย thatsawan
บันทึกประชุม มารียา ซีฟู้ดส์
โดย thatsawan จ 25 พฤษภาคม 2020 11:40 am บอร์ด มารียา ซีฟู้ดส์ (Main)
0
1
จ 25 พฤษภาคม 2020 11:40 am โดย thatsawan
10 สุดยอดสตรีทฟู้ดในแอฟริกาตะวันตก
โดย Anonymous อ 24 พฤษภาคม 2020 9:58 pm บอร์ด พูดคุยเรื่องทั่วไป จับฉ่าย
0
35
อ 24 พฤษภาคม 2020 9:58 pm โดย บุคคลทั่วไป
ข้อมูลสำหรับทำระบบ
โดย mindphp อ 24 พฤษภาคม 2020 4:07 am บอร์ด มารียา ซีฟู้ดส์ (Main)
0
3
อ 24 พฤษภาคม 2020 4:07 am โดย mindphp
อัพเดดความคืบหน้า / Progress - มารียา ซีฟู้ดส์
โดย mindphp อ 24 พฤษภาคม 2020 4:07 am บอร์ด มารียา ซีฟู้ดส์ (Main)
0
3
อ 24 พฤษภาคม 2020 4:07 am โดย mindphp
อัพเดด Template เว็บไซต์ FDD (V2)
โดย mindphp อ 24 พฤษภาคม 2020 3:51 am บอร์ด FDD (Main)
0
1
อ 24 พฤษภาคม 2020 3:51 am โดย mindphp
R - ปรับกราฟฟิก ของเว็บ FDD
โดย mindphp อ 24 พฤษภาคม 2020 3:50 am บอร์ด FDD (Main)
0
2
อ 24 พฤษภาคม 2020 3:50 am โดย mindphp
ความคืบหน้า / Progress
โดย mindphp อ 24 พฤษภาคม 2020 3:46 am บอร์ด FDD (Main)
1
2
อ 26 พฤษภาคม 2020 8:18 am โดย mindphp
VDO - SP Page builder
โดย numtan5839 ศ 22 พฤษภาคม 2020 6:27 pm บอร์ด SP Page Builder Thai Edition - Manual & VDO & เทคนิคการใช้งาน
1
7
ศ 22 พฤษภาคม 2020 7:00 pm โดย mindphp
วิธีการใช้ Google Tasks แอพจัดการบันทึกสิ่งที่ต้องทำ
โดย sirirat ศ 22 พฤษภาคม 2020 11:04 am บอร์ด Share Knowledge
0
60
ศ 22 พฤษภาคม 2020 11:04 am โดย sirirat
งานประจำวันที่ 22 พฤษภาคม 2563
โดย sirirat ศ 22 พฤษภาคม 2020 10:10 am บอร์ด M102 - ศิริรัตน์ ทิพย์น้อย
1
15
ศ 22 พฤษภาคม 2020 11:22 am โดย numtan5839
สรุปการเรียนรู้ประจำวัน 21/05/63
โดย sirirat ศ 22 พฤษภาคม 2020 10:08 am บอร์ด M102 - ศิริรัตน์ ทิพย์น้อย
0
3
ศ 22 พฤษภาคม 2020 10:08 am โดย sirirat
รายงานความคืบหน้า / Process
โดย mindphp ศ 22 พฤษภาคม 2020 1:07 am บอร์ด SP Page Builder Thai Edition (Main)
1
3
ศ 22 พฤษภาคม 2020 1:34 am โดย mindphp
ส่ง site map ให้ google แต่ไม่โชว์ในเมนูบนเว็บเรา จะมีผลอะไรกับเว็บไหมครับ
โดย toonytoony2004 พฤ 21 พฤษภาคม 2020 10:17 pm บอร์ด Joomla Development
6
91
ส 23 พฤษภาคม 2020 10:56 pm โดย toonytoony2004
B - เวลาของบอร์ดไม่ตรงเวลาไทย
โดย thatsawan พฤ 21 พฤษภาคม 2020 5:19 pm บอร์ด Odoojob.com - Tester
0
2
พฤ 21 พฤษภาคม 2020 5:19 pm โดย thatsawan
B - ข้อความแนะนำตัว ของผู้สมัครไม่แสดงใน บริษัทที่เปิดรับ
โดย thatsawan พฤ 21 พฤษภาคม 2020 5:18 pm บอร์ด Odoojob.com - Tester
0
2
พฤ 21 พฤษภาคม 2020 5:18 pm โดย thatsawan
R - [email Formart-หาคน] เเจ้งเมื่อมีคนสมัครงานใน Odoojob
โดย thatsawan พฤ 21 พฤษภาคม 2020 5:12 pm บอร์ด Odoojob.com - Manual & Content
0
1
พฤ 21 พฤษภาคม 2020 5:12 pm โดย thatsawan
B - บริษัทหาคน ต้องการเปลี่ยน Email รับสมัครงานหาทางเข้าไม่เจอ
โดย thatsawan พฤ 21 พฤษภาคม 2020 5:07 pm บอร์ด Odoojob.com - Tester
0
1
พฤ 21 พฤษภาคม 2020 5:07 pm โดย thatsawan
R - [email Formart-หางาน] หลังสมัครงาน บน Odoojob
โดย thatsawan พฤ 21 พฤษภาคม 2020 4:57 pm บอร์ด Odoojob.com - Manual & Content
0
5
พฤ 21 พฤษภาคม 2020 4:57 pm โดย thatsawan