วัตถุประสงค์
- • เรียนรู้หลักการสร้างและการใช้งานตารางแฮช
- • เรียนรู้การวิเคราะห์อัลกอริทึมจากการใช้งานตารางแฮช
ตารางแฮชคืออาร์เรย์ของข้อมูล ใช้สำหรับเก็บข้อมูลเพื่อการค้นหาอย่างรวดเร็ว โดยจะเก็บดัชนี (Index) ของคีย์ใดๆ ที่ไม่ซ้ำกัน ส่วนวิธีการเก็บนั้นจะนำคีย์มาเข้ารหัสด้วยฟังก์ชันแฮช จะได้ผลัพธ์เป็นดัชนีของตาราง ซึ่งเป็นตำแหน่งที่ใช้เก็บคีย์นั้นๆ แต่บางครั้งคีย์คนละตัวอาจจะแฮชได้ดัชนีเดียวกัน เราเรียกว่าแฮชชนกัน ก็ต้องปรับดัชนี และบางครั้งก็ต้องปรับขนาดของตารางแฮช เพื่อให้เก็บคีย์ได้ทั้งหมดในตาราง เช่นการเก็บข้อมูลประชากร โดยใช้เลขบัตรประชาชนเป็นคีย์ ทำได้โดยการแฮชเลขบัตรประชาชน ก็จะได้ดัชนีว่าเลขบัตรนี้จะเก็บในช่องไหนของตาราง เมื่อจะค้นหาข้อมูลประชากร ก็นำเลขบัตรประชาชนมาแฮช ก็จะรู้ว่าเลขบัตรนี้อยู่ในช่องไหน โดยใช้เวลาในการเก็บหรือค้นหาเพียง 1 ครั้งเท่านั้น ซึ่งตารางแฮชนับเป็นวิธีการเก็บข้อมูลสำหรับการค้นหาที่เร็วที่สุด มีค่า Big O = O(1)
แต่ละช่องจะเก็บข้อมูลพิเศษตัวหนึ่ง เรียกว่าคีย์ ร่วมกับข้อมูลอื่นๆ ในตัวอย่างนี้ คีย์คือจำนวนเต็ม หรือตัวเลข ตัวเลขนี้อาจเป็นรหัสประจำตัวหรือหมายเลขบัตรประชาชน
การเพิ่มข้อมูลเข้าไปในตารางแฮช -->> Top
Hash (key) = (key mod 701)
ค่าแฮชของ 580625685 คืออะไร
Hash (580625685) = 580625685 % 701 = 3
ค่าแฮชใช้สำหรับกำหนดตำแหน่งของข้อมูลในตาราง แต่ถ้าตำแหน่งนั้นมีข้อมูลอยู่แล้ว เช่นตารางข้างบน ถ้าใส่ข้อมูลใหม่ที่มีค่าแฮชเป็น 2 จะเกิดการชนกัน (collision) ระหว่างข้อมูลใหม่กับข้อมูลเดิมที่มีอยู่แล้วในตำแหน่ง 2 ทำให้ไม่สามารถใส่ข้อมูลได้ วิธีการแก้ไขคือ เราต้องเลื่อนไปทางขวาของตารางเรื่อยๆจนกว่าจะเจอตำแหน่งที่ว่างอยู่ ซึ่งวิธีนี้เรียกว่าแฮชเส้นตรง (Linear Probing)
การแก้ปัญหาการชน -->> Top
1) การแยกดัชนีด้วยลิงค์ลิสต์ (Separate Chaining)
2) การค้นหาดัชนีว่าง (Open Addressing)
3) การเพิ่มขนาดของตาราง (Rehashing)
การแยกดัชนีด้วยลิงค์ลิสต์ จะสร้างตารางแฮชด้วยอาร์เรย์ แล้วนำคีย์ที่มีดัชนีซ้ำกัน ไปเก็บในลิงค์ลิสต์ตัวเดียวกัน วิธีการนี้จะไม่มีการชนเลย การเพิ่มข้อมูลในตารางแฮชมีค่า Big O = O(1) ส่วนการค้นหามีค่า Big O = O(c) ขึ้นอยู่กับว่าดัชนีที่ซ้ำกัน มีจำนวนคีย์มากน้อยแค่ไหน
Hash(4) = 4 mod 10 = 4
Hash(16) = 16 mod 10 = 6
Hash(9) = 9 mod 10 = 9
Hash(64) = 64 mod 10 = 4
Hash(25) = 25 mod 10 = 5
Hash(36) = 36 mod 10 = 6
Hash(49) = 49 mod 10 = 9
Hash(0) = 0 mod 10 = 0
Hash(81) = 81 mod 10 = 1
เมื่อต้องการค้นหาข้อมูล เช่นต้องการหาว่ามีจำนวนเต็ม 16 อยู่ในตารางหรือไม่ เราก็แฮช 16 ได้ค่าดัชนีเป็น 6 เราก็ค้นหา 16 จากลิงค์ลิสต์ของดัชนี 6 ซึ่งตัวแรกคือ 36 ก็ให้ค้นหาต่อไปจนกว่าจะเจอ ในกรณีนี้เราต้องค้นหาจากลิสต์อีก 2 ครั้ง รวมเป็น 3 ครั้ง คือ O(3) เป็นต้น
แบบฝึกหัด A -->> Top
1. กำหนดขนาดของตารางเป็น 11
• ให้หาฟังก์ชันแฮช
• ให้ใส่ข้อมูลต่อไปนี้ในตาราง 75, 66, 42, 192, 91, 40, 49, 87, 67, 16, 417, 130, 372, 227
• แล้ววาดรูปตารางแฮชพร้อมลิงค์ลิสต์
มีวิธีการหาตำแหน่งที่ว่างในตารางอยู่หลายวิธี เช่นการเลื่อนไปทีละตัวแบบเส้นตรง (Linear Probing) และการเลื่อนข้ามแบบยกกำลังสอง (Quadratic Probing)
แฮชเส้นตรง (Linear Probing) -->> Top
เป็นวิธีการแก้ปัญหาการชนโดยการเลื่อนแบบเส้นตรง ทีละตำแหน่ง ไปทางขวา เมื่อเจอตำแหน่งว่างก็เอาข้อมูลใส่ที่ตำแหน่งนั้น
f(i) = iHashi(x) = (Hash (x) + f (i)) mod Size
ตัวอย่างค่าแฮชของ 701466868 มีค่าเป็น Hash (701466868) = 701466868 % 701 = 2 แต่ปรากฎว่าช่องที่ [2] มีข้อมูลอยู่แล้ว ก็ให้เราเลื่อนทีละตำแหน่งเพื่อหาตำแหน่งที่ว่าง ในที่นี้คือตำแหน่งที่ [5] ของอาร์เรย์ เราก็ใส่ข้อมูลที่มีค่าแฮช [2] ไปในตารางช่องที่ [5] ซึ่งจะเห็นว่าข้อมูลในตารางไม่ตรงกับค่าแฮชของคีย์ ดังนั้นในการค้นหาข้อมูล เราจะต้องตรวจสอบช่องอื่นๆในตาราง เริ่มจากช่องของค่าแฮช ทีละช่องจนกว่าจะเจอข้อมูล หรือเจอช่องที่ว่างซึ่งแปลว่าหาไม่เจอนั่นเอง
• ให้ใส่ค่า 89,18,49,58,69 ลงไปในตารางแฮช
f(i) = i
Hashi(x) = ( Hash(x) + f(i) ) % 10
แบบฝึกหัด B -->> Top
• แฮชฟังก์ชันคือ hash(key) = key % 11
• ให้ใส่ค่าต่อไปนี้ 75, 66, 42, 55, 93, 40, 49, 60
• วาดรูปตาราง
แฮชยกกำลังสอง Quadratic Probing -->> Top
เป็นวิธีการแก้ปัญหาการชนโดยการเลื่อนไปยังตำแหน่งในตารางแฮชแบบยกกำลังสองของจำนวนครั้งที่เลื่อน จนกว่าจะเจอตำแหน่งที่ว่างหรือตำแหน่งที่ถูกลบแล้ว เมื่อเกิดการชน การเลื่อนหาตำแหน่งที่ว่างในตารางแบบยกกำลังสอง มีโอกาสที่เจอตำแหน่งว่างถัดไปมากกว่าการแฮชแบบเส้นตรง นั่นก็คือทำให้การใส่ข้อมูลและค้นหาข้อมูลทำได้เร็วขึ้น
f(i) = i2Hashi(x) = ( Hash(x) + f(i) ) mod Size
ให้ใส่ค่า 89,18,49,58,69 ลงไปในตารางแฮช
f(i) = i2
hi(x) = ( hash(x) + f(i) ) mod 10
แบบฝึกหัด C -->> Top
กำหนดขนาดของตาราง size = 11
แฮชฟังก์ชันคือ Hash(key) = key % 11
ให้ใส่ค่าต่อไปนี้ 75, 66, 42, 55, 93, 40, 49, 60
วาดรูปตาราง
การแฮชซ้ำ (Rehashing) -->> Top
เมื่อตารางใกล้เต็ม จะเกิดการชนกันมากขึ้น ทำให้ใส่ข้อมูลในตารางได้ยากขึ้น ช้าลง วิธีการแก้ปัญหาคือการสร้างตารางใหม่ แล้วถ่ายข้อมูลจากตารางเก่ามาใส่ในตารางใหม่ หรือเรียกว่าแฮชซ้ำ (Rehashing) เสร็จแล้วก็ลบตารางเดิม
โดยปกติควรทำการแฮชซ้ำ เมื่อมีข้อมูลในตารางมากกว่า 50% เช่นถ้าตารางมี 11 ช่อง เมื่อจะใส่ข้อมูลตัวที่ 6 ซึ่งเป็นจำนวนข้อมูลที่เกินกว่า 50% ของขนาดตาราง ก็ให้ทำการแฮชซ้ำเสียก่อนดังนี้
2) ให้อ่านค่าข้อมูลจากตารางเดิม แล้วทำการแฮชข้อมูลทั้งหมดเข้าไปในตารางใหม่
3) ให้ลบตารางเดิม แล้วใช้ตารางใหม่ ในการแฮชข้อมูลตัวใหม่
การแฮชซ้ำ จะเกิดขึ้นตามปริมาณข้อมูลที่เก็บในตารางแฮช เพราะเริ่มแรกเราไม่ทราบจำนวนข้อมูลทั้งหมด ว่ามีจำนวนข้อมูลเท่าไร จึงต้องสร้างตารางไว้พอประมาณเท่านั้น
แฮชฟังก์ชันคือ Hash(x) = x mod 7
Hash(13) = 13%7 = [6]
Hash(15) = 15%7 = [1]
Hash(24) = 24%7 = [3]
จะได้ข้อมูลเข้าไปในตารางตามรูป
เมื่อจะใส่ค่า 6 ปรากฎว่าตารางมีข้อมูลเกินกว่า 50% ก็ให้สร้างตารางใหม่ที่มีขนาด 2 เท่า และเป็นจำนวนเฉพาะ ในที่นี้คือ 2*7 = 14, จำนวนเฉพาะตัวแรกที่มากกว่า 14 คือ 17 จะได้
แฮชฟังก์ชันใหม่คือ Hash(x) = x mod 17
จากนั้นให้ทำการแฮชซ้ำข้อมูลเดิม 3 ตัวจากตารางเดิม เขาไปในตารางใหม่ และแฮชข้อมูลใหม่ 6 และ 23 ดังนี้
Hash(24) = 24%17 = [7]
Hash(13) = 13%17 = [13]
Hash(6) = 6%17 = [6]
Hash(23) = 23%17 = [6], คีย์ 23 ชนกับ คีย์ 6 ถ้าใช้แฮชเส้นตรง คีย์ 23 ก็จะไปอยู่ที่ตำแหน่ง [8]
ให้ใส่ค่า 89,18,49,58,69 ลงไปในตารางแฮช
f(i) = i2
hi(x) = ( hash(x) + f(i) ) mod 10
• กำหนดให้ขนาดของตาราง Size = 11
• ให้ใส่ค่า 89,23,49,58,67,91,80,11,22,33 ลงในตารางแฮช โดยใช้วิธีการแฮชแบบยกกำลังสอง และให้ทำการแฮชซ้ำ เมื่อข้อมูลในตารางมีมากกว่า 50%
f(i) = i2
Hashi(x) = ( Hash(x) + f(i) ) mod 11
Hash(89) = 89%11 = [1]
Hash(23) = 23%11 = [1] ชนกับ 89 ให้แฮชซ้ำแบบยกกำลังสอง ได้ตำแหน่งแรกคือ [2] ซึ่งว่าง
Hash(49) = 49%11 = [5]
Hash(58) = 58%11 = [3]
Hash(67) = 67%11 = [1] ชนกับ 89 ให้แฮชซ้ำแบบยกกำลังสอง ได้ตำแหน่งแรกคือ [1]+1=[2] ซึ่งไม่ว่าง ตำแหน่งถัดไปคือ [1] + 4 = [5] ชนกับ 49 แฮชซ้ำครั้งสาม ได้ตำแหน่ง [1] + 9 = [10] ซึ่งว่างอยู่ตามรูป
เมื่อจะใส่ค่า 91 ปรากฎว่าตารางมีข้อมูลเกินกว่า 50% ก็ให้สร้างตารางใหม่ที่มีขนาด 2 เท่า และเป็นจำนวนเฉพาะ ในที่นี้คือ 2*11 = 22, จำนวนเฉพาะตัวแรกที่มากกว่า 22 คือ 23 จะได้ตารางใหม่ขนาด 23 ดัชนี [0] ถึง [22] ก็ให้เอาข้อมูลทั้งห้าตัวคือ 89,23,58,49,67 มาแฮชซ้ำในตารางใหม่เสียก่อน แล้วค่อยแฮชข้อมูลใหม่คือ 91,80,11,22,33 เข้าไปในตารางใหม่ตามรูป
แบบฝึกหัด D -->> Top
• กำหนดขนาดของตาราง size = 11
• แฮชฟังก์ชันคือ Hash(key) = key % 11
• ให้ใส่ค่าต่อไปนี้ 75, 66, 42, 55, 93, 40, 49, 60
• วาดรูปตาราง
1. หาค่าแฮชของคีย์ที่ต้องการค้นหา
2. ตรวจสอบข้อมูลในตำแหน่งของค่าแฮชในตารางแฮชว่าตรงกันหรือไม่
3. ถ้าไม่ตรงก็ให้เลื่อนไปทางขวาเรื่อยๆจนกว่าจะเจอ
4. ถ้าพบช่องว่าง หมายถึงหาไม่เจอ
ตัวอย่างการค้นหาคีย์ 701466868 จากตารางขนาด 701 ค่าแฮชของ 701466868 มีค่าเป็น Hash (701466868) = 701466868 % 701 = 2
แต่ปรากฎว่าช่องที่ [2] มีข้อมูลอยู่แล้ว ก็ให้เราค้นหาข้อมูลตำแหน่งถัดไปตามวิธีที่ใช้แฮช เช่นถ้าเป็นแฮชเส้นตรงก็เลื่อนทีละตำแหน่ง เป็น [3], [4], [5], … ถ้าเป็นแฮชยกกำลังสอง ก็เลื่อนโดยนับจาก [2] เป็น [2]+1=[3], [2]+4=[6], [2]+9=[11], … ตามลำดับ เพื่อตรวจสอบข้อมูลที่ต้องการค้นหา ในที่นี้ใช้แฮชเส้นตรงจะได้ตำแหน่งที่เจอข้อมูลคือตำแหน่งที่ [5]
Hash (293) = 293 % 10 = 3
ให้ค้นหาข้อมูลจากลิงค์ลิสต์ในตำแหน่งที่ 3 ของตาราง โดยใช้หลักการค้นหาในลิงค์ลิสต์ ซึ่งจะพบข้อมูล 293 ในลิสต์ ตามรูป
การลบข้อมูล -->> Top
เราสามารถลบข้อมูลจากตารางแฮชได้ โดยใช้วิธีการค้นหาจากค่าแฮช ถ้าเจอข้อมูลที่ต้องการ ก็ลบออกไป โดยการทำสัญลักษณ์พิเศษว่า “ลบแล้ว” ซึ่งช่องที่ “ลบแล้ว” กับช่องที่ “ว่าง” ไม่มีข้อมูลเหมือนกัน แต่ความหมายต่างกัน โดยในการค้นหา จะหยุดเมื่อเจอช่อง “ว่าง” แต่จะทำการค้นหาต่อไป ถ้าเจอช่อง “ลบแล้ว”
โปรแกรมสร้างตารางแฮช -->> Top
เนื่องจากตารางแฮชเป็นคลาสที่มีอยู่แล้วใน visual studio เราสามารถใช้งานตารางแฮชได้โดยการเพิ่ม namespace the System.Collections ดังนี้
using System.Collections; เราสร้างตารางแฮชจากคลาส Hashtable ดังนี้
Hashtable symbols = new Hashtable(); สร้างตารางด้วยขนาดค่าเริ่มต้นตามที่ระบบกำหนดเอง
HashTable symbols = new Hashtable(50); สร้างตารางขนาด 50 ช่อง
HashTable symbols = new Hashtable(25, 0.5); สร้างตารางขนาด 25 ช่อง และเพิ่มขนาดของตารางเป็นสองเท่าและจำนวนเฉพาะเมื่อมีจำนวนข้อมูล 50% ของตาราง
ใส่คีย์ name และข้อมูล M. Munlin
ใส่คีย์ age และข้อมูล 47
ใส่คีย์ dept และข้อมูล IT
ใส่คีย์ sex และข้อมูล Male
ใส่คีย์ salary และข้อมูล 30000
หรือจะใส่ข้อมูลในตารางด้วยดัชนีของอาร์เรย์ก็ได้ดังนี้
Symbols["name"] = "M. Munlin";
Symbols["age"] = 47;
Symbols["sex"] = "Male";
Symbols["dept"] = "IT";
Symbols["salary"] = 30000;
เราสามารถใช้ลูป foreach ในการหาค่า key-value ดังนี้
int numElements;
numElements = symbols.Count;
รีเซตตาราง ล้างข้อมูลทั้งหมดด้วยคำสั่ง Clear() ดังนี้
symbols.Clear();
ลบคีย์ออกจากตารางด้วยคำสั่ง Remove() ดังนี้
symbols.Remove("name");
ตรวจสอบว่ามีคีย์อยู่ในตารางหรือไม้ด้วยคำสั่ง ContainsKey() ดังนี้
string aKey;
Console.Write("Enter a key to remove: ");
aKey = Console.ReadLine();
if (symbols.ContainsKey(aKey))
symbols.Remove(aKey);
โปรแกรมนี้มีการใช้คลาส HashTable จึงต้องเรียกใช้งานไลบรารี System.Collections;
และมีการอ่านข้อมูลจากไฟล์ จึงต้องเรียกใช้งานไลบรารี System.IO;
using System.Collections;
using System.IO;
namespace glossary
{
class Program
{
private static void WriteDictFile(Hashtable g)
{
// Write each directory name to a file.
using (StreamWriter sw = new StreamWriter("e:\\words.txt"))
{
foreach (Object key in g.Keys)
{
sw.WriteLine("{0}: {1}", key, g[key]);
}
Console.WriteLine("Done! writing Dictionary.");
}
}
private static void BuildGlossary(Hashtable g)
{
StreamReader inFile;
string line;
string[] words;
inFile = File.OpenText("e:\\words.txt");
char[] delimiter = new char[] { ':' };
while (inFile.Peek() != -1)
{
line = inFile.ReadLine();
words = line.Split(delimiter);
g.Add(words[0], words[1]);
}
inFile.Close();
}
static void Main(string[] args)
{
Hashtable glossary = new Hashtable();
BuildGlossary(glossary);
Console.Write("Enter word to find: ");
string word = Console.ReadLine();
if (glossary.ContainsKey(word))
{
Console.Write("Word: {0} \nMeaning: {1}\n", word, glossary[word]);
}
else
Console.WriteLine("Word {0} not found", word);
Console.ReadKey();
}
}
}
Adder: an electronic circuit that performs an addition operation on binary values
Addressability: the number of bits stored in each addressable location in memory
Bit: short for binary digit
Block: a logical group of zero or more program statements
Call: the point at which the computer begins following the instructions
in a subprogram
Compiler: a program that translates a high-level program into machine code
Data: information in a form a computer can use
Database: a structured set of data
Cpu: central processing unit
Ram: random access memory
Rom: read only memory
โปรแกรมสร้าง Dictionary ด้วยตารางแฮช -->> Top
การเพิ่มข้อมูลในตารางแฮช ทำเพียงครั้งเดียว ดังนั้นค่า Big O คือ O(1) แต่ในกรณีที่มีการชนกันของค่าแฮช ก็ต้องเลื่อนไปยังตำแหน่งที่ว่าง จำนวน c ครั้ง ดังนั้นค่า Big O คือ O(c)
การลบข้อมูลในตารางแฮช ทำเพียงครั้งเดียว ดังนั้นค่า Big O คือ O(1) แต่ในกรณีที่มีการชนกันของค่าแฮช ก็ต้องเลื่อนไปยังตำแหน่งที่ว่าง จำนวน c ครั้ง ดังนั้นค่า Big O คือ O(c)
สรุป -->> Top
• คีย์อาจเป็นตัวเลข หรือตัวอักษร หรือข้อความ ที่สามารถคำนวณหาค่าแฮชได้
• ในการสร้างตารางแฮช ควรสร้างตารางที่มีขนาดเป็นจำนวนเฉพาะ (prime number) เพื่อให้ค่าแฮชมีการกระจายอย่างสมดุล
• ตำแหน่งของข้อมูลในตารางแฮชขึ้นอยู่กับค่าแฮชของข้อมูลนั้นๆ
• เมื่อเกิดการชน เราแก้ปัญหาโดยการเลื่อนไปทางขวาแบบเส้นตรง (Linear probing) หรือแบบยกกำลังสอง (quadratic probing)
• การค้นหาคีย์ในตารางแฮชใชเวลาเร็วมาก โดยปกติแล้วแค่ครั้งเดียวก็เจอแล้ว
• ถ้าเราลบข้อมูลออกจากตารางแฮช เราต้องทำเครื่องหมาย “ลบแล้ว” เพื่อให้การค้นหาข้อมูลเนินการต่อไปอย่างถูกต้อง
• เมื่อตารางใกล้เต็ม โดยมีข้อมูลมากกว่าครึ่งของตาราง ควรทำการสร้างตารางใหม่ (Rehashing)