การใช้ตารางแฮชของตัวเองด้วย Open Addressing Linear Probing ใน C++

ตารางแฮชเป็นโครงสร้างข้อมูลที่ใช้เก็บคู่คีย์-ค่า ฟังก์ชันแฮชถูกใช้โดยตารางแฮชเพื่อคำนวณดัชนีลงในอาร์เรย์ที่จะแทรกหรือค้นหาองค์ประกอบ

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

นี่คือโปรแกรม C++ เพื่อใช้งานตารางแฮชด้วยโพรบเชิงเส้น

อัลกอริทึม

เริ่มต้น ประกาศฟังก์ชัน แทรก (int k, int v) ประกาศ hash_val, init, delindex ไปยังตัวชี้จำนวนเต็ม เริ่มต้น hash_val =HashFunc(k) intialize init =-1 intialize delindex =-1 while (hash_val !=init and (ht[hash_val] ==DelNode::getNode() or ht[hash_val] !=NULL and ht[hash_val] ->k !=k)) if (init ==-1) init =hash_val if (ht[hash_val] ==DelNode::getNode()) delindex =hash_val hash_val =HashFunc(hash_val + 1) if (ht[hash_val ] ==NULL หรือ hash_val ==init) if(delindex !=-1) ht[delindex] =new HashTable(k, v) อื่น ht[hash_val] =ใหม่ HashTable(k, v) if(init !=hash_val) if (ht[hash_val] !=DelNode::getNode()) if (ht[hash_val] !=NULL) if (ht[hash_val]->k==k) ht[hash_val]->v =v อื่น ht[ hash_val] =HashTable ใหม่ (k, v) สิ้นสุด

สำหรับการค้นหาค่าคีย์:

เริ่มประกาศฟังก์ชัน SearchKey(int k) ประกาศ hash_val เริ่มต้นของประเภทข้อมูลจำนวนเต็ม เริ่มต้น hash_val =HashFunc(k) intialize init =-1 ในขณะที่ (hash_val !=init และ (ht[hash_val] ==DelNode::getNode() หรือ ht[hash_val] !=NULL และ ht[hash_val]->k!=k if (init ==-1) init =hash_val hash_val =HashFunc(hash_val + 1) if (ht[hash_val] ==NULL or hash_val ==init) return -1 else return ht[hash_val]->vEnd. 

 สำหรับการลบ: 
 
Begin Declare Function Remove(int k) ประกาศ hash_val เริ่มต้นของประเภทข้อมูลจำนวนเต็ม เริ่มต้น hash_val =HashFunc(k) เริ่มต้น init =-1 ในขณะที่ (hash_val !=init และ (ht[hash_val] ==DelNode::getNode() หรือ ht[hash_val] !=NULL และ ht[hash_val]->k!=k)) if (init ==-1) init =hash_val hash_val =HashFunc(hash_val + 1) if (hash_val !=init และ ht[hash_val] !=NULL) ลบ ht[hash_val] ht[hash_val] =DelNode::getNode()สิ้นสุด
 
โค้ดตัวอย่าง
 
#include #include #include using namespace std;const int T_S =5;class HashTable { สาธารณะ:int k; int วี; HashTable (int k, int v) { this->k =k; this->v =v; }};คลาส DelNode:สาธารณะ HashTable { ส่วนตัว:DelNode แบบคงที่ * en; DelNode ():HashTable (-1, -1) {} สาธารณะ:คงที่ DelNode *getNode () { if (en ==NULL) en =ใหม่ DelNode (); กลับ en; }};DelNode *DelNode::en =NULL;คลาส HashMapTable { ส่วนตัว:HashTable ** ht; สาธารณะ:HashMapTable () { ht =ใหม่ HashTable * [T_S]; สำหรับ (int i =0; i k !=k)) { if (init ==-1 ) init =hash_val; ถ้า (ht[hash_val] ==DelNode::getNode()) delindex =hash_val; hash_val =HashFunc (hash_val + 1); } if (ht[hash_val] ==NULL || hash_val ==init) { if(delindex !=-1) ht[delindex] =new HashTable(k, v); อื่น ht[hash_val] =ใหม่ HashTable(k, v); } if(init !=hash_val) { if (ht[hash_val] !=DelNode::getNode()) { if (ht[hash_val] !=NULL) { if (ht[hash_val]->k==k) ht [hash_val]->v =v; } } อื่น ht[hash_val] =ใหม่ HashTable(k, v); } } int SearchKey (int k) { int hash_val =HashFunc (k); int init =-1; ในขณะที่ (hash_val !=init &&(ht[hash_val] ==DelNode::getNode() || ht[hash_val] !=NULL &&ht[hash_val]->k!=k)) { if (init ==-1 ) init =hash_val; hash_val =HashFunc (hash_val + 1); } if (ht[hash_val] ==NULL || hash_val ==init) คืนค่า -1; อื่นส่งคืน ht[hash_val]->v; } โมฆะ ลบ (int k) { int hash_val =HashFunc (k); int init =-1; ในขณะที่ (hash_val !=init &&(ht[hash_val] ==DelNode::getNode() || ht[hash_val] !=NULL &&ht[hash_val]->k!=k)) { if (init ==-1 ) init =hash_val; hash_val =HashFunc (hash_val + 1); } if (hash_val !=init &&ht[hash_val] !=NULL) { ลบ ht[hash_val]; ht[hash_val] =DelNode::getNode(); } } ~HashMapTable() { ลบ[] ht; }};int main () { แฮช HashMapTable; int k, วี; int ค; while(1) { cout<<"1.Insert element ลงในตาราง"<>ค; สวิตช์ (c) { กรณีที่ 1:cout <<"ป้อนองค์ประกอบที่จะแทรก:"; ซิน>>วี; cout<<"Enter คีย์ที่องค์ประกอบที่จะแทรก:"; ซิน>>เค; แฮช.Insert(k, v); หยุดพัก; กรณีที่ 2:cout<<"ป้อนคีย์ขององค์ประกอบที่จะค้นหา:"; ซิน>>เค; if(hash.SearchKey(k) ==-1) { cout<<"ไม่พบองค์ประกอบที่คีย์ "<>เค; แฮช. ลบ (k); หยุดพัก; กรณีที่ 4:ทางออก(1); ค่าเริ่มต้น:cout<<"\nป้อนตัวเลือกที่ถูกต้อง\n"; } } คืนค่า 0;}
 
ผลลัพธ์
 
1.Insert element ใน table2.Search element จาก key3.Delete element at a key4.ExitEnter your choice:1Enter element to be insert:10Enter key at which element to be insert:21.Insert element ลงใน table2. ค้นหาองค์ประกอบจากคีย์3.ลบองค์ประกอบที่คีย์4.ออกป้อนตัวเลือกของคุณ:1ป้อนองค์ประกอบที่จะแทรก:7ป้อนคีย์ที่องค์ประกอบที่จะแทรก:61.แทรกองค์ประกอบลงในตาราง2.ค้นหาองค์ประกอบจากคีย์3.ลบองค์ประกอบที่คีย์4 .ExitEnter ตัวเลือกของคุณ:1Enter องค์ประกอบที่จะแทรก:4Enter คีย์ที่องค์ประกอบที่จะแทรก:51.Insert องค์ประกอบลงใน table2.Search องค์ประกอบจาก key3.Delete องค์ประกอบที่ key4.Exit ป้อนตัวเลือกของคุณ:1Enter องค์ประกอบที่จะแทรก:12ป้อนคีย์ที่องค์ประกอบที่จะแทรก:31.แทรกองค์ประกอบลงในตาราง2.ค้นหาองค์ประกอบจากคีย์3.ลบองค์ประกอบที่คีย์4.ออกป้อนตัวเลือกของคุณ:15ป้อนตัวเลือกที่ถูกต้อง1.แทรกองค์ประกอบลงในตาราง2.ค้นหาองค์ประกอบจากคีย์3.ลบ องค์ประกอบที่คีย์4.ออกป้อนตัวเลือกของคุณ:1Enter องค์ประกอบที่จะแทรก:15ป้อนคีย์ที่องค์ประกอบที่จะแทรก:81.แทรกองค์ประกอบลงในตาราง2.ค้นหาองค์ประกอบจากคีย์3.ลบองค์ประกอบที่คีย์4.ออก ป้อนตัวเลือกของคุณ:2ป้อนคีย์ขององค์ประกอบที่จะค้นหา:6องค์ประกอบที่คีย์ 6 :71.แทรกองค์ประกอบลงในตาราง2.ค้นหาองค์ประกอบจากคีย์3.ลบองค์ประกอบที่คีย์4.ออกป้อนตัวเลือกของคุณ:3ป้อนคีย์ขององค์ประกอบที่จะลบ:21.แทรกองค์ประกอบลงในตาราง2.ค้นหาองค์ประกอบจากคีย์3.ลบ องค์ประกอบที่คีย์4.ออกป้อนตัวเลือกของคุณ:2ป้อนคีย์ขององค์ประกอบที่จะค้นหา:2ไม่พบองค์ประกอบที่คีย์ 21.แทรกองค์ประกอบลงในตาราง2.ค้นหาองค์ประกอบจากคีย์3.ลบองค์ประกอบที่คีย์4.ออกป้อนตัวเลือกของคุณ:4