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

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

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

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

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

 

ฟังก์ชัน initIterator()

ฟังก์ชัน initIterator() ทำหน้าที่กำหนดค่าเริ่มต้นให้แก่ตัวแปรบางตัวของคลาสซึ่งทำหน้าที่จัดการลิงค์ลิสต์ ฟังก์ชัน initIterator() ไม่ต้องการอาร์กิวเมนต์ใดๆ และไม่คืนค่าใดๆ ดังแสดงในตัวอย่างโปรแกรมถัดไป ฟังก์ชัน initIterator() จะถูกเรียกโดยฟังก์ชัน displayAll() ซึ่งเป็นฟังก์ชันที่ทำหน้าที่แสดงข้อมูลทั้งหมดภายในตารางแฮช คุณจะได้เรียนเรื่องฟังก์ชัน displayAll() ในหัวข้อ “การสร้างตารางแฮชด้วยภาษา C++” ต่อไปในบทนี้

เมื่อฟังก์ชัน initIterator() ถูกเรียกมันจะกำหนดค่าให้สมาชิกข้อมูลสองตัวของคลาส Hashtable สมาชิก current_entry จะได้รับการกำหนดค่าให้เป็น NULL และสมาชิก current_index จะถูกกำหนดให้มีค่าเท่ากับสมาชิก tablesize

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

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

ฟังก์ชัน displayAll() จะเรียกใช้งานฟังก์ชัน initIterator() เพื่อตรวจหาหน่วยข้อมูลตัวแรกในตารางแฮชก่อนการเรียกใช้งานฟังก์ชัน hasNext() และ getNextKey() เพราะทั้งสองฟังก์ชันนี้จะเรียกใช้สมาชิก current_entry และ current_index โดยตรง เราจะดูรายละเอียดของสองฟังก์ชันนี้ในหัวข้อถัดไป


void initIterator(){
    current_entry = NULL;
    current_index = tablesize;
    for(int I=0; I<tablesize; I++){
        if(table[I] == NULL){
            continue;
        }else{
            current_entry = table[I];
            current_index = i;
            break;
        }
    }
}

 

ฟังก์ชัน hasNext() และ getNextKey()

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

ฟังก์ชัน hasNext() ทำการตรวจสอบโดยเปรียบเทียบค่าของ current_entry กับ NULL หากค่าของ current_entry เป็น NULL ฟังก์ชัน hasNext() จะคืนค่าบูลีนเป็นเท็จ มิฉะนั้นจะคืนค่าบูลีนเป็นจริง

bool hasNext(){
    if(current_entry == NULL){
        return false;
    }else{
        return true;
    }
}

 

ดังที่คุณคงยังจำได้จากหัวข้อ “ฟังก์ชัน initIterator()” ว่าทั้ง current_entry และ current_index ล้วนเป็นสมาชิกข้อมูลของคลาส Hashtable โดย current_entry ทำหน้าที่เก็บค่าอ้างอิงไปยังหน่วยข้อมูลปัจจุบันในตารางแฮช ส่วน current_index เก็บค่าดรรชนีของอาร์เรย์ table ที่ชี้ไปยังหน่วยข้อมูลปัจจุบัน

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

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

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

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

ค่าของ next จะถูกนำมาเปรียบเทียบกับ NULL ในคำสั่ง if หาค่าของ next ไม่เป็น NULL แสดงว่ายังมีหน่วยข้อมูลอื่นอยู่ภายในลิงค์ลิสต์ที่ตำแหน่งดรรชนีนี้อีก ค่าของ next จะถูกนำไปใส่ใน current_entry ทำให้หน่วยข้อมูลถัดไปกลายเป็นหน่วยข้อมูลปัจจุบันของตารางแฮช

อย่างไรก็ดีหากค่า next เท่ากับ NULL ฟังก์ชัน getNextKey() จะข้ามแต่ละหน่วยในอาร์เรย์ table ไปเพื่อหาหน่วยในอาร์เรย์ที่ไม่เป็น NULL ซึ่งหากหาเจอฟังก์ชัน getNextKey() จะคัดลอกค่าของ AE ไปใส่ไว้ใน current_entry และคัดลอกค่าดรรชนีของ AE นั้นไปใส่ใน current_index แล้วฟังก์ชัน getNextKey() ก็จะจบการทำงาน

หากหน่วยที่ยังเหลือในอาร์เรย์ table เป็น NULL ทั้งหมดแสดงว่าไม่มีหน่วยข้อมูลในตารางแฮชแล้ว ฟังก์ชัน getNextKey() ก็จะนำค่า NULL ไปใส่ใน current_entry และนำค่าใน tablesize ไปใส่ใน current_index ค่า key และ value นี้ถูกดึงออกมาจากตารางแฮชโดยไม่มีลำดับที่เฉพาะเจาะจงแต่อย่างใด เพราะโดยทั่วไปแล้วตารางแฮชไม่สนับสนุนการเก็บข้อมูลโดยเรียงตามลำดับ

void getNextKey(char* key){
    if(current_entry == NULL){
        key[0] = 9192;
        return;
    }
    strcpy(key, current_entry->key);
    if(current_entry->next != NULL){
        current_entry = current_entry->next;
    }else{
        for(int i=current_index+1; i<tablesize; i++){
            if(table[i] == NULL){
                continue;
            }
            current_entry = table[i];
            current_index = i;
            return;
        }
        current_entry = NULL;
        current_index = tablesize;
    }
}

 

สร้างตารางแฮชด้วยภาษา C++

ตอนนี้คุณรู้แล้วว่าส่วนประกอบต่างๆ ของคลาส Hashtable ทำงานอย่างไร ได้เวลานำชิ้นส่วนต่างๆ มาประกอบเข้าด้วยกันเป็นโปรแกรมประยุกต์ใช้งานด้วยภาษา C++ เสียที เราจะแบ่งโปรแกรมออกเป็นสามไฟล์ ประกอบด้วย HashtableDemo.cpp เป็นไฟล์เก็บตัวโปรแกรมประยุกต์ใช้งาน HashTable.h เป็นไฟล์เฮดเดอร์ทำหน้าที่เก็บนิยามของโครงสร้าง metadata และคลาส Hashtable และไฟล์ Hashtable.cpp ทำหน้าที่เก็บโค้ดของฟังก์ชันต่างๆ ที่ท้ายหัวข้อนี้จะมีโค้ดของโปรแกรมทั้งสามไฟล์โดยสมบูรณ์ ในหัวข้อนี้เราจะมาให้ความสนใจกับวิธีนำคลาส Hashtable มาประยุกต์ใช้ ส่วนเรื่องเมธอดและสมาชิกต่างๆ ของคลาสนั้นคุณได้เรียนไปเรียบร้อยแล้ว

โปรแกรมจะเริ่มการทำงานโดยประกาศอินสแตนซ์ของคลาส Hashtable แล้วกำหนดค่าอ้างอิงของคลาสให้กับ พอยน์เตอร์ชื่อ hashtable จากนั้นเราประกาศตัวแปรแบบ char สองตัวให้เป็นค่าจากมาโคร SIZE_KEY และ SIZE_VALUE ที่เรานิยามไว้เพื่อกำหนดขนาดของอาร์เรย์ สองอาร์เรย์นี้ทำหน้าที่เก็บ key และ value ของข้อมูลที่คุณจะใส่เข้าไปในตารางแฮช

ต่อมาเราใช้ฟังก์ชัน strcpy() คัดลอกค่า key และ value ไปใส่ในอาร์เรย์ key และ value แต่ก่อนที่เราจะนำมันแทรกเข้าไปในตารางได้ เราจะต้องตรวจสอบก่อนว่ามี key ค่านี้อยู่ในตารางแฮชแล้วหรือยังด้วยการเรียกใช้ฟังก์ชัน contains() อันเป็นฟังก์ชันสมาชิกของคลาส Hashtable() ฟังก์ชัน contains() จะคืนค่าบูลีนเป็นจริงหากมี key นั้นแล้ว ถ้าไม่เช่นนั้นก็จะคืนค่าบูลีนเป็นเท็จ ให้สังเกตว่าเรานำตัวกระทำ not (!) มาใช้เพื่อกลับตรรกะของค่าที่ฟังก์ชันส่งมา เราทำเช่นนี้เพื่อให้บรรทัดคำสั่งภายใต้ if ทำงานต่อไป

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

เราทำเช่นนี้อีกสองหนเพื่อแทรกค่า key และ value อีกสองชุดเข้าไปในตารางแฮช ข้อมูลเหล่านี้จะถูกแสดงออกมาบนจอภาพดังนี้ และหน้าตาของตารางแฮชจะเป็นดังรูปที่ 5

 

รูปที 11-5 สภาพของตารางแฮชหลังการทำงานของฟังก์ชัน put() ครั้งสุดท้าย

 

Adding node – key: 389 value: Mary

Adding node – key: 415 value: Henry

Adding node – key: 999 value: Joe

เมื่อค่าทั้งสามถูกแทรกเข้าไปเรียบร้อยแล้ว โปรแกรมจะเรียกฟังก์ชัน displayAll() ซึ่งเป็นฟังก์ชันที่อยู่เดี่ยวๆ ไม่ใช่ฟังก์ชันสมาชิกของคลาส Hashtable เพื่อแสดงข้อมูลภายในตารางแฮช ฟังก์ชันนี้ถูกนิยามไว้ใต้ฟังก์ชัน main() ในตัวอย่างนี้

เมื่อฟังก์ชันทำงานเราจะเห็นข้อความต่อไปนี้ปรากฏบนจอภาพ

Current node is hashtable:

Key: 415 value: Henry

Key: 999 value: Joe

Key: 389 value: Mary

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

After removing 415:

Current nodes in hashtable:

Key: 999 value: Joe

Key: 389 value: Mary

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

Destroying hashtable:

Remove node – key: 999 Joe

Remove node – key: 389 Mary

ซอร์โค้ดสมบูรณ์ในภาษา C++

#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include 93Hashtable.h
void displayAll(Hashtable* hashtable);
void main(){
    Hashtable* hashtable = new Hashtable();
    char key[SIZE_KEY];
    char value[SIZE_VALUE];
    strcpy(key, 9338994);
    strcpy(value, 93Mary94);
    if(!hashtable->contains(key)){
        cout << 93Adding node 96 key: 93 << key << 93value: 93 << value << endl;
        hashtable->put(key, value)
    }
    strcpy(key, 9341594);
    strcpy(value, 93Henry94);
    if(!hashtable->contains(key)){
        cout << 93Adding node 96 key: 93 << key << 93value: 93 << value << endl;
        hashtable->put(key, value)
    }
    strcpy(key, 9399994);
    strcpy(value, 93Joe94);
    if(!hashtable->contains(key)){
        cout << 93Adding node 96 key: 93 << key << 93value: 93 << value << endl;
        hashtable->put(key, value)
    }
    displayAll(hashtable);
    hashtable->remove(9341594);
    cout << 93After removing 415:94 << endl;
    displayAll(hashtable);
    count << 93\nDestroying hashtable:94 << endl;
    delete hashtable;
}

void displayAll(Hashtable* hashtable){
    char key[SIZE_KEY];
    char value[SIZE_VALUE];
    cout << 93\nCurrent nodes in hashtable:94 << endl;
    hashtable->initIterator();
    while(hashtable->hasNext()){
        hashtable->getNextKey(key);
        hashtable->get(key, value);
        cout << 93key: 93 << key << 93\tvalue: 93 << value << endl;
    }
}

/////////////// HashTable.h //////////////////
#include <string.h>
#define SIZE_KEY32
#define SIZE_VALUE256
#define DEFAULT_TABLESIZE101

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;

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.cpp ////////////////
#include <iostream.h>
#include <stdlib.h>
#include 93Hashtable.h
Hashtable::Hashtable(int tablesize){
    Size = 0;
    this->tablesize = tablesize;
    table = new METADATA* [tablesize];
    for(int I=0; I<tablesize; I++){
        table[I] = NULL;
    }
}

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

bool Hashtable::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;
}

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

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

bool Hashtable::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;
}

void Hashtable::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;
}

int Hashtable::getSize(){
    return size;
}

METADATA* Hashtable::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;
}

long Hashtable::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);
}

void Hashtable::initIterator(){
    current_entry = NULL;
    current_index = tablesize;
    for(int I=0; I<tablesize; I++){
        if(table[I] == NULL){
            continue;
        }else{
            current_entry = table[I];
            current_index = i;
            break;
        }
    }
}

bool Hashtable::hasNext(){
    if(current_entry == NULL){
        return false;
    }else{
        return true;
    }
}

void Hashtable::getNextKey(char* key){
    if(current_entry == NULL){
        key[0] = 9192;
        return;
    }
    strcpy(key, current_entry->key);
    if(current_entry->next != NULL){
        current_entry = current_entry->next;
    }else{
        for(int i=current_index+1; i<tablesize; i++){
            if(table[i] == NULL){
                continue;
            }
            current_entry = table[i];
            current_index = i;
            return;
        }
        current_entry = NULL;
        current_index = tablesize;
    }

 

สร้างตารางแฮชในภาษาจาวา

การสร้างโปรแกรมประยุกต์ใช้งานตารางแฮชในภาษาจาวาง่ายกว่าภาษา C++ เนื่องจากจาวาได้เตรียมคลาส Hashtable มาไว้ให้เรียบร้อยแล้ว โดยเป็นส่วนหนึ่งของ Java Collection Classes ซึ่งนิยามไว้ในเพ็คเกจ java.util โดยมีคลาสที่เจตนาทำมาให้ใช้งานเกี่ยวกับตารางแฮชสองคลาสคือคลาส Hashtable และคลาส HashMap สองคลาสนี้แตกต่างกันตรงการทำงานที่เกี่ยวข้องกับเธรด (thread)

คลาส Hashtable เป็นคลาสแบบ synchronize ทำให้สามารถใช้งานอินสแตนซ์ของมันได้อย่างปลอดภัยจากหลาย เธรดพร้อมๆ กัน ส่วน HashMap มิได้มีการทำงานแบบ synchronize จึงเหมาะที่จะใช้งานกับเพียงเธรดเดียว โปรเซสหลายๆ โปรเซสสามารถเรียกใช้งานคลาส Hashtable ได้พร้อมๆ กันโดยไม่มีปัญหา ส่วนคลาส HashMap เหมาะสำหรับใช้กับโปรเซสเพียงโปรเซสเดียวเท่านั้น

ต่อไปนี้เราจะมาดูวิธีสร้างโปรแกรมประยุกต์ในเวอร์ชันภาษาจาวาซึ่งมีการทำงานเทียบเท่าเวอร์ชันภาษา C++ ที่คุณได้เรียนวิธีสร้างมาแล้วในหัวข้อก่อนหน้านี้ ตัวโปรแกรมทั้งหมดจะแสดงอยู่ที่ส่วนท้ายของหัวข้อนี้ เราจะเริ่มโดยประกาศอินสแตนซ์ของคลาส Hashtable แล้วกำหนดชื่อของอินสแตนซ์ว่า hashtable

ต่อไปเราประกาศอินสแตนซ์ของคลาส String สองอินสแตนซ์โดยตั้งชื่อว่า key และ value แล้วนำข้อมูลที่เราต้องการนำไปแทรกในตารางแฮชเป็นหน่วยข้อมูลแรกไปใส่ในสองอินสแตนซ์นี้ แต่ก่อนจะแทรกข้อมูลเราต้องตรวจสอบก่อนว่าในตารางแฮชมี key ค่าเดียวกันนี้หรือยัง ซึ่งทำได้โดยเรียก containsKey() ซึ่งเป็นเมธอดสมาชิกของคลาส Hashtable การทำเช่นนี้เทียบได้กับการเรียกใช้ฟังก์ชัน contains() ในโปรแกรมเวอร์ชันภาษา C++

ต่อไปเราจะแสดงคู่ของค่า key/value บนจอภาพก่อนเรียก put() อันเป็นเมธอดสมาชิกของคลาส Hashtable เพื่อทำการแทรกข้อมูลคู่นี้เข้าไปในตารางแฮช เมธอด put() อันเป็นเมธอดสมาชิกของคลาส Hashtable นี้เทียบได้กับฟังก์ชัน put() ที่คุณได้เรียนวิธีสร้างในภาษา C++ ไปแล้ว

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

Adding node – key: 389 value: Mary

Adding node – key: 415 value: Henry

Adding node – key: 999 value: Joe

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

Retrieving a value out of the hashtable:

Found key: 999 value: Henry

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

Size of hashtable before removing nodes: 3

การแสดงหน่วยข้อมูลทำได้โดยเรียก displayEntries() ซึ่งเป็นเมธอดอิสระที่เรานิยามไว้ถัดจากเมธอด main() ของโปรแกรม

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

เราใช้ keySet() อันเป็นเมธอดของคลาส Hashtable ในการสร้าง set ที่บรรจุไว้ด้วย key ที่นำมาจากตารางแฮช เมื่อสร้าง set แล้วเมธอด displayEntries() จะสร้างตัว iterator เมธอด hasNext() และ next() อันเป็นเมธอดสมาชิกของคลาส iterator มีไว้เพื่อให้เราสามารถท่องไปภายใน set ตามค่า key

ขั้นแรกเราเรียกเมธอด hasNext() โดยใช้เป็นเงื่อนไขของลูป while ซึ่งจะตรวจสอบว่ายังมีหน่วยข้อมูลถัดไปใน set หรือไม่ เมธอด hasNext() จะคืนค่าบูลีนเป็นจริงหากมีหน่วยข้อมูลถัดไป มิฉะนั้นก็จะคืนค่าบูลีนมาเป็นเท็จ

หากมีหน่วยข้อมูลถัดไปโปรแกรมจะเรียกเมธอด next() ซึ่งจะขยับไปยังหน่วยข้อมูลถัดไปแล้วส่งค่า key ของหน่วยข้อมูลนั้นมาให้ ค่า key นี้ถูกส่งกลับมาในรูปของออบเจ็กต์ เราจึงต้องแปลงให้เป็น string เสียก่อนแล้วจึงนำไปใส่ใน key string ค่านี้จะถูกส่งไปให้เมธอด get() เพื่อดึงข้อมูลที่ตรงกับ key นี้มา เมธอด get() จะคืนค่ามาเป็นค่าออบเจ็กต์ที่ต้องแปลงให้เป็น string ก่อนจะนำไปใส่ใน value string จากนั้นเรานำค่าใน key string และ value string ออกแสดงบนจอภาพดังนี้

Contents of the hashtable:

Key: 415 value: Henry

Key: 999 value: Joe

Key: 389 value: Mary

ต่อไปโปรแกรมจะลบหน่วยข้อมูลที่มี key เป็น 415 โดยเรียก remove() อันเป็นเมธอดของคลาส Hashtable หลังลบแล้วโปรแกรมจะแสดงขนาดของตารางแฮช และข้อมูลของตารางแฮชบนจอภาพดังนี้

Removing an entry from the hashtable:

Size of hashtable after removing node: 2

Contents of the hashtable:

Key: 999 value: Joe

Key: 389 value: Mary

ซอร์โค้ดสมบูรณ์ในภาษาจาวา

/////////// HashtableDemo.cpp ///////////////////
import java.lang.*;
import java.text.*;
import java.util.*;
public class HashtableExample{
    public static void main(String[] args){
        Hashtable hashtable = new Hashtable();
        String key;
        String value;
        Key = 9341594;
        Value = 93Mary94;
        If (!hashtable.containsKey(key)){
            System.out.println(93Adding node 96 key: 93 + key + hashtable.put(key, value);
        }

        Key = 9341594;
        Value = 93Henry94;
        If (!hashtable.containsKey(key)){
            System.out.println(93Adding node 96 key: 93 + key + hashtable.put(key, value);
        }

        Key = 9399994;
        Value = 93joe94;
        If (!hashtable.containsKey(key)){
            System.out.println(93Adding node 96 key: 93 + key + hashtable.put(key, value);
        }
        System.out.println(93\nRetrieving a value out of the hashtable:94);
        value = (String)Hashtable.get(9341594);
        if(value != null){
            System.out.println(93Found key: 93 + key + 93 value: 93 + value);
        }
        System.out.println(93\nSide of hashtable before removing nodes: 93 + hashtable.size());
        System.out.println(93\nContents of the hashtable: 93);
        displayEntries(hashtable);
        System.out.println(93\nRemoving an entry from the hashtable: 93);
        hashtable.remove(9341594);
        System.out.println(93\nSize of hashtable after removing node: 93 + hashtable after removing node: 93 + hashtable.size());
        System.out.println(93\nContents of the hashtable: 93);
        displayEntries(hashtable);
        }
        private static void displayEntries(Hashtable hashtable){
            Set keys = hashtable.keySet();
            Iterator ii = key.iterator();
            while(ii.hasNext()){
                String key = (String)ii.next();
                String value = (String)hashtable.get(key);
                System.out.println(93key: 93 + key + 93\tvalue: 93 + value);
        }
    }
}

 สรุปท้ายบทความ

การเขียนโปรแกรมตารางแฮชด้วยภาษา C++ และภาษาจาวาไม่ยากมากจนเกินไปหากท่านเข้าใจหลักการทำงานของมัน ในภาษา C# จะง่ายพอๆ กับจาวา เพราะ .NET Framework มีคลาสไลบรารีเกี่ยวกับ Hash มาให้อย่างสมบูรณ์เราจึงสามารถเรียกใช้ได้ง่ายๆ หากท่านต้องการอ่านบทความเทคนิกการเขียนโปรแกรมอื่นๆ ของผู้เขียนกรุณาติดตามในนิตยการ Windows IT Pro ได้ทุกเดือน

Post a comment or leave a trackback: Trackback URL.

ความเห็น

  • Krirk  On สิงหาคม 20, 2007 at 1:53 pm

    ดีครับ เคยได้แต่เป็นผู้ใช้ไม่เคยได้เป็นผู้สร้างกับเค้าซักทีอ่านบทความนี้ทำให้รู้ว่า Hash table เค้าสร้างกันยังไงhttp://Devgod.blogspot.com

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

    ตามจากภาคแรก

ใส่ความเห็น

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: