การจัดการข้อมูลเป็นหนึ่งในงานที่สำคัญในด้านการเขียนโปรแกรม ไม่ว่าจะเป็นการเก็บข้อมูล, ค้นหา, เพิ่ม หรือลบข้อมูล ซึ่งการใช้โครงสร้างข้อมูลที่เหมาะสมสามารถช่วยให้ระบบทำงานได้รวดเร็วและมีประสิทธิภาพมากขึ้น ในบทความนี้ เราจะมาพูดถึงการใช้เทคนิค Quadratic Probing ซึ่งเป็นวิธีหนึ่งในการจัดการการชนใน Hash Table เมื่อเราใช้ภาษา C ซึ่งเป็นภาษาโปรแกรมระดับต่ำที่ให้การควบคุมที่เข้มงวดและประสิทธิภาพที่สูง
Quadratic Probing เป็นวิธีการแก้ปัญหาการชน (collision resolution) ใน Hash Table โดยใช้สมการเชิงกำลังสองเพื่อค้นหาที่ว่างในกรณีที่สล็อตที่ประมวลผลจากฟังก์ชันแฮชเต็มไปแล้ว สมการที่ใช้มักจะในรูปแบบของ H(x) = (H(x) + F(i)) % table_size, โดยที่ F(i) = i^2 (i คือ ค่าที่เพิ่มขึ้นเรื่อยๆ เพื่อหาช่องว่างถัดไป)
ต่อไปนี้เป็นตัวอย่างโค้ดฟังก์ชันต่างๆ ของ Quadratic Probing Hash Table ในภาษา C:
Structure ของ Hash Item และ Hash Table
#include
#include
#define TABLE_SIZE 10
typedef struct {
int key;
int data;
} HashItem;
typedef struct {
HashItem* items[TABLE_SIZE];
} HashTable;
HashTable* createHashTable() {
HashTable* table = (HashTable*)malloc(sizeof(HashTable));
for (int i = 0; i < TABLE_SIZE; ++i)
table->items[i] = NULL;
return table;
}
// เพิ่มฟังก์ชันแฮชที่นี่
ฟังก์ชันการใส่ข้อมูล (Insert)
unsigned int hash(int key) {
return key % TABLE_SIZE;
}
void insert(HashTable* table, int key, int data) {
HashItem* newItem = (HashItem*)malloc(sizeof(HashItem));
newItem->key = key;
newItem->data = data;
// Quadratic probing
int index = hash(key);
int i = 0;
while (table->items[index] != NULL && i < TABLE_SIZE) {
index = hash(index + i * i);
i++;
}
if (i < TABLE_SIZE)
table->items[index] = newItem;
}
ฟังก์ชันการค้นหา (Find)
HashItem* find(HashTable* table, int key) {
int index = hash(key);
int i = 0;
while (table->items[index] != NULL && i < TABLE_SIZE) {
if (table->items[index]->key == key)
return table->items[index];
index = hash(index + i * i);
i++;
}
return NULL; // ไม่พบข้อมูล
}
ฟังก์ชันการลบข้อมูล (Delete)
void delete(HashTable* table, int key) {
int index = hash(key);
int i = 0;
while (table->items[index] != NULL && i < TABLE_SIZE) {
if (table->items[index]->key == key) {
free(table->items[index]);
table->items[index] = NULL;
return;
}
index = hash(index + i * i);
i++;
}
}
การจัดการข้อมูลแบบไดนามิคด้วย Quadratic Probing Hashing เป็นเทคนิคที่ท้าทายและเต็มไปด้วยศักยภาพในการพัฒนาระบบที่มีประสิทธิภาพ ที่ Expert-Programming-Tutor (EPT), เรามุ่งมั่นให้นักเรียนเรียนรู้เทคนิคการเขียนโค้ดอย่างมีประสิทธิภาพ และการใช้เทคนิคขั้นสูงอย่าง Quadratic Probing สามารถส่งเสริมการศึกษาของคุณได้อย่างไม่น่าเชื่อ คุณไม่เพียงจะเรียนรู้วิธีการแก้ไขปัญหาโปรแกรมเมอร์อย่างสร้างสรรค์เท่านั้น แต่คุณยังจะได้พัฒนาทักษะการคิดและการวิเคราะห์ของคุณไปพร้อมๆ กัน หากคุณสนใจในการเป็นโปรแกรมเมอร์ที่มีทักษะและความรู้ที่ครอบคลุมเราขอเชิญชวนคุณเข้าร่วมหลักสูตรของเรา ณ EPT วันนี้!
หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง
หากมีข้อผิดพลาด/ต้องการพูดคุยเพิ่มเติมเกี่ยวกับบทความนี้ กรุณาแจ้งที่ http://m.me/Expert.Programming.Tutor
085-350-7540 (DTAC)
084-88-00-255 (AIS)
026-111-618
หรือทาง EMAIL: NTPRINTF@GMAIL.COM