การจัดการข้อมูลเป็นงานสำคัญที่นักพัฒนาซอฟต์แวร์ต้องให้ความสนใจเป็นพิเศษ เพราะการที่โค้ดของเราสามารถจัดการกับข้อมูลได้เป็นอย่างดีนั้น จะช่วยเพิ่มประสิทธิภาพในการทำงานของซอฟต์แวร์ ในภาษา C# หนึ่งเทคนิคที่ได้รับความนิยมก็คือการใช้ Hashing เพื่อจัดการข้อมูลแบบไดนามิค วันนี้เราจะพูดถึง Seperate Chaining Hashing โดยเฉพาะ ซึ่งเป็นวิธีหนึ่งของ Collision resolution ในการจัดการ hash collisions.
Seperate Chaining Hashing เกิดขึ้นเมื่อมีการทำ hashing และข้อมูลหลายๆ ชิ้นที่มีคีย์ต่างกัน หลุดเข้าไปอยู่ในบัคเก็ต (bucket) เดียวกัน ซึ่งแทนที่จะทำการ overwrite ข้อมูลเก่า หรือใช้การ probing เพื่อหาบัคเก็ตว่าง Seperate Chaining ใช้ลิงก์ลิสต์ (Linked List) หรือโครงสร้างข้อมูลอื่นๆ เช่น AVL trees หรือ Red-Black trees เพื่อเก็บรายการข้อมูลที่มี hash value เหมือนกันนั้นเอง
ตอนนี้เรามาดูตัวอย่างของโค้ดในเทคนิค Seperate Chaining Hashing ในการ insert, insertAtFront, find, และ delete กัน:
// สร้างโครงสร้างข้อมูลของ Node
public class HashNode {
public K key;
public V value;
public HashNode next;
public HashNode(K key, V value) {
this.key = key;
this.value = value;
this.next = null;
}
}
// สร้างคลาสซึ่งใช้ Seperate Chaining Hashing
public class HashMap {
private List> bucketArray = new List>();
private int numBuckets; // จำนวน buckets.
private int size; // จำนวนโหนด keys.
public HashMap() {
numBuckets = 10;
size = 0;
// สร้าง empty chains
for (int i = 0; i < numBuckets; i++)
bucketArray.Add(null);
}
// เทคนิค hashing แบบง่าย
private int GetBucketIndex(K key) {
int hashCode = key.GetHashCode();
int index = hashCode % numBuckets;
return index;
}
// เพิ่มข้อมูล (insert)
public void Add(K key, V value) {
int bucketIndex = GetBucketIndex(key);
HashNode head = bucketArray[bucketIndex];
// ตรวจสอบว่า key นี้มีอยู่แล้วหรือไม่
while (head != null) {
if (head.key.Equals(key)) {
head.value = value;
return;
}
head = head.next;
}
size++;
head = bucketArray[bucketIndex];
HashNode newNode = new HashNode(key, value);
newNode.next = head;
bucketArray[bucketIndex] = newNode;
// โค้ดนี้มีส่วนของการ Rehash นิดหน่อยด้วยเมื่อ size เกิน threshold กำหนด
}
// ลบข้อมูล (delete)
public V Remove(K key) {
int bucketIndex = GetBucketIndex(key);
// เริ่มต้นที่ head ของลิงก์
HashNode head = bucketArray[bucketIndex];
HashNode prev = null;
while (head != null) {
if (head.key.Equals(key))
break;
prev = head;
head = head.next;
}
if (head == null) {
return default(V); // ไม่พบ
}
size--;
if (prev != null)
prev.next = head.next;
else
bucketArray[bucketIndex] = head.next;
return head.value;
}
// ตรวจหาข้อมูล (find)
public V Get(K key) {
int bucketIndex = GetBucketIndex(key);
HashNode head = bucketArray[bucketIndex];
// ค้นหา key ใน chain
while (head != null) {
if (head.key.Equals(key))
return head.value;
head = head.next;
}
// หากไม่พบ
return default(V);
}
}
จากโค้ดด้านบน คุณจะเห็นว่าเราพยายามจัดการกับ collisions โดยใช้ลิงก์ลิสต์ในแต่ละ bucket. ข้อดีของ Seperate Chaining Hashing คือมันสามารถจัดการกับภาวะที่เกิด collision ได้อย่างง่ายดาย และประสิทธิภาพโดยรวมไม่ค่อยได้รับผลกระทบจาก load factor (อัตราส่วนระหว่างจำนวนโหนดที่มีอยู่ต่อจำนวน buckets).
ข้อเสียของเทคนิคนี้อาจจะมีด้วยเช่นกัน มันอาจจะจับจงใช้ความจำเพิ่มขึ้นหากมีจำนวน chain ที่ยาว นอกจากนี้ ถ้าการทำ hashing ไม่กระจายข้อมูลอย่างเท่าเทียม ก็อาจมีปัญหาด้านประสิทธิภาพเมื่อเกิด collisions บ่อยครั้งในบัคเก็ตเดียวกัน
หากคุณพบว่ามีความสนใจในการเขียนโค้ดเพื่อจัดการข้อมูลแบบไดนามิค ณ Expert-Programming-Tutor (EPT) เรามีคอร์สเรียนที่จะทำให้คุณเข้าใจเบื้องลึกเกี่ยวกับอัลกอริธึมในการจัดการข้อมูลผ่าน Seperate Chaining Hashing และหลากหลายเทคนิคอื่นๆ ใน C# ที่จะทำให้บริการซอฟต์แวร์ของคุณมีประสิทธิภาพมากยิ่งขึ้น.
หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง
หากมีข้อผิดพลาด/ต้องการพูดคุยเพิ่มเติมเกี่ยวกับบทความนี้ กรุณาแจ้งที่ http://m.me/Expert.Programming.Tutor
085-350-7540 (DTAC)
084-88-00-255 (AIS)
026-111-618
หรือทาง EMAIL: NTPRINTF@GMAIL.COM