Bloggang.com : zkaru

Bloggang.com : weblog for you and your gang

เรื่องที่อยากเขียน ... เรื่องที่พยายามเขียน ...

Group Blog

All blogs

Hash Table

hash table เป็น data structure ประเภทหนึ่งที่ใช้เก็บและค้นหาข้อมูลได้เร็วมาก
หลักการคือนำ key ของข้อมูลที่จะจัดเก็บมาทำการคำนวนโดยใช้ hash function เพื่อแบ่งกลุ่ม (bucket)
โดยพยายามให้แต่ละกลุ่มมีจำนวนข้อมูลอยู่น้อยๆ และเท่าๆ กัน
เมื่อจะทำการค้นหาก็นำ key ที่จะค้น มาคำนวนด้วย hash function ว่าอยู่ในกลุ่มไหน
ซึ่งถ้าในกลุ่มมีข้อมูลอยู่น้อย การค้นหาจะได้ผลลัพธ์ที่เร็วมาก

ความเร็วของ hash table จะขึ้นกับการแบ่งกลุ่มของ hash function
hash function ที่ดีต้องทำงานเร็ว และทำให้ข้อมูลมีการกระจายตัว
คือมีข้อมูลอยู่ในแต่ละกลุ่มจำนวนเท่าๆ กัน
หากข้อมูลในแต่ละกลุ่มมีความแตกต่างกันมาก
การค้นในกลุ่มที่มีข้อมูลมากจะทำได้ช้าลง
hash table ที่เร็วที่สุดจะมีข้อมูลอยู่อันเดียวในแต่ละกลุ่ม บางทีจะเรียกว่า map table หรือ perfect hash

ลองมาดูตัวอย่าง hash function แบบง่ายๆ

แบบแรก เป็นการนำเอารหัสของตัวอักษรสองตัวแรกมาเป็น hash value
unsigned int hash_function_first_2_char (unsigned char *key, int length)
{
   unsigned int hash = 0;
   if (length == 1)
      hash = key[0];
   else if (length >= 2)
      hash = key[0] * 256 + key[1];
   return hash;
}

แบบถัดมา เอารหัสของตัวอักษรทุกตัวมาบวกกัน (checksum)
unsigned int hash_function_checksum (unsigned char *key, int length)
{
   unsigned int hash = 0;
   while (length-- > 0)
      hash += *key++;
   return hash;
}

เมื่อได้ค่าจาก hash function แล้ว ก็นำค่ามา modulo กับจำนวนกลุ่ม (BUCKET_SIZE)
ก็จะเป็นเลขกลุ่ม (bucket number) ใช้สำหรับอ้างอิงกลุ่มต่อไป
ตัวอย่าง hash function ทั้งสองแบบ ถึงจะทำงานเร็ว แต่จะให้ผลลัพธ์ซ้ำ (collision)
คือมีการกระจายตัวของข้อมูลไม่ดี ผลก็คือบางกลุ่มจะมีข้อมูลมาก
และบางกลุ่มจะมีข้อมูลน้อยหรือไม่มีข้อมูลเลย

hash function ที่ผมแนะนำคือ one-at-a-time hash ซึ่งคิดค้นโดย Robert Jenkins
Robert Jenkins นอกจากจะคิดค้น hash function แล้วยังเป็นผู้คิดค้น ISAAC
ซึ่งเป็น algorithm สำหรับการสร้างเลขสุ่มอย่างเทียม (pseudorandom number)
และถูกนำไปใช้ทำ stream encryption ที่มีความปลอดภัยสูงอีกด้วย

Robert Jenkins คิดค้น hash function ไว้หลายตัว
แต่ one-at-a-time เป็นตัวที่ง่าย และซับซ้อนน้อยสุด
code ตัวอย่างของ one-at-a-time

unsigned int hash_one_at_a_time (char *data, int len)
{
   int i;
   unsigned int hash;
   hash = 0;
   for (i = 0; i < len; i++) {
      hash += ((unsigned char *)data)[i];
      hash += (hash<<10);
      hash ^= (hash>>6);
   }
   hash += (hash<<3);
   hash ^= (hash>>11);
   hash += (hash<<15);
   return hash;
}

ผลการทดสอบการกระจายตัว (//www.burtleburtle.net/bob/hash/doobs.html#statistics)
ทดสอบโดยใช้คำภาษาอังกฤษจาก dictionary จำนวน 38,470 คำ นำมาคำนวนค่า hash ขนาด 32 bits
ไม่พบผลลัพธ์ซ้ำ (collision) เลย นับเป็น hash function ที่ดีตัวหนึ่งเลยครับ

ผมใช้ one-at-a-time hash ในงานของผมอยู่เหมือนกัน
อย่างใน project XIBOTS ผมใช้เป็นฐานข้อมูลสำหรับเก็บ URL ที่รวบรวมมาได้
ตัว hash function จะอยู่ใน source file db.c
ถ้าสนใจก็ไป download มาดูได้นะครับ

ข้อสังเกตุอย่างหนึ่งสำหรับ hash table คือมันต้องทำงานร่วมกับ data structure แบบอื่น
ตัวมันเองทำหน้าที่แค่แบ่งกลุ่ม คือคำนวน key ออกมาเป็นเลขกลุ่ม
ได้เลขกลุ่มแล้วจะไปหากลุ่มได้อย่างไร โครงสร้างของกลุ่มจะเป็นยังไง
หรือตัวข้อมูลที่อยู่ในแต่ละกลุ่มจะเก็บแบบไหน เราต้องมาออกแบบกันต่างหาก
อย่างใน project XIBOTS กลุ่มข้อมูลจะเป็น fix array ชื่อ hash_bucket มีขนาด HASH_BUCKET_SIZE
ส่วนข้อมูลคือ struct db_url_info จะเก็บเป็น dynamic array อยู่ในกลุ่มข้อมูลอีกที

struct hash_info
{
   int count;
   int size;
   struct db_url_info **array;   /* ข้อมูล URL เก็บเป็น dynamic array */
};
static struct hash_info hash_bucket[HASH_BUCKET_SIZE];   /* กลุ่มข้อมูลเก็บแบบ fix array ขนาด HASH_BUCKET_SIZE */

ข้อเสียของ hash table

ความเร็วของการค้นหาจะขึ้นอยู่กับการเลือกใช้ hash function
หากเลือกใช้ hash function ไม่ดี การค้นหาก็จะช้าลง
และ hash function บางแบบจะเหมาะกับข้อมูลบางประเภทเท่านั้น
พอข้อมูลเปลี่ยนการกระจายตัวก็อาจจะแย่ลง

การเข้าถึงข้อมูลไม่ได้มีการเรียงลำดับ (sort)
ถ้าเราต้องการเข้าถึงข้อมูลแบบที่ต้องการลำดับ เช่น
หาข้อมูลที่มี key น้อยที่สุด หรือ มากที่สุด
หรือหาข้อมูลที่มี key เป็นตัวถัดไป ก็จะทำไม่ได้

ถ้าใครมาถามว่าจะใช้ hash แบบไหนดี
ก็บอกไปเลยว่า ทำทีละอย่าง ครับ