ให้เรตสมาชิก: 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 คือเมื่อเกิดการชนกันของฟังก์ชัน จะทำการหาช่องในตารางแฮชใหม่โดยกระโดดไปจากเดิมเป็นฟังชันหนึ่ง หรือจนกว่าจะหาช่องว่างเจอเเละใส่ค่าลงไป 

 

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

กระทู้ล่าสุดจากเว็บบอร์ด
หัวข้อกระทู้
ตอบ
เปิดดู
ล่าสุด
ติดตั้ง module flaskwebgui ไม่ได้ครับ
โดย benzas00123 พ 29 ม.ค. 2020 6:53 pm บอร์ด Programming - C/C++ & java & Python
2
66
พฤ 30 ม.ค. 2020 11:52 am โดย jirawoot
ความรู้พื้นฐานเกี่ยวกับบัญชีแยกประเภท
โดย nutchasn พ 29 ม.ค. 2020 6:32 pm บอร์ด Accounting software & ERP โปรแกรมบัญชี ระบบอีอาร์พี
0
38
พ 29 ม.ค. 2020 6:32 pm โดย nutchasn
Pillow library ฟังก์ชั่น Image.new() ฟังก์ชั่นที่ใช้สำหรับการสร้างไฟล์รูปภาพ
โดย benzas00123 พ 29 ม.ค. 2020 6:21 pm บอร์ด Python Knowledge
0
32
พ 29 ม.ค. 2020 6:21 pm โดย benzas00123
ความรู้พื้นฐานเกี่ยวกับงบทดลอง (Taial Balance)
โดย nutchasn พ 29 ม.ค. 2020 6:00 pm บอร์ด Accounting software & ERP โปรแกรมบัญชี ระบบอีอาร์พี
0
36
พ 29 ม.ค. 2020 6:00 pm โดย nutchasn
Pillow library ฟังก์ชั่น ImageDraw() ฟังก์ชั่นสำหรับการเพิ่มตัวอักษรเข้าไปในภาพ
โดย benzas00123 พ 29 ม.ค. 2020 5:52 pm บอร์ด Python Knowledge
0
44
พ 29 ม.ค. 2020 5:52 pm โดย benzas00123
การปรับปรุงค่าใช้จ่ายจ่ายล่วงหน้า (Prepaid expenses)
โดย nutchasn พ 29 ม.ค. 2020 5:29 pm บอร์ด Accounting software & ERP โปรแกรมบัญชี ระบบอีอาร์พี
0
34
พ 29 ม.ค. 2020 5:29 pm โดย nutchasn
วิธีการเขียน php สำหรับตรวจสอบหมายเลขบัตรประชาชนว่ามีความถูกต้องหรือไม่
โดย Ittichai_chupol พ 29 ม.ค. 2020 5:24 pm บอร์ด PHP Knowledge
0
61
พ 29 ม.ค. 2020 5:24 pm โดย Ittichai_chupol
ทำความรู้จักกับชนิดข้อมูลใน SQL
โดย nutchasn พ 29 ม.ค. 2020 4:38 pm บอร์ด Accounting software & ERP โปรแกรมบัญชี ระบบอีอาร์พี
0
44
พ 29 ม.ค. 2020 4:38 pm โดย nutchasn
วิธีการปรับปรุงรายได้รับล่วงหน้า (Deferred Income)
โดย nutchasn พ 29 ม.ค. 2020 3:38 pm บอร์ด Accounting software & ERP โปรแกรมบัญชี ระบบอีอาร์พี
0
38
พ 29 ม.ค. 2020 3:38 pm โดย nutchasn
ผมไม่สามารถใช้ module tkinter ได้ครับ
โดย benzas00123 พ 29 ม.ค. 2020 2:04 pm บอร์ด Programming - C/C++ & java & Python
10
131
พฤ 30 ม.ค. 2020 10:15 am โดย benzas00123
การปรับปรุงรายได้ค้างรับ (Accrued Revenue)
โดย nutchasn พ 29 ม.ค. 2020 2:09 pm บอร์ด Accounting software & ERP โปรแกรมบัญชี ระบบอีอาร์พี
0
39
พ 29 ม.ค. 2020 2:09 pm โดย nutchasn
ปิด textbox เพื่อให้ไม่สามารถแก้ไขข้อมูลได้ด้วย radio button
โดย benzas00123 พ 29 ม.ค. 2020 11:31 am บอร์ด HTML CSS
0
49
พ 29 ม.ค. 2020 11:31 am โดย benzas00123
อยากทราบวิธีการ insert ข้อมูลในตอนติดตั้ง Extension ของ phpbb
โดย Ittichai_chupol พ 29 ม.ค. 2020 11:03 am บอร์ด Programming - PHP
1
69
พ 29 ม.ค. 2020 11:08 am โดย thatsawan
เจอของจริง
โดย noppadonsk พ 29 ม.ค. 2020 10:58 am บอร์ด พูดคุยเรื่องทั่วไป จับฉ่าย
0
56
พ 29 ม.ค. 2020 10:58 am โดย noppadonsk
อยากทราบวิธีแยกข้อมูลที่เรียงกันอย่างไม่เป็นระเบียบเข้า DB
โดย meetingyou999 อ 28 ม.ค. 2020 10:37 pm บอร์ด Programming - PHP
0
79
อ 28 ม.ค. 2020 10:37 pm โดย meetingyou999
Pillow library ฟังก์ชั่น Filters สำหรับการปรับ Filters ของภาพให้มีลูกเล่นมากขึ้น
โดย benzas00123 อ 28 ม.ค. 2020 6:52 pm บอร์ด Python Knowledge
0
60
อ 28 ม.ค. 2020 6:52 pm โดย benzas00123
เรียนรู้การใช้สูตรจาก Excel เพื่อง่ายต่อการคำนวณ
โดย nutchasn อ 28 ม.ค. 2020 6:51 pm บอร์ด Accounting software & ERP โปรแกรมบัญชี ระบบอีอาร์พี
0
73
อ 28 ม.ค. 2020 6:51 pm โดย nutchasn
Pillow library ฟังก์ชั่น convert ฟังก์ชั่นสำหรับเปลี่ยนโหมดสีของภาพ
โดย benzas00123 อ 28 ม.ค. 2020 6:40 pm บอร์ด Python Knowledge
0
57
อ 28 ม.ค. 2020 6:40 pm โดย benzas00123
ทำความรู้จักโปรแกรม power bi เพื่อใช้ในการวิเคราะห์ข้อมูล
โดย nutchasn อ 28 ม.ค. 2020 4:30 pm บอร์ด Accounting software & ERP โปรแกรมบัญชี ระบบอีอาร์พี
0
50
อ 28 ม.ค. 2020 4:30 pm โดย nutchasn
ทำความรู้เกี่ยวประเภทของสมุดรายวันขั้นต้น เพื่อใช้จดรายการค่าที่เกิดขึ้น
โดย nutchasn อ 28 ม.ค. 2020 3:33 pm บอร์ด Accounting software & ERP โปรแกรมบัญชี ระบบอีอาร์พี
0
37
อ 28 ม.ค. 2020 3:33 pm โดย nutchasn