การจัดการข้อมูลเป็นหนึ่งในส่วนสำคัญของการศึกษาวิทยาการคอมพิวเตอร์และการเขียนโปรแกรม โดยเฉพาะอย่างยิ่งเมื่อข้อมูลมีจำนวนมากและต้องการการค้นหาที่รวดเร็ว การใช้เทคนีค hashing คือคำตอบสำหรับความท้าทายนี้ โดยในภาษา C++ เทคนิคหนึ่งที่น่าสนใจคือ Quadratic Probing Hashing ที่ช่วยแก้ปัญหาการชน (collision) ของข้อมูลที่ถูก hash ไปใส่ในตำแหน่งเดียวกัน
การทำงานของ Quadratic Probing คือ เมื่อพบการชน โปรแกรมจะค้นหาตำแหน่งใหม่ผ่านสมการแบบ Quadratic โดยเพิ่ม Quadratic sequence (1^2, 2^2, 3^2,...) กับ index ที่พบการชน สิ่งนี้ช่วยกระจายตำแหน่งที่มีการชนออกไปโดยไม่เกิดการชนซ้ำที่ตำแหน่งเดิม เพิ่มประสิทธิภาพในการค้นหาในภายหลัง
ต่อไปนี้คือตัวอย่างโค้ดสำหรับการ insert, find, และ delete ใน C++ โดยใช้ Quadratic Probing Hashing:
#include
#include
#define TABLE_SIZE 10
#define PRIME 7
class HashTable {
private:
std::vector table;
int total_elements;
public:
// Constructor
HashTable() : table(TABLE_SIZE, -1), total_elements(0) {}
// Hash function
int hashFunction(int key) {
return key % TABLE_SIZE;
}
// Function to insert a key
void insert(int key) {
if (total_elements >= TABLE_SIZE) {
std::cout << "Hash table is full" << std::endl;
return;
}
int index = hashFunction(key);
int h = 1;
while (table[index] != -1) {
index = (index + h * h) % TABLE_SIZE;
h++;
}
table[index] = key;
total_elements++;
}
// Function to find a key
bool find(int key) {
int index = hashFunction(key);
int h = 1;
while (table[index] != -1) {
if (table[index] == key) {
return true;
}
index = (index + h * h) % TABLE_SIZE;
h++;
}
return false;
}
// Function to delete a key
void deleteKey(int key) {
int index = hashFunction(key);
int h = 1;
while (table[index] != -1) {
if (table[index] == key) {
table[index] = -2; // Deleted key is marked with a special value
total_elements--;
return;
}
index = (index + h * h) % TABLE_SIZE;
h++;
}
std::cout << "Key not found" << std::endl;
}
// Function to display the hash table
void displayTable() {
for (int i = 0; i < TABLE_SIZE; i++) {
if (table[i] != -1 && table[i] != -2) {
std::cout << i << " --> " << table[i] << std::endl;
} else {
std::cout << i << std::endl;
}
}
}
};
int main() {
HashTable hashTable;
// Insert data
hashTable.insert(12);
hashTable.insert(25);
hashTable.insert(35);
hashTable.insert(26);
// Display table
hashTable.displayTable();
// Find key
std::cout << "Key 25 Found: " << hashTable.find(25) << std::endl;
// Delete key
hashTable.deleteKey(25);
std::cout << "After deleting key 25" << std::endl;
hashTable.displayTable();
}
ข้อดีของการใช้ Quadratic Probing Hashing คือ ช่วยลดการชนของตำแหน่งที่คล้ายกัน ซึ่งเป็นปัญหาที่เกิดร่วมกับ Linear Probing Hashing ที่มีการแก้ปัญหาด้วยการเพิ่ม Linear sequence (1, 2, 3, ...) กับ index ที่ชน อย่างไรก็ตามข้อเสียคือ อาจมีการเกิด secondary clustering หมายถึงตำแหน่งที่มีการชนกันมากเกินไปและมีการเติมช่องว่างด้วยค่าที่อยู่ใกล้กันโดยที่อาจมีการวนซ้ำ (cycle) ภายในตาราง hashing
การศึกษาการเขียนโปรแกรมเป็นทักษะสำคัญที่จะช่วยให้คุณจัดการกับข้อมูลได้อย่างเชี่ยวชาญ การเรียนรู้เทคนิคเช่น Quadratic Probing Hashing และการใช้ภาษา C++ นั้นสามารถทำให้คุณก้าวหน้าในอาชีพการเป็นโปรแกรมเมอร์ได้ หากคุณมีความสนใจในการพัฒนาทักษะการเขียนโปรแกรมของคุณ การเรียนที่ EPT โรงเรียนสอนโปรแกรมมิ่งที่คุณไว้วางใจได้ จะช่วยให้คุณไปถึงเป้าหมายทางวิชาการและอาชีพของคุณได้อย่างแน่นอน!
หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง
หากมีข้อผิดพลาด/ต้องการพูดคุยเพิ่มเติมเกี่ยวกับบทความนี้ กรุณาแจ้งที่ http://m.me/Expert.Programming.Tutor
085-350-7540 (DTAC)
084-88-00-255 (AIS)
026-111-618
หรือทาง EMAIL: NTPRINTF@GMAIL.COM