การจัดการข้อมูลเป็นหัวใจหลักของการพัฒนาโปรแกรม และเทคนิคต่างๆ มักถูกออกแบบมาเพื่อจัดการกับข้อมูลในลักษณะต่างๆ โดยเทคนิคหนึ่งที่ทั้งน่าสนใจและท้าทายคือการใช้ 'Linear Probing Hashing' ในภาษา C เพื่อจัดการข้อมูลแบบไดนามิค วันนี้เราจะพาไปรู้จักกับ Linear Probing พร้อมทั้งโค้ดตัวอย่าง และวิเคราะห์ข้อดีข้อเสียของมัน
Linear Probing เป็นวิธีการแก้ปัญหาการชน (collision) ของข้อมูลที่ถูกแฮชเข้าไปในตารางแฮช (hash table) ซึ่งเมื่อมีการชนของข้อมูล (หลายๆ ข้อมูลมีค่าแฮชเดียวกัน) เทคนิคนี้จะค้นหาค่า index ถัดไปในตารางแฮชโดยเรียงต่อเนื่อง จนกระทั่งพบช่องว่างที่สามารถเก็บข้อมูลได้
Insert (การแทรกข้อมูล)
เมื่อต้องการเพิ่มข้อมูลใหม่ เราจะคำนวณ index ผ่านฟังก์ชันแฮช หากช่องนั้นว่าง เราจะแทรกข้อมูลเข้าไปได้ทันที แต่หากมีข้อมูลอยู่แล้ว เราจะเลื่อนไปยังช่องถัดไปจนกว่าจะพบช่องว่าง
Find (การค้นหาข้อมูล)
การค้นหาโดยใช้แฮชเทเบิลมีประสิทธิภาพสูง ต้องคำนวณแฮชแล้วไปยัง index ที่เก็บข้อมูล หากไม่พบให้เลื่อนไปเรื่อยๆ จนกว่าจะพบหรือจนถึงจุดที่เริ่มค้นหา
Delete (การลบข้อมูล)
การลบข้อมูลใน linear probing สามารถทำได้โดยการค้นหาข้อมูลก่อนแล้วทำเครื่องหมายที่ช่องนั้นว่า "ลบแล้ว" หรือ "ตำแหน่งนี้ว่าง"เพื่อให้การเพิ่มหรือการค้นหาถัดไปสามารถใช้งานได้เหมือนช่องว่าง
#include
#include
#define TABLE_SIZE 10
typedef struct {
int key;
int data;
} HashTableItem;
HashTableItem* hashTable[TABLE_SIZE];
// Hash function
int hashFunction(int key) {
return key % TABLE_SIZE;
}
// Insert operation
void insert(int key, int data) {
int index = hashFunction(key);
int startIndex = index;
// Create a new hash table item
HashTableItem* newItem = (HashTableItem*)malloc(sizeof(HashTableItem));
newItem->data = data;
newItem->key = key;
// Probe to find the empty slot or the end of the table
while (hashTable[index] != NULL && hashTable[index]->key != key) {
index = (index + 1) % TABLE_SIZE;
if (index == startIndex) return; // Table is full
}
hashTable[index] = newItem;
}
// Find operation
int find(int key) {
int index = hashFunction(key);
int startIndex = index;
// Find the item with the key
while (hashTable[index] != NULL) {
if (hashTable[index]->key == key)
return hashTable[index]->data;
index = (index + 1) % TABLE_SIZE;
if (index == startIndex) return -1; // Key not found
}
return -1; // Key not found
}
// Delete operation
void delete(int key) {
int index = hashFunction(key);
int startIndex = index;
// Find the item to delete
while (hashTable[index] != NULL) {
if (hashTable[index]->key == key) {
HashTableItem* temp = hashTable[index];
hashTable[index] = NULL; // Mark as deleted
free(temp); // Free memory
return;
}
index = (index + 1) % TABLE_SIZE;
if (index == startIndex) return; // Item not found
}
}
int main() {
insert(1, 20);
insert(2, 70);
insert(42, 80);
printf("Element at key 1: %d\n", find(1));
delete(1);
int element = find(1);
if (element == -1) {
printf("Element not found\n");
}
return 0;
}
การทำความเข้าใจเทคนิคต่างๆ ในการจัดการข้อมูลเป็นสิ่งสำคัญสำหรับนักพัฒนาซอฟต์แวร์ สถาบัน EPT เข้าใจถึงความจำเป็นนี้และพร้อมที่จะนำเสนอคอร์สเรียนที่จะช่วยให้คุณได้รู้จักกับเทคนิคโปรแกรมมิ่งที่แตกต่างไปจากปกติ ถ้าหากคุณมีความสนใจในการเรียนรู้เพิ่มเติมเกี่ยวกับวิธีการเหล่านี้หรืออยากพัฒนาทักษะการเขียนโค้ดของคุณ EPT พร้อมที่จะเป็นผู้ช่วย และนำทางคุณไปสู่การเป็นนักพัฒนาที่เชี่ยวชาญและมั่นใจในฝีมือของตัวเอง จงอย่ารอช้า ร่วมสัมผัสการเรียนรู้ที่น่าตื่นเต้นกับเราให้เร็วที่สุด!
หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง
หากมีข้อผิดพลาด/ต้องการพูดคุยเพิ่มเติมเกี่ยวกับบทความนี้ กรุณาแจ้งที่ http://m.me/Expert.Programming.Tutor
085-350-7540 (DTAC)
084-88-00-255 (AIS)
026-111-618
หรือทาง EMAIL: NTPRINTF@GMAIL.COM