Hash table ( ตารางแฮช ) 1/2

ไปหน้าแรก | สารบัญ | Laploy.comระเบียนบทความ | บทความจากลาภลอย

สร้าง Hash table ( ตารางแฮช )

ด้วยภาษา C++ และจาวา ตอน 1

ท่านผู้อ่านท่านหนึ่งตั้งกระทู้ถามมาในเว็บบอร์ด laploy.com ว่าดังนี้ “อยากทราบว่า Hashtable ทำงานอย่างไร ใช้กับอะไรบ้าง ในกรณีไหนที่ควรใช้หรือไม่ควร อยากให้อาจารย์ช่วยอธิบายให้หน่อยครับ ขอพระคุณครับ” ผมจึงตัดสินใจเขียนรับใช้เป็นบทความที่คุณจะได้อ่านต่อไปนี้

 ตารางแฮช หรือ Hash table คือโครงสร้างข้อมูลชนิดหนึ่ง (โครงสร้างข้อมูลแบบอื่นๆ คือ สแตก คิว ลิงค์ลิสต์และอื่นๆ อีกมาก) คำว่าตารางแฮช หรือ Hash table เป็นหนึ่งในคำศัพท์ด้านการเขียนโปรแกรมที่มีการทำงานไม่ตรงตามชื่อของมันเลย คำว่า hash (คลุกเคล้า) อันที่จริงหมายถึง mishmash (ไม่คลุกเคล้า) และคำว่าตารางปรกติจะหมายถึงชุดข้อมูลที่จัดเป็นคอลัมน์และแถว ตารางซึ่งเก็บข้อมูลแบบปะปนกันยุ่งดูเหมือนจะไม่มีประโยชน์ในการนำไปใช้งาน แต่อันที่จริงมิได้เป็นเช่นนั้น นักเขียนโปรแกรมสามารถนำตารางแฮชมาใช้เก็บข้อมูลขนาดใหญ่ได้อย่างมีประสิทธิภาพ ในบทความนี้คุณจะได้เรียนวิธีสร้างและวิธีนำตารางแฮชมาประยุกต์ใช้งาน

 

กายวิภาคของตารางแฮช

การประยุกต์ใช้งานเชิงวัตถุที่เลียนแบบชีวิตจริง จะต้องเก็บและเรียกข้อมูลในปริมาณมากๆ โดยข้อมูลจะถูกรวมไว้กับออบเจ็กต์ภายในอินสแตนซ์ของคลาสที่เป็นตัวแทนของออบเจ็กต์ในโปรแกรมประยุกต์ใช้งาน

อ็อบเจ็กต์ต่างๆ จะถูกเก็บโดยใช้สมาชิกโครงสร้างข้อมูลเพียงตัวเดียว การจะเลือกโครงสร้างข้อมูลแบบใดขึ้นอยู่กับลักษณะของการประยุกต์ใช้งาน ตารางแฮชคือโครงสร้างข้อมูลที่ใช้เพื่อเก็บอ็อบเจ็กต์ที่มีความสัมพันธ์ระหว่าง key และ value

ตารางแฮชเป็นอาร์เรย์ที่เก็บพอยน์เตอร์ที่ชี้ไปยังข้อมูล (array of pointer ต่อไปจะเรียกย่อว่า AP) ข้อมูลจะอยู่ในรูปแบบของโครงสร้างข้อมูลที่ผู้ใช้นิยามขึ้นเอง(User Define Structure ต่อไปจะเรียกย่อๆ ว่า UDS) อันประกอบด้วยส่วนต่างๆ สามส่วน คือ key, value และพอยน์เตอร์ที่ทำหน้าที่ชี้ไปยัง UDS ลำดับถัดไปในตารางแฮช เรามีความจำเป็นต้องใช้พอยน์เตอร์นี้เฉพาะในกรณีที่มีการชนกันของข้อมูลดังจะได้อธิบายต่อไปในบทความนี้

key ทำหน้าที่แยกแยะความแตกต่างให้แก่ value ข้อมูลใน UDS แต่ละตัวต้องมี key ที่ไม่ซ้ำกัน value คือข้อมูลที่คู่กันกับ key ซึ่งภายในตารางแฮชหนึ่งๆ อาจมีข้อมูลซ้ำกันได้ คิดเสียว่า key เป็นหมายเลขประจำตัวนักเรียน ซึ่งอยู่คู่กันกับชื่อนักเรียน นักเรียนแต่ละคนย่อมได้รับหมายเลขประจำตัวไม่ซ้ำกัน แต่นักเรียนบางคนชื่ออาจเหมือนกันก็ได้

สิ่งที่ทำให้ตารางแฮชมีความน่าสนใจคือวิธีที่นักเขียนโปรแกรมกำหนด UDS ให้แก่หน่วยในอาร์เรย์ (Array Element ต่อไปจะเรียกย่อๆ ว่า AE) ของตารางแฮช โดยโปรแกรมจะนำ key ของ UDS มา “คลุกเคล้ากัน” ก่อนจะนำไปตัดสินใจว่า AE ใดจะคู่กับ UDS ใด

ถ้าคุณอ่านย่อหน้าบนแล้วงงก็ไม่ต้องใจเสีย ที่คุณงงเป็นเรื่องธรรมดาเพราะหลักการนี้ไม่ใช่แนวคิดที่เห็นภาพได้ชัดเจนในทันที ลองดูตัวอย่างต่อไปนี้แล้วคุณจะเข้าใจ รูปที่ 1 แสดงข้อมูลสามตัวในตารางแฮช ภาพนี้ลดทอนความซับซ้อนลงโดยให้กล่องหนึ่งกล่องเป็นตัวแทนอินสแตนซ์ของ UDS ที่มีค่า key/value เก็บอยู่ ส่วนนิยามโดยละเอียดของ USD ของจริงๆ เราจะว่ากันอีกทีภายหลังในบทความนี้

 

รูปที่ 1 ตารางแฮชคืออาร์เรย์ซึ่งหน่วยข้อมูลชี้ไปยังข้อมูลในโครงสร้างข้อมูลที่ผู้ใช้กำหนดเอง

 

นอกจากนั้นรูปที่ 1 ยังแสดงอาร์เรย์ซึ่งเป็นตัวแทนของตารางแฮช ให้สังเกตว่า AE แต่จะตัวจะชี้ไปยัง UDS ซึ่งทำหน้าเป็นตัวเก็บข้อมูลจริงๆ ในตารางแฮช

UDS แต่ละตัวจับคู่กับ AE โดยใช้ค่า key ใน UDS โดยค่าของ key จะถูกนำมาแปลงเป็นดรรชนีของอาร์เรย์โดยใช้กระบวนการแปลงที่เรียกว่าการแฮช (hashing) ผลลัพธ์ที่ได้คือค่าแฮช (hash value) จะถูกนำไปใช้เป็นค่าดรรชนีของอาร์เรย์ที่ชี้ไปยัง UDS ตัวที่ค่า key ถูกทำการแฮช ค่าดรรชนีของอาร์เรย์ที่เห็นในรูปที่ 1ก็เป็นค่าที่ได้จากกระบวนการแฮชที่กล่าวมานี้

ขอให้คิดเสียว่าการแฮชคือการทำให้ได้ค่าดรรชนีที่จับคู่ค่า key ของ UDS กับ AE ของอาร์เรย์ในตารางแฮช ส่วนการแฮชทำอย่างไรคุณจะได้เรียนในหัวข้อต่อๆ ไปในบทความนี้

เทคนิคการแฮชทำให้ได้ค่าดรรชนีแบบกระจายตัวเสมอกัน (even distribution index) ช่วยให้การค้นข้อมูลทำได้เร็วกว่าการค้นข้อมูลจากดรรชนีที่เรียงลำดับ โดยใช้คำหรือชื่อที่เรียงตัวกันในรูปแบบที่ทำนายได้ เพราะเมื่อเรานำบิตต่างๆ ที่ประกอบเป็นคำหรือชื่อมาสลับสับเปลี่ยนคลุกเคล้ากัน โปรแกรมจะไม่มองบิตต่างๆ ว่าเป็นชุดตัวอักษรอีกต่อไป แต่จะมองว่าเป็นบิตที่รวมตัวกันอย่างสุ่มเสี่ยง (randomize) ซึ่งการค้นจะทำได้อย่างมีประสิทธิภาพมากกว่า

กระบวนการแฮชเป็นกลวิธีความเร็วสูงอย่างหนึ่งที่นำค่า key ที่เรียงตัวตามค่าตัวเลขหรือตัวอักษรมาทำให้เป็นค่าสุ่มปลอม (pseudo random) หากค่า key เป็นชื่อ ตัวอักษรบางตัวจะปรากฏบ่อยกว่าตัวอักษรบางตัว หรือลำดับอักษรบางแบบจะปรากฏบ่อยกว่าบางแบบ การแฮชจะโยกย้ายบิตต่างๆ เพื่อทำให้มันกลายเป็นค่าสุ่มอย่างหลอกๆ และมีอัตราการกระจายตัวที่สม่ำเสมอมากขึ้น ซึ่งจำเป็นต้องใช้เพื่อการค้นตารางแฮชได้อย่างรวดเร็ว

ผลลัพธ์ที่ได้จากการแฮชคือจำนวนที่ไม่มีนัยสำคัญอย่างแท้จริง (no real significance number) ซึ่งเราจะนำมาใช้เป็นค่าดรรชนีในการ เรียก-เก็บ ข้อมูลที่สัมพันธ์กันกับค่าในตารางแฮช ดรรชนีที่เห็นในรูปที่ 1 คือค่าแฮชที่ได้จากการแฮช key ใน UDS ที่คู่กันกับค่าใน AE ของตารางแฮช

 

ปัญหาของการแฮช

เทคนิคการแฮชมิได้สมบูรณ์พร้อม บางครั้งจะเกิดปัญหาขึ้นเมื่อนำค่า key ที่แตกต่างกันสองอันมาทำการแฮชแล้วเกิดได้ผลลัพธ์เป็นค่าแฮชซ้ำกัน และถูกเก็บไว้ใน AE เดียวกัน นักเขียนโปรแกรมได้คิดค้นทางแก้เพื่อจัดการกับความขัดแย้งนี้ได้หลายวิธี

วิธีสามัญในการแก้ไขความขัดแย้งนี้คือการจับหน่วยข้อมูลที่มีค่าแฮชซ้ำกันไปใส่ในลิงค์ลิสต์ ยกตัวอย่างเช่นเรามีข้อมูลสองหน่วยที่ key ของมันให้ค่าแฮชที่ซ้ำกันและถูกนำไปเป็นไว้ใน AE เดียวกันอย่างที่เห็นในรูปที่ 2

 

รูปที่ 2 เมื่อมีค่าแฮชซ้ำกันเราจะใช้ลิงค์ลิสต์มาเชื่อมโยงโครงสร้างข้อมูลที่ผู้ใช้กำหนดเอง

 

เนื่องจากข้อมูลสองชุดจะอยู่ใน AE เดียวกันไม่ได้นักเขียนโปรแกรมจึงสร้างลิงค์ลิสต์ และให้ AE ชี้ไปที่ UDS อันแรก ส่วน UDS อันที่สองไม่ต้องมี AE มาชี้ แต่จะใช้วิธีเชื่อมโยงกับ UDS อันแรกด้วยตัวเชื่อมโยงของลิงค์ลิสต์

ดังที่คุณจะได้เห็นต่อไปในบทความนี้ว่าโปรแกรมหาตำแหน่งของของหน่วยข้อมูลในตารางแฮชโดยการใช้ค่าแฮชเป็นตัวอ้างอิง ค่าแฮชจะถูกนำไปใช้เป็นดรรชนีของ AE ตัวที่ชี้ไปยังหน่วยข้อมูล ตอนนี้คุณคงเห็นปัญหาที่ติดพันมา คือมันจะชี้ไปที่หน่วยข้อมูลตัวแรกเท่านั้น ไม่สามารถชี้ไปยังตัวถัดไปในลิงค์ลิสต์ได้

นักเขียนโปรแกรมแก้ปัญหานี้โดยเขียนโปรแกรมให้อ่านค่า key ของหน่วยข้อมูลตัวแรกและนำมาเปรียบเทียบกับข้อมูลที่ต้องการค้นหา หากไม่ตรงกันโปรแกรมจะเลื่อนไปตรวจดูตัวต่อไปในลิงค์ลิสต์ และทำซ้ำอย่างนี้จนกว่าจะพบข้อมูลที่ต้องการ หรือไม่ก็เคลื่อนไปจนถึงสุดลิงค์ลิสต์

 

การพัฒนาตารางแฮช

การสร้างและประยุกต์ใช้งานตารางแฮชมีสองขั้นตอน ขั้นตอนแรกคือการนิยาม UDS ซึ่งคล้ายการนิยาม node ของลิงค์ลิสต์ ขั้นตอนที่สองคือการสร้างคลาส Hashtable ซึ่งคลาส Hashtable จะทำหน้าที่ประกาศอินสแตนซ์ของ UDS และนิยามสมาชิกข้อมูลและฟังก์ชันสมาชิกที่จำเป็นต้องใช้เพื่อเพิ่ม ลบ และจัดการกับข้อมูลในตารางแฮช

 

คลาส Hashtable

ขั้นตอนแรกของการนำตารางแฮชมาใช้ในโปรแกรมของเราคือการสร้างนิยาม UDS และคลาส Hashtable ที่เราจะใช้ทำงานกับตารางแฮชในโปรแกรมของเรา เราจะเริ่มโดยการนิยาม UDS ดังนี้

typedef struct Metadata{
    struct Metadata(char* key, char* value){
        strcpy(this->key, key);
        strcpy(this->value, value);
        next = NULL;
    }
    char key[SIZE_KEY];
    char value[SIZ_VALE];
    struct Metadata* next;
}METADAT;

 

เราเรียก structure นี้ว่า Metadata เพราะคำว่า metadata หมายถึงข้อมูลที่ใช้พรรณนาข้อมูล ทำนองเดียวกับชื่อคอลัมน์ในโปรแกรมตารางคำนวณ เราจะนำข้อมูลไปใส่ใน structure เมื่อเราประกาศอินสแตนซ์ของ metadata ในคลาส Hashtable

โครงสร้างข้อมูล metadata มีสมาชิกสามตัว สมาชิกตัวแรกคืออาร์เรย์แบบ char ชื่อ key ซึ่งเราใช้ทำหน้าที่เก็บ key ที่เป็นคู่ค่า key/value สมาชิกตัวที่สองคืออาร์เรย์แบบ char ชื่อ value ซึ่งเราใช้ทำหน้าที่เก็บตัวข้อมูลที่เป็นคู่ค่า key/value สมาชิกตัวสุดท้ายชื่อ next เป็นพอยน์เตอร์ทำหน้าที่ชี้ไปยังโครงสร้าง metadata ตัวต่อไป ทำให้โปรแกรมสามารถหาโครงสร้างข้อมูลที่เชื่อมโยงกันจากค่าดรรชนีที่กำหนดได้

ขนาดของอาร์เรย์แบบ char ทั้งสองตัวถูกกำหนดโดยค่าจากการ #define ซึ่งเรานิยามมาโครไว้สองตัวคือ SIZE_KEY และ SIZE_VALUE นิยามของมาโครสองตัวนี้จะอยู่ในไฟล์ HashTable.h

คุณคงสังเกตว่าในนิยาม structure มี constructor อยู่ด้วยเพื่อให้โปรแกรมประยุกต์สามารถกำหนดค่าเริ่มต้นให้แก่ค่า key และ value ของ structure ได้ ซึ่งค่าเหล่านี้จะถูกนำไปใส่ในอาร์เรย์แบบ char ที่เกี่ยวข้อง นอกจากนั้นมันยังทำหน้าที่กำหนดค่าเริ่มต้นให้พอยน์เตอร์ next ที่จะชี้ไปยัง node ถัดไปในลิงค์ลิสต์ดังคุณจะได้เห็นวิธีทำต่อไปในบทความนี้

เมื่อเรานิยามโครงสร้าง metadata แล้ว ต่อไปเราจะนิยามคลาส Hashtable ซึ่งมีหน้าที่ประกาศอินสแตนซ์ของโครงสร้าง metadata และนิยามฟังก์ชันต่างๆ ที่จะนำไปใช้จัดการโครงสร้าง metadata

นิยามของคลาส Hashtable เป็นดังนี้

class Hashtable{
    private:
    int tablesize;
    METADATA** table;
    int size;
    METADATA* current_entry;
    Int current_index;
    Long hashString(char* key);
    METADATA* find(char* key);
public:
    Hashtable(int tablesize = DEFAULT_TABLESIZE);
    virtual ~Hashtable();
    bool put(char* key, char* value);
    bool get(char* key, char* value);
bool contains(char* key);
bool remove(char* key);
void removeAll();
int getSize();
void initIterator();
bool hashNext();
void getNextKey(char* key);
};

 

เราจัดรูปแบบคลาส Hashtable ให้แบ่งเป็นสองส่วนคือส่วน private access specifier และส่วน public access specifier ในบริเวณ private access specifier เราจะใช้เพื่อเก็บสมาชิกข้อมูลห้าตัว และฟังก์ชันสมาชิกอีกสองตัว

สมาชิกข้อมูลตัวแรกเป็นชนิดเลขจำนวนเต็มชื่อ Tablesize ซึ่งภายหลังเราจะกำหนดให้เป็นข้อมูลขนาดของอาร์เรย์พอยน์เตอร์ที่ใช้เก็บหน่วยข้อมูลต่างๆ ในตารางแฮช สมาชิกตัวต่อไปคือพอยน์เตอร์ที่ชี้ไปยังพอยน์เตอร์ (Pointer to Pointer ต่อไปจะเรียกย่อๆ ว่า PTP) ที่เราตั้งชื่อว่า table ทำหน้าที่เป็นอาร์เรย์พอยน์เตอร์ของ metadata ซึ่งเก็บข้อมูลในตารางแฮช ข้อมูลแต่ละหน่วยที่อยู่ใน table คือพอยน์เตอร์ชี้ไปลิงค์ลิสต์ของหน่วยข้อมูลนั้นๆ เบื้องต้นเราใส่ค่า NULL ไว้เพื่อแสดงว่าที่ดรรชนีนี้ยังไม่มีหน่วยข้อมูล

สมาชิกข้อมูลตัวที่สามของคลาส Hashtable เป็นตัวแปรแบบเลขจำนวนเต็มชื่อ size ซึ่งภายหลังเราจะนำค่าจำนวนหน่วยข้อมูลในตารางแฮชมาเก็บ สมาชิกสองตัวสุดท้ายคือ current_entry และ current_index สมาชิก current_entry คือพอยน์เตอร์ที่ชี้ไปยังหน่วยข้อมูลปัจจุบันภายในโครงสร้าง metadata ส่วน current_index คือเลขจำนวนเต็มทำหน้าที่แสดงค่า key ปัจจุบัน ทั้งคู่จะถูกใช้ซ้ำกับทุกหน่วยข้อมูลในตารางแฮช

นอกจากสมาชิกข้อมูลแล้ว ในพื้นที่ส่วน private access specifier ของคลาส Hashtable ยังมีฟังก์ชันสมาชิกอีกสองตัวคือ hashString() และ find() ฟังก์ชัน hashString() ทำหน้าที่รับค่า key ที่เป็นค่าชุด key/value แล้วส่งกลับมาเป็นรหัสที่แฮชแล้ว รหัสแฮชที่ส่งกลับมานี้เป็นค่าดรรชนีของหน่วยข้อมูลที่อยู่ภายในตารางแฮช ดรรชนีคืออาร์เรย์ของ metadata พอยน์เตอร์ ฟังก์ชัน find() ทำหน้าที่ค้นตารางแฮชตาม key ที่กำหนดแล้วคืนผลลัพธ์มาเป็นพอยน์เตอร์ที่ชี้ไปยังโครงสร้าง metadata ที่มีค่าตรงกับ key นั้น ฟังก์ชันทั้งสองนี้จะถูกฟังก์ชันอื่นเรียกใช้อีกทีดังจะพรรนณารายละเอียดต่อไปภายหลังในบทความนี้

ในส่วน public access specifier ของคลาส Hashtable จะประกอบไปด้วยฟังชันสมาชิกต่างๆ ที่เราจำเป็นต้องใช้เพื่อสร้างและจัดการกับตารางแฮช ซึ่งจะได้อธิบายรายละเอียดของแต่ละตัวต่อไปในบทความนี้

 

Constructor และ Destructor

Constructor ของคลาส Hashtable ทำหน้าที่กำหนดค่าเริ่มต้นให้แก่สมาชิกข้อมูลและสร้างตารางแฮชดังแสดงในตัวอย่างโปรแกรมข้างล่าง เมื่อโปรแกรมสร้างอินสแตนซ์ของคลาส Hashtable ขนาดของอาร์เรย์พอยน์เตอร์ (tablesize) จะถูกส่งมายัง constructor ค่าที่จะส่งให้ constructor ต้องเป็นเลขจำนวนเต็ม ซึ่งจะถูกนำไปกำหนดให้เป็นค่าของสมาชิกข้อมูล tablesize ในคลาส Hashtable

Constructor ทำหน้าที่จองหน่วยความจำให้แก่อาร์เรย์พอยน์เตอร์ metadata ซึ่งเราจะใช้เก็บข้อมูลตารางแฮช อาร์เรย์นี้จะถูกกำหนดค่าจากสมาชิก table ของคลาส คุณได้เรียนไปก่อนหน้านี้แล้วว่าสมาชิกข้อมูล table คืออาร์เรย์พอยน์เตอร์ที่ชี้ไปยังโครงสร้าง metadata

 

รูปที่ 3 constructor ประกาศพอยน์เตอร์อาร์เรย์ซึ่งหน่วยข้อมูลแต่ละตัวของอาร์เรย์ชี้ไปยังอินสแตนซ์ของโครงสร้าง metadata

 

ทันทีที่อินสแตนซ์ถูกสร้างขึ้น constructor จะใช้ลูป for เพื่อกำหนดค่าเริ่มต้นให้แก่หน่วยต่างๆ ในตารางให้เป็นค่า NULL สมาชิกข้อมูล size ถูกกำหนดให้เป็นศูนย์เพื่อเป็นเครื่องแสดงว่าไม่มีหน่วยข้อมูลอยู่ภายในตาราง อย่างไรก็ดีคุณอาจเพิ่มขนาดของตารางได้โดยส่งผ่านค่า tablesize มายัง constructor รูปที่ 3 แสดงตารางแฮชที่มีข้อมูลห้าหน่วย

Hashtable(int tablesize){
    Size = 0;
    this->tablesize = tablesize;
    table = new METADATA* [tablesize];
    for(int I=0; I<tablesize; I++){
        table[I] = NULL;
    }
}

เมธอด destructor ของคลาส Hashtable แสดงในตัวอย่างโปรแกรมถัดไป มันมีหน้าที่สองอย่าง อย่างแรกคือเรียกฟังก์ชัน removeAll() เพื่อลบหน่วยข้อมูลทั้งหมดออกจากตารางแฮช อย่างที่สองคือลบพอยน์เตอร์ที่ใช้ชี้ไปยังตารางโดยใช้ตัวกระทำ delete

~Hashtable(){
    removeAll();
    delete[] table;
}

 

การแทรกหน่วยข้อมูลใหม่

คุณแทรกหน่วยข้อมูลใหม่เข้าไปในตารางแฮชได้โดยเรียกใช้ฟังก์ชัน put() ซึ่งเป็นฟังก์ชันที่เรียกใช้จากโปรแกรมประยุกต์ได้โดยตรงเพราะเรานิยามไว้ในส่วน public access specification ของคลาส Hashtable

ดังคุณจะเห็นในตัวอย่างโปรแกรมถัดไปว่าฟังก์ชัน put() ต้องการอาร์กิวเมนต์สองตัว ตัวแรกเป็นพอยน์เตอร์แบบ char ชื่อ key ทำหน้าที่เก็บค่า key ของหน่วยข้อมูลใหม่ อาร์กิวเมนต์ตัวที่สองชื่อ value เป็นพอยน์เตอร์แบบ char อีกเหมือนกัน ทำหน้าที่ชี้ไปยังข้อมูลของหน่วยข้อมูลใหม่ ฟังก์ชัน put() จะคืนค่าบูลีนเป็นจริงหากแทรกหน่วยข้อมูลใหม่ได้สำเร็จมิฉะนั้นจะคืนค่ามาเป็นเท็จ

ดังที่คุณคงจะจำได้ว่าค่า key แต่ละตัวจะต้องไม่ซ้ำกัน ดังนั้นก่อนการแทรกข้อมูลใหม่เราจึงต้องตรวจสอบก่อนว่ามีค่า key ที่จะแทรกอยู่ในตารางแฮชแล้วหรือไม่ ซึ่งทำได้โดยเรียกใช้ฟังก์ชัน find() และส่งค่า key ไปให้ฟังก์ชัน find()

ค่า key ที่เก็บอยู่ในตารางแฮชนั้นเหมือนกันทุกประการกับค่า key ที่เราส่งให้ฟังก์ชัน find() ค่าแฮชคือตัวกำหนดว่าจะนำมันไปใส่ใน bucket ใด และใช้ฟังก์ชัน find() เพื่อเปรียบเทียบค่า key ในตารางกับค่า key ที่ต้องการ คุณจะได้เรียนรายละเอียดของฟังก์ชัน find() ภายหลังในบทความนี้

หากไม่พบ key ที่ต้องการฟังก์ชัน find() จะคืนค่ามาเป็น NULL มิฉะนั้นมันจะคืนค่ามาเป็นพอยน์เตอร์ที่ชี้ไปยังโครงสร้าง metadata ตัวที่มีค่า key นั้น หากฟังก์ชัน find() ไม่ได้คืนค่ามาเป็น NULL แสดงว่ามี key นั้นอยู่ในตารางแฮชแล้วฟังก์ชัน put() จะคืนค่ามาเป็นเท็จ

อย่างไรก็ดีหากฟังก์ชัน find() คืนค่ามาเป็น NULL หน่วยข้อมูลใหม่จะถูกนำไปใส่เพิ่มในตารางโดยสร้างอินสแตนซ์ใหม่ของโครงสร้าง metadata แล้วกำหนดค่าให้เป็น key และ value ของข้อมูลหน่วยใหม่ และนำค่าอ้างอิงไปเก็บไว้ในพอยน์เตอร์ชื่อ entry

ต่อไปเป็นการเรียกฟังก์ชัน hashString() เพื่อส่งค่า key ไปยังข้อมูลหน่วยใหม่ ฟังก์ชัน hashString() ทำหน้าที่แฮชค่า key ซึ่งจะถูกนำไปใช้เป็นดรรชนีของอาร์เรย์สำหรับหน่วยต่างๆ ในตารางแฮช ค่าแฮชจะถูกนำไปใส่ในตัวแปรแบบเลขจำนวนเต็มชื่อ bucket คุณจะได้เรียนการทำงานของฟังก์ชัน hashString() ในบทความนี้ภายหลัง

ค่าจำนวนเต็มใน bucket จะถูกนำไปใช้เป็นดรรชนีของอาร์เรย์ชื่อ data ซึ่งเป็นสมาชิกข้อมูลของคลาส Hashtable ดังที่คุณคงยังจำได้จากหัวข้อที่แล้วในบทความนี้ว่า data คืออาร์เรย์ของพอยน์เตอร์ที่ชี้ไป metadata ซึ่งทำให้ table[bucket] ชี้ไปยังส่วนในตารางที่จะถูกกำหนดให้เป็นหน่วยข้อมูลใหม่

ก่อนที่จะกำหนดส่วนในตารางให้เป็นหน่วยข้อมูลใหม่ หน่วยข้อมูลที่อยู่ใน bucket ขณะนั้นจะต้องถูกนำไปใส่ในอินสแตนซ์ถัดไปของโครงสร้าง metadata ที่ชื่อ entry ซึ่งเราประกาศไว้ในฟังก์ชัน put() หลังการกำหนดค่านี้ หน่วยข้อมูลใหม่จะถูกนำไปใส่ในส่วน table[bucket] ของตารางแฮช ผลกระทบที่เกิดขึ้นคือหน่วยข้อมูลใหม่นี้จะกลายเป็นหน่วยข้อมูลแรกในลิงค์ลิสต์ของอาร์เรย์ตำแหน่งนี้ หากที่ดรรชนีนี้ยังไม่มีหน่วยข้อมูล ค่าของดรรชนีจะเป็น NULL จึงทำให้พอยน์เตอร์ next ของหน่วยข้อมูลใหม่เป็น NULL ซึ่งก็ถูกต้องเพราะหน่วยข้อมูลใหม่เป็นเพียงหน่วยข้อมูลเดียวภายในลิงค์ลิสต์

 

รูปที่ 4 นี่คือสิ่งที่เกิดขึ้นหลังการใส่หน่วยข้อมูลใหม่เข้าไปในตารางแฮช

 

ต่อไปฟังก์ชัน put() จะเพิ่มค่าตัวแปร size ซึ่งเป็นสมาชิกข้อมูลของคลาส Hashtable เพื่อเป็นเครื่องชี้ว่าบัดนี้หน่วยข้อมูลใหม่ได้ถูกเพิ่มเข้ามาในตารางแฮชแล้ว แล้วฟังก์ชัน put() จึงคืนค่าบูลีน เป็นจริง รูปที่ 4 แสดงภาพตารางแฮชเมื่อเราส่งค่า 111 เป็น key และ Bob เป็น value ให้แก่ฟังก์ชัน put()

bool put(char* key, char* value){
    if(find(key) != NULL){
        return false;
    }
    METADATA* entry = new METADATA(key, value);
    int bucket = hashString(key);
    entry->next = table[bucket];
    table[bucket] = entry;
    size++;
    return true;
}

 

การดึงข้อมูล

คุณสามารถดึงข้อมูลที่เก็บอยู่ในตารางแฮชโดยเรียกฟังก์ชัน get() ดังแสดงในตัวอย่างโปรแกรมถัดไป ฟังก์ชัน get() ต้องการอาร์กิวเมนต์สองตัว ตัวแรกคือพอยน์เตอร์แบบ char ที่ชี้ไปยัง key ของหน่วยข้อมูลที่คุณต้องการดึง หากพบ key ที่ต้องการในตารางแฮชฟังก์ชัน get() คัดลอกค่าของหน่วยข้อมูลจากตารางแฮชมายังพอยน์เตอร์ char แล้วมันจะคืนค่าบูลีนเป็นจริง หากไม่พบ key ที่ต้องการในตารางแฮชฟังก์ชัน get()จะคืนค่าบูลีนเป็นเท็จ

ฟังก์ชัน get() ค้นในตารางแฮชโดยเรียกฟังก์ชัน find() และส่งค่า key ที่มันได้รับเป็นอาร์กิวเมนต์ตัวแรกไปให้ฟังก์ชัน find() ฟังก์ชัน find() จะแฮชค่า key ก่อนที่จะค้นในตารางแฮช หากฟังก์ชัน find() พบข้อมูลที่หามันจะคืนค่ามาเป็นค่าอ้างอิงตำแหน่งของโครงสร้าง metadata ที่เก็บ key นั้น ถ้าหาไม่เจอก็จะคืนค่ามาเป็น NULL

ฟังก์ชัน get() จะนำค่าอ้างอิงที่ได้รับจากฟังก์ชัน find() มาใส่ใน temp ซึ่งเป็นพอยน์เตอร์ที่ใช้ชี้ไปยังโครงสร้าง metadata ฟังก์ชัน get() จะตรวจสอบว่าค่าใน temp เป็น NULL หรือไม่ หากใช่มันจะกำหนดให้ AE แรกของอาร์กิวเมนต์ value มีค่าเป็น NULL character (ทำให้ value เป็น string ที่ว่างเปล่า) แล้วฟังก์ชัน get() จะคืนค่าบูลีนเป็นเท็จเพื่อเป็นเครื่องแสดงว่าไม่มี key นั้นในตารางแฮช

หาก temp ไม่เป็น NULL แสดงว่าฟังก์ชัน find() พบค่า key ในตารางแฮช และมันได้คืนค่ามาเป็นตำแหน่งอ้างอิงไปยัง metadata ที่มีหน่วยข้อมูล value ของหน่วยข้อมูลที่ต้องการคัดลอกไปใส่ในอาร์กิวเมนต์ value แล้ว จากนั้นฟังก์ชัน get() จะคืนค่าบูลีนเป็นจริง

bool get(char* key, char* value){
    METADATA* temp = find(key);
    if(temp == NULL){
        value[0] = 9192;
        return false;
    }else{
        strcpy(value, temp->value);
        return true;
    }
}

 

ฟังก์ชัน find()

เราต้องเรียกใช้ฟังก์ชัน find() หลายครั้งจากในฟังก์ชันต่างๆ ดั้งนั้นเราจะมาดูการทำงานโดยละเอียดของฟังก์ชัน find() กันหน่อย อย่างที่คุณคงจำได้ว่าจุดประสงค์ของฟังก์ชัน find() คือค้นตารางแฮชเพื่อหา key หากพบ key ฟังก์ชัน find() จะคืนค่ามาเป็นค่าอ้างอิงโครงสร้าง metadata ที่มี key และ value ที่คู่กันเก็บอยู่ หากไม่พบ key ฟังก์ชัน find() จะคืนค่ามาเป็น NULL

ฟังก์ชัน find() ต้องการอาร์กิวเมนต์เพียงตัวเดียวคือค่า key และส่งผ่านไปให้ฟังก์ชัน HashString() ทำการแฮชค่า key นั้นแล้วส่งกลับมาเป็นค่าแฮชของ key ที่ต้องทำอย่างเพราะ key ที่เก็บอยู่ในตารางแฮช อันที่จริงแล้วคือค่าแฮชของ key จริงๆ ดังนั้นเราจึงต้องแปลง key ให้เป็นจำนวนแฮชก่อน ฟังก์ชัน find() จึงจะสามารถนำไปใช้ระบุตำแหน่งของหน่วยข้อมูลในอาร์เรย์พอยน์เตอร์ได้

ค่าแฮชที่ได้จากฟังก์ชัน hashString() จะถูกนำไปใส่ในตัวแปรแบบเลขจำนวนเต็มชื่อ bucket ซึ่งถูกใช้เป็นดรรชนีเพื่อระบุหน่วยในอาร์เรย์ table ซึ่งก็คือตารางแฮช ค่า AE ของมันคือค่าอ้างอิงไปยังโครงสร้าง metadata ซึ่งจะถูกนำมากำหนดให้กับพอยน์เตอร์ temp ของโครงสร้าง metadata

ตราบเท่าที่พอยน์เตอร์ temp ไม่เป็น NULL ฟังก์ชัน find() จะใช้ฟังก์ชัน strcmp() เพื่อเปรียบเทียบค่า key ในโครงสร้าง metadata กับค่า key ที่ฟังก์ชัน find() ได้รับมาเป็นอาร์กิวเมนต์ และ temp จะถูกใช้เป็นเงื่อนไขของคำสั่ง while ซึ่งทำงานเป็นวนรอบเพื่อการค้นหาใน node ทั้งหมดของลิงค์ลิสต์ หากไม่มีข้อมูลที่ตรงกัน สมาชิกตัวถัดไปของโครงสร้าง metadata ที่ชี้ด้วย temp จะถูกนำไปใส่ใน temp และฟังก์ชัน find() จะเปรียบเทียบค่า key ต่อไป

หากตรวจสอบทั้งตารางแฮชแล้วไม่พบค่าที่ตรงกัน ฟังก์ชัน find() จะคืนค่ามาเป็น NULL

METADATA* find(char* key){
    int bucket = hashString(key);
    METADATA* temp = table(bucket);
    while(temp != NULL){
        if(strcmp(key, temp->key) == 0){
            return temp;
        }
        temp = temp->next;
    }
    return NULL;
}

 

ฟังก์ชัน contains()

หน้าที่ของฟังก์ชัน contains() คือตรวจสอบว่ามีค่า key อยู่ในตารางแฮชหรือไม่ อย่างที่คุณเห็นในนิยามถัดไป ฟังก์ชัน contains() เป็นฟังก์ชันที่สร้างง่ายไม่ซับซ้อน แต่กระนั้นก็มีบทบาทสำคัญในการทำงานกับตารางแฮช

อย่างที่คุณเรียนไปแล้วในตอนต้นบทว่า key ในตารางแฮชต้องไม่ซ้ำกัน ฟังก์ชัน contains() ทำให้โปรแกรมประยุกต์สามารถแน่ใจได้ว่า key ทั้งหมดแตกต่างกันโดยการตรวจสอบว่ามี key ใหม่ที่จะเพิ่มเข้าไปอยู่ในตารางแฮชแล้วหรือยัง

ฟังก์ชัน contains() ต้องการอาร์กิวเมนต์เพียงตัวเดียว ซึ่งก็คือค่าอ้างอิงถึง key ที่คุณต้องการตรวจสอบว่ามีอยู่ในตารางแฮชหรือไม่ ฟังก์ชัน contains() จะคืนค่าบูลีนเป็นจริงหากมี key นั้นแล้ว หรือคืนค่าบูลีนเป็นเท็จหากยังไม่มี key นั้นในตารางแฮช

ฟังก์ชัน contains() ตรวจสอบว่ามี key ที่ต้องการแล้วหรือยังโดยเรียกฟังก์ชัน find() แล้วส่งค่า key ไปให้ คุณเรียนไปแล้วในหัวข้อก่อนหน้านี้ในบทความนี้ว่าฟังก์ชัน find() จะคืนค่ามาเป็นค่าอ้างอิงไปยังโครงสร้าง metadata หรือไม่ก็ NULL ฟังก์ชัน contains() จึงคอยตรวจดูว่าฟังก์ชัน find() คืนค่าอะไรมา

หากฟังก์ชัน find() คืนค่า NULL มาฟังก์ชัน contains() ก็จะคืนค่าบูลีนเป็นเท็จ มิฉะนั้นหากฟังก์ชัน find() คืนค่าอ้างอิงไปยังโครงสร้าง metadata ที่มี key ฟังก์ชัน contains() ก็จะคืนค่าบูลีนเป็นจริง

bool contains(char* key){
    if(find(key) == NULL){
        return false;
    }else{
        return true;
    }
}

 

การลบหน่วยข้อมูล

คุณต้องเรียกใช้ฟังก์ชัน remove() เมื่อใดก็ตามที่โปรแกรมของคุณต้องการลบหน่วยข้อมูลออกจากตารางแฮช ฟังก์ชัน remove() ซึ่งแสดงในตัวอย่างโปรแกรมถัดไปต้องการอาร์กิวเมนต์เพียงตัวเดียว ซึ่งเป็นค่า key ของหน่วยข้อมูลที่คุณต้องการลบออกจากตารางแฮช หากพบหน่วยข้อมูลที่ตรงกับค่า key และลบได้สำเร็จ ฟังก์ชัน find() จะคืนค่าบูลีนเป็นจริงหรือมิฉะนั้นจะคืนค่าบูลีนเป็นเท็จ

ฟังก์ชัน remove() จะแฮชค่า key ก่อนทำการค้นหาและลบหน่วยข้อมูล โดยการเรียกฟังก์ชัน hashString() แล้วส่งค่า key ซึ่งเป็นอาร์กิวเมนต์ที่ฟังก์ชัน remove() ได้รับมา ฟังก์ชัน hashString() จะคืนค่ามาเป็นค่าแฮชของ key นั้น ซึ่งจะถูกนำไปใส่ในตัวแปรชนิดเลขจำนวนเต็มชื่อ bucket

ตัวแปร bucket ถูกใช้เป็นค่าดรรชนีของอาร์เรย์ table ซึ่งเป็นสมาชิกข้อมูลของคลาส Hashtable ค่า table[bucket] คือค่าอ้างอิงไปยังหน่วยข้อมูลในตารางแฮช ซึ่งเก็บลิงค์ลิสต์ที่จะต้องถูกค้น ค่านี้จะถูกนำไปใส่ในพอยน์เตอร์ temp เพื่อการหาซ้ำในลิงค์ลิสต์

จากนั้นฟังก์ชัน remove() จะตรวจดูว่ามีหน่วยข้อมูลอยู่หรือไม่โดยเปรียบเทียบพอยน์เตอร์ temp กับค่า NULL หากพบว่าเป็น NULL มันจะส่งคืนค่าบูลีนเป็นเท็จไปให้บรรทัดคำสั่งที่เรียกฟังก์ชัน remove() หาก temp ไม่ใช่ NULL แสดงว่าในลิงค์ลิสต์มีหน่วยข้อมูลอยู่อย่างน้อยหนึ่งหน่วย ฟังก์ชัน remove() จะตรวจสอบว่าหน่วยข้อมูลที่จะลบเป็นหน่วยใดในลิงค์ลิสต์ของตารางแฮช

ขั้นแรกฟังก์ชัน remove() จะตรวจสอบว่าหน่วยข้อมูลเป็น node แรกของลิงค์ลิสต์หรือไม่โดยใช้ฟังก์ชัน strcmp() เพื่อตรวจสอบค่า key ของหน่วยข้อมูลกับค่า key ที่ฟังก์ชัน remove() ได้รับมา หากมีค่าตรงกันฟังก์ชัน strcmp() จะคืนค่ามาเป็นศูนย์ ฟังก์ชัน remove() ก็จะรู้ว่าหน่วยข้อมูลที่ต้องการลบคือ node แรกของลิงค์ลิสต์ หากหน่วยข้อมูลไม่ใช่ node แรกของลิงค์ลิสต์ ฟังก์ชัน remove() จะต้องทำงานซ้ำเพื่อตรวจสอบ node ที่เหลือในลิงค์ลิสต์เพื่อค้นหาหน่วยข้อมูลที่ต้องการลบ

หากหน่วยข้อมูลที่ต้องการลบคือ node แรกในลิงค์ลิสต์ ฟังก์ชัน remove() จะดำเนินการสลับตำแหน่ง node ภายในลิงค์ลิสต์ อย่างที่คุณเรียนไปแล้วก่อนหน้านี้ในบทความนี้ว่า metadata ประกอบด้วยสามส่วนคือ key, value และ next ที่ใช้อ้างอิงไปยังหน่วยข้อมูลถัดไปในลิงค์ลิสต์

ค่าตำแหน่งของ node ที่ชี้โดย next จะถูกนำไปเก็บไว้ใน table[bucket] ซึ่งก่อนหน้านี้เก็บค่าอ้างอิงไปยังหน่วยข้อมูลที่กำลังจะถูกลบออกจากตารางแฮช การทำเช่นนี้เป็นเหตุให้หน่วยข้อมูลถัดไปกลายเป็น node แรกของลิงค์ลิสต์เพราะว่าหน่วยข้อมูลปัจจุบันเป็นหน่วยข้อมูลอันแรกของลิงค์ลิสต์

เมื่อสลับที่แล้วฟังก์ชัน remove() จะใช้ตัวกระทำ delete เพื่อยกเลิกการจองหน่วยความจำของหน่วยข้อมูลปัจจุบัน ซึ่งถูกชี้โดยพอยน์เตอร์ temp หน่วยข้อมูลจึงถูกลบออกไปจากตารางแฮชด้วยการทำงาน ณ จุดนี้ จากนั้นฟังก์ชัน remove() จะลดค่า size ลงหนึ่งเพื่อให้สัมพันธ์กับการที่ข้อมูลถูกลบไป แล้วคืนค่าบูลีนเป็นจริงเพื่อเป็นเครื่องแสดงว่าประสบความสำเร็จในการลบหน่วยข้อมูล

หากหน่วยข้อมูลไม่ใช่ node แรกของลิงค์ลิสต์ ฟังก์ชัน remove() จะต้องขยับไปตรวจดู node ถัดไปในลิงค์ลิสต์ ซึ่งทำได้โดยนำค่า next ของโครงสร้าง metadata ซึ่งเป็นหน่วยข้อมูลถัดไป มาใส่ในพอยน์เตอร์ temp_next ตราบเท่าที่พอยน์เตอร์ temp_next ไม่ใช่ NULL ฟังก์ชัน remove() จะเรียกฟังก์ชัน strcmp() เพื่อเปรียบเทียบค่า key ที่ฟังก์ชัน remove() ได้รับมาเป็นอาร์กิวเมนต์ กับค่า key ที่เป็นสมาชิกของโครงสร้างข้อมูลที่ temp_next ชี้อยู่

หากพบว่าตรงกัน จะมีการสลับที่ node เหมือนการสลับที่ node เมื่อพบค่าที่ตรงกันกับ node แรกของลิงค์ลิสต์ หากไม่ตรงกันค่า next จะถูกนำไปใส่ในพอยน์เตอร์ temp_next แล้วดำเนินการค้าหาต่อไป หากหาค้นหาจนเกลี้ยงลิงค์ลิสต์แล้วไม่พบค่า key ฟังก์ชัน remove() จะคืนคาบูลีนเป็นเท็จ

bool remove(char* key){
    int bucket = hashString(key);
    METADATA* temp = table[bucket];
    if(temp == NULL){
        return false;
    }else if(strcmp(key, temp->key) == 0) {
        table[bucket] = temp->next;
        delete temp;
        size--;
        return true;
    }else{
        METADATA* temp_next = temp->next;
        while(temp_next != NULL){
            if(strcmp(key, temp_next->key) == 0){
                temp->next = temp_next->next;
                delete temp_next;
                size--;
                return true;
            }
            temp = temp->next;
            temp_next = temp_next->next;
        }
    }
    return false;
}

อีกวิธีหนึ่งที่จะลบรายการจากตารางแฮชคือใช้ฟังก์ชัน removeAll() ดังแสดงในตัวอย่างโปรแกรมถัดไป ฟังก์ชันนี้จะลบข้อมูลทั้งหมดออกจากตารางแฮช ฟังก์ชัน removeAll() ทำเช่นนั้นได้โดยใช้ลูป for วนซ้ำไปแต่ละหน่วยในตาราง ในแต่ละหน่วยจะมีคำสั่ง while คอยวนลบหน่วยในลิงค์ลิสต์ เมื่อลบออกไปได้หนึ่งหน่วยแล้วลูป for จะเคลื่อนไปยังหน่วยถัดไปไล่ลบไปเช่นนี้จนกระทั้งหน่วยข้อมูลทุกหน่วยถูกลบออกจากตารางแฮช

การทำงานเริ่มโดยประกาศตัวแปรชื่อ temp ซึ่งเป็นพอยน์เตอร์ทำหน้าที่ชี้ไปยังโครงสร้าง metadata จากนั้น temp จะได้รับค่าอ้างอิงไปยังหน่วยข้อมูลแรกในอาร์เรย์ table ของตารางแฮช

ตราบเท่าที่พอยน์เตอร์ temp ไม่มีค่าเป็น NULL ฟังก์ชัน removeAll() จะใส่ค่าอ้างอิงไปยังหน่วยข้อมูลถัดไปของหน่วยข้อมูลปัจจุบัน (คือค่าจากสมาชิกข้อมูล next ของโครงสร้าง metadata) ค่า key และ value จะถูกแสดงบนจอภาพก่อนที่หน่วยข้อมูลตัวที่ถูกชี้ด้วยพอยน์เตอร์ temp จะถูกลบด้วยตัวกระทำ delete

หน่วยข้อมูลที่ถูกชี้ด้วยพอยน์เตอร์ next จะถูกนำไปใส่ในพอยน์เตอร์ temp แล้วฟังก์ชัน removeAll() จะกลับไปทำงานที่ต้นลูป while เพื่อลบหน่วยข้อมูลถัดไปในตารางแฮช การทำงานจะดำเนินไปเช่นนี้จนพอยน์เตอร์ temp มีค่าเป็น NULL ซึ่งหมายถึงตารางแฮชว่างเปล่า (เมื่อ temp มีค่าเป็น NULL แสดงว่าเสร็จไปหนึ่งลิงค์ลิสต์ จาวาจะกลับออกไปที่ลูปนอกเพื่อดำเนินการกับลิงค์ลิสต์ตัวต่อไป) สุดท้ายฟังก์ชัน removeAll() จะกำหนดค่า size ซึ่งเป็นสมาชิกของคลาส Hashtable ให้เป็นศูนย์เพื่อเป็นเครื่องแสดงว่าบัดนี้ไม่มีหน่วยข้อมูลในตารางแฮชแล้ว

void removeAll(){
    for(int i=0; i<tablesize; i++){
        METADATA* temp = table[i];
        while(temp != NULL){
            METADATA* next = temp->next
            cout << 93Removing node 96key:94 << temp->key << 93\t94 << temp->value << endl;
            delete temp;
            temp = next;
        }
    }
    size = 0;
}

 

ฟังก์ชัน getSize()

ฟังก์ชัน getSize() เป็นฟังก์ชันที่สร้างง่ายที่สุดในคลาส Hashtable เพราะอย่างที่เห็นในตัวอย่างโปรแกรมถัดไปว่ามันมีคำสั่งเพียงบรรทัดเดียว ทำหน้าที่อ่านค่าจากสมาชิกข้อมูล size แล้วส่งเป็นค่าจำนวนเต็มให้โปรแกรมที่เรียกใช้งานมัน

คุณอาจสงสัยว่าทำไมต้องนิยามฟังก์ชัน getSize() ในเมื่อเราจะให้โปรแกรมประยุกต์อ่านค่าสมาชิกข้อมูล size โดยตรงก็ได้ คำตอบคือเพื่อสร้างบูรณภาพของข้อมูล เพราะหากเราย่อมให้โปรแกรมเข้าถึงสมาชิกข้อมูล size ได้โดยตรง คำสั่งในโปรแกรมอาจไปเปลี่ยนแปลงค่า size ให้เป็นค่าที่ไม่ถูกต้องได้ ดังนั้นการกำจัดการเข้าถึงไว้เฉพาะฟังก์ชันสมาชิกของคลาสจึงสามารถป้องกันความผิดพลาดในลักษณะนี้ได้

int getSize(){
    return size;
}

 

ฟังก์ชัน hashString()

ฟังก์ชัน hashString() เป็นอีกฟังก์ชันหนึ่งที่ฟังก์ชันต่างๆ ในคลาส Hashtable เรียกใช้เมื่อต้องการแปลงค่า key ให้เป็นค่าแฮช ฟังก์ชัน hashString() ต้องการอาร์กิวเมนต์เพียงตัวเดียวคือพอยน์เตอร์ชนิด char ซึ่งชี้ไปยังค่า key ที่จะแฮช ผลการแฮชที่ได้จะส่งคืนมาให้เป็นข้อมูลชนิด long

นิยามของฟังก์ชัน hashString() แสดงในตัวอย่างโปรแกรมถัดไป การแฮชเริ่มโดยตรวจสอบขนาดของ key โดยใช้ฟังก์ชัน strlen() ขนาดจะถูกนำไปใส่ในตัวแปรชนิดจำนวนเต็มชื่อ n และเราประกาศตัวแปรแบบ long ชื่อ h ซึ่งเรากำหนดค่าเริ่มต้นเป็นศูนย์ เราจะใช้ตัวแปรนี้เก็บพักค่าระหว่างทำการประมวลผลค่าแฮช

ขั้นตอนการแฮชเป็นการทำงานกับค่า key ในระดับบิต เป็นการทำให้ค่า key กลายเป็นค่าสุ่ม ฟังก์ชัน hashString() จะใช้ลูป for วนทำงานกับแต่ละตัวอักษรของ key ในการวนแต่ละรอบตัวแปร h จะถูกเลื่อนบิต (h<<2) และบิตของตัวอักษรปัจจุบันของ key จะถูกนำไปใส่แทนที่บิตที่ถูกเลื่อน แล้วนำผลลัพธ์ที่ได้ไปเก็บในตัวแปร h กระบวนการนี้ดำเนินไปเรื่อยจนกระทั่งตัวอักษรของ key ถูกแฮชจนครบทุกตัว

ถัดไปฟังก์ชัน hashString() จะทำการคำนวณเพื่อหาค่าโมดูลัส (การหารแบบเอาเศษ) ของค่าแฮชขั้นสุดท้าย (h) กับค่าขนาดของตาราง (h % tablesize) ค่าที่ได้จากการทำโมดูลัสอาจเป็นได้ทั้งบวกและลบ อย่างไรก็ดีค่าแฮชต้องเป็นจำนวนบวกเท่านั้น ดังนั้นฟังก์ชัน hashString() จึงแปลงค่าที่ได้จากการทำโมดูลัสให้เป็นค่าสัมบูรณ์เสียก่อน (abs(h % tablesize))

long hashString(char* key){
    int n = strlen(key);
    long h = 0;
    for(int i=0; i<n; i++){
        h = (h << 2) + key[i];
    }
    return abs(h % tablesize);
}

 

หมายเหตุ : เป้าหมายของการแฮชคือการนำชุดข้อมูลที่เป็น key มาแปลงเป็นค่าดรรชนีซึ่งมีลำดับการกระจายตัวที่เหมาะสม แม้นักเขียนโปรแกรมหลายคนจะเห็นพ้องกันว่าขนาดของแฮชควรเป็นจำนวนเฉพาะ (prime number) แต่ยังมีขั้นตอนวิธี (Algorithm) ในการแฮชอีกหลายแบบ อย่างไรก็ดีขั้นตอนวิธีในการหาค่าแฮชทุกแบบจะมีการเลื่อนบิตร่วมอยู่ด้วยเสมอ

ไม่มีฟังก์ชันใดให้ค่าแฮชที่ดีพร้อม ฟังก์ชันแฮชบางแบบก็เหมาะกับข้อมูลบางแบบ ตามปรกติแล้วนักเขียนโปรแกรมจะทดสอบฟังก์ชันแฮชหลายๆ แบบกับชุดข้อมูลที่ต้องการก่อนที่จะเลือกฟังก์ชันแฮชที่ให้ประสิทธิภาพสูงสุด

 

เรื่อง Hash table ยังไม่จบ (ที่ท่านอ่านไปนี้เป็นครึ่งแรก) เนื่องจาก Blog ของ Space โพสหนึ่งตอนยาวมากไม่ได้ ผู้เขียนจึงแบ่งออกเป็นสองโพส กรุณาติดตามอ่านส่วนที่เหลือในโพสถัดไป

ตอนต่อไป : ฟังก์ชัน initIterator() ส่วนอื่นๆ ของคลาส Hash table และการสร้างในจาวา

Post a comment or leave a trackback: Trackback URL.

ความเห็น

  • Tatchai R.  On ตุลาคม 5, 2007 at 8:18 pm

    เยี่ยมๆ ครับ กําลังสนใจอยู่พอดี เซิร์สจากกูเกิลเจอ

  • L'amour  On กุมภาพันธ์ 16, 2009 at 9:27 pm

    โอ๊ว ข้าน้อยขอคาราวะ ท่านเทพจิง อ่านแล้วทราบซึ้งเข้าใจอย่างท่องแท้เลยครับขอบคุณครับ!

  • I Love MoohNoi  On เมษายน 30, 2009 at 7:40 pm

    มึน

  • Nu  On ตุลาคม 14, 2009 at 7:54 pm

    ขอบคุณนะคะ ^^

  • suchon  On มีนาคม 10, 2010 at 4:56 pm

    ขอบคุณมากครับ อ่านแล้วเล่นเอามึนเลยเหอๆ้http://www.iTouchAccessoriesZ.us

  • sihanouvong  On เมษายน 2, 2010 at 4:38 pm

    Wow !!!!!!!!!!!Thanks jaaaaaaaaaaaaa @^^@

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s

%d bloggers like this: