ดาวไม่ได้ใช้งานดาวไม่ได้ใช้งานดาวไม่ได้ใช้งานดาวไม่ได้ใช้งานดาวไม่ได้ใช้งาน
 

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

 

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

กระทู้ล่าสุดจากเว็บบอร์ด
หัวข้อกระทู้
ตอบ
เปิดดู
ล่าสุด
ทำความรู้จัก Cloud
โดย aninthana ศ 20 ก.ย. 2019 6:36 pm บอร์ด Web Hosting Review - Free Host Share Host VPS
0
5
ศ 20 ก.ย. 2019 6:36 pm โดย aninthana
เปรียบเทียบ smart watch รุ่นต่างๆ จากหลายๆค่าย รุ่นไหนโดน รุ่นไหนดี มารับชมกันได้เลย
โดย chatee supasand ศ 20 ก.ย. 2019 5:41 pm บอร์ด พูดคุยเรื่องทั่วไป จับฉ่าย
0
10
ศ 20 ก.ย. 2019 5:41 pm โดย chatee supasand
วิธีสมัครและใช้งาน api อัตราแลกเปลี่ยนเงินตรา จาก ธนาคารแห่งประเทศไทย ด้วย php
โดย birdkritsna ศ 20 ก.ย. 2019 4:14 pm บอร์ด Programming - PHP
0
10
ศ 20 ก.ย. 2019 4:14 pm โดย birdkritsna
จะทำ path way เป็นลูกศรชีต้องทำยังไงครับ
โดย jamepiyawat ศ 20 ก.ย. 2019 3:50 pm บอร์ด HTML CSS
0
9
ศ 20 ก.ย. 2019 3:50 pm โดย jamepiyawat
อยากทราบวิธีที่จะทำให้เมือเรากดปุ่มซื้อสินค้าแล้วจะมีหน้า pop เด้งขึ้นมาครับ
โดย jamepiyawat ศ 20 ก.ย. 2019 3:30 pm บอร์ด HTML CSS
0
4
ศ 20 ก.ย. 2019 3:30 pm โดย jamepiyawat
อยากทราบวิธีทำปุ่มกดสลับค่าระหว่าง list box ครับ
โดย birdkritsna ศ 20 ก.ย. 2019 2:59 pm บอร์ด Programming - PHP
4
27
ศ 20 ก.ย. 2019 4:10 pm โดย mindphp
ระดับ User นี้มีข้อจำกัดอะไรบ้างครับ
โดย Patipat ศ 20 ก.ย. 2019 2:45 pm บอร์ด ปัญหาการใช้ phpBB3, SMF, Joomla, Wordpress, CMS CRM
1
14
ศ 20 ก.ย. 2019 2:50 pm โดย tsukasaz
ทำไมโค้ดของผมแสดงผลชื่อจังหวัดชื่ออำเภอผิดครับ
โดย jamepiyawat ศ 20 ก.ย. 2019 2:20 pm บอร์ด JavaScript & Jquery Ajax
8
24
ศ 20 ก.ย. 2019 3:22 pm โดย jamepiyawat
งานประจำวันที่ 20 กันยายน 2562
โดย birdkritsna ศ 20 ก.ย. 2019 9:22 am บอร์ด M094 - กฤษณะ จะโรจน์รัมย์
2
12
ศ 20 ก.ย. 2019 6:32 pm โดย birdkritsna
VDO ทดลองการเข้าใช้งาน การเข้าใช้งาน ในการสร้าง เว็บไซต์ พร้อม โดเมน
โดย aninthana ศ 20 ก.ย. 2019 10:27 am บอร์ด M092 - อนินธนา บุญยัง
2
9
ศ 20 ก.ย. 2019 11:57 am โดย aninthana
VDO สอนการทำให้เว็บเข้าใช้งานด้วย https บน DA
โดย aninthana ศ 20 ก.ย. 2019 10:16 am บอร์ด M092 - อนินธนา บุญยัง
1
9
ศ 20 ก.ย. 2019 11:32 am โดย thatsawan
งานประจำวันที่ 20 กันยายน 2562
โดย chatee supasand ศ 20 ก.ย. 2019 9:53 am บอร์ด MT33 - นายชาตรี สุภาแสน
2
13
ศ 20 ก.ย. 2019 7:32 pm โดย chatee supasand
งานประจำวันที่ 20 กันยายน 2562
โดย aninthana ศ 20 ก.ย. 2019 9:45 am บอร์ด M092 - อนินธนา บุญยัง
0
4
ศ 20 ก.ย. 2019 9:45 am โดย aninthana
งานประจำวันที่ 20 กันยายน 2562
โดย aninthana ศ 20 ก.ย. 2019 9:43 am บอร์ด M092 - อนินธนา บุญยัง
5
35
ศ 20 ก.ย. 2019 6:49 pm โดย aninthana
งานประจำวันที่ 20 กันยายน 2562
โดย Patipat ศ 20 ก.ย. 2019 9:38 am บอร์ด M088 - ปฏิภัทร สารธรรม
1
4
ศ 20 ก.ย. 2019 6:49 pm โดย Patipat
งานประจำวันที่ 20 กันยายน 2562
โดย jamepiyawat ศ 20 ก.ย. 2019 9:10 am บอร์ด M084 - นายปิยวัช เชาว์วิมล
2
8
ศ 20 ก.ย. 2019 6:57 pm โดย jamepiyawat
งานประจำวันที่ 20 กันยายน 2562
โดย jirawoot ศ 20 ก.ย. 2019 9:06 am บอร์ด M090 - นายจิระวุฒิ อัครลิขิตกุล
1
3
ศ 20 ก.ย. 2019 7:09 pm โดย jirawoot
ทำความรู้จักกับ Google Lighthouse ตรวจสอบคุณภาพเว็บไซต์
โดย birdkritsna พฤ 19 ก.ย. 2019 6:37 pm บอร์ด พูดคุยเรื่องทั่วไป จับฉ่าย
0
16
พฤ 19 ก.ย. 2019 6:37 pm โดย birdkritsna
ส่วนประกอบของเว็บไซต์ มีอะไรบ้าง
โดย aninthana พฤ 19 ก.ย. 2019 6:12 pm บอร์ด Web Hosting Review - Free Host Share Host VPS
0
11
พฤ 19 ก.ย. 2019 6:12 pm โดย aninthana
วิธีทำภาพให้มีขอบโค้งมนด้วยโปรแกรม คล้าย photoshop ออนไลน์ freephototool.com
โดย jamepiyawat พฤ 19 ก.ย. 2019 5:51 pm บอร์ด Graphic design
1
17
พฤ 19 ก.ย. 2019 11:15 pm โดย pipoipi