การแฮชเป็นวิธีการที่เราสามารถแมปองค์ประกอบข้อมูลความยาวใดๆ กับคีย์ขนาดคงที่ได้ การแฮชทำงานเป็นคู่คีย์-ค่า
ฟังก์ชันการแฮชคือฟังก์ชันที่ทำแผนที่ในแมปแฮช องค์ประกอบข้อมูลที่กำหนดให้เป็นอินพุตในฟังก์ชันแฮชอาจได้รับคีย์แฮชเดียวกัน ในกรณีนี้องค์ประกอบอาจทับซ้อนกัน เพื่อหลีกเลี่ยงไม่ให้องค์ประกอบที่มีแฮชคีย์เหมือนกัน จึงมีการแนะนำแนวคิดของการโยง
การสร้างแฮชแมป
ในการสร้าง hashmap เราจำเป็นต้องมีฟังก์ชัน hashing ที่จะกำหนดค่าดัชนีขององค์ประกอบข้อมูล
เรามีตารางแฮชพร้อมถัง n อัน การแทรกโหนดลงใน ตารางแฮช เราได้รับฟังก์ชันแฮชเป็น
hashIndex =คีย์ % noOfBuckets
ตอนนี้ เราจะใช้ฟังก์ชันแฮชนี้และคำนวณดัชนีแฮชของทุกค่าที่แทรกลงใน แฮชแมป .
-
แทรกองค์ประกอบและคำนวณ hashIndex ของค่าคีย์ที่กำหนด จากนั้นแทรกโหนดใหม่ต่อท้ายรายการ
-
ในการลบโหนด เราจะคำนวณดัชนีแฮช และในบัคเก็ตที่สอดคล้องกับดัชนีแฮช เราจะค้นหาองค์ประกอบในบัคเก็ตแล้วลบออก
ตัวอย่าง
#include<iostream>
#include <list>
using namespace std;
class Hash{
int BUCKET;
list < int >*table;
public:
Hash (int V);
void insertItem (int x);
void deleteItem (int key);
int hashFunction (int x){
return (x % BUCKET);
}
void displayHash ();
};
Hash::Hash (int b){
this->BUCKET = b;
table = new list < int >[BUCKET];
}
void Hash::insertItem (int key){
int index = hashFunction (key);
table[index].push_back (key);
}
void Hash::deleteItem (int key){
int index = hashFunction (key);
list < int >::iterator i;
for (i = table[index].begin (); i != table[index].end (); i++){
if (*i == key)
break;
}
if (i != table[index].end ())
table[index].erase (i);
}
void Hash::displayHash (){
for (int i = 0; i < BUCKET; i++){
cout << i;
for (auto x:table[i])
cout << " --> " << x;
cout << endl;
}
}
int main (){
int a[] = { 5, 12, 67, 9, 16 };
int n = 5;
Hash h (7);
for (int i = 0; i < n; i++)
h.insertItem (a[i]);
h.deleteItem (12);
h.displayHash ();
return 0;
} ผลลัพธ์
0 1 2 --> 9 --> 16 3 4 --> 67 5 --> 5 6
