โปรแกรม C++ สำหรับ Hashing แบบ Chaining

Hashing (แฮชชิง) เป็นวิธีการจับคู่ข้อมูลความยาวเท่าไหร่ก็ตามให้เป็นคีย์ขนาดคงที่ Hashing ทำงานแบบคีย์-ค่า (key-value pairs)

Hash Function (ฟังก์ชันแฮช) คือฟังก์ชันที่ทำการจับคู่ใน Hash Map ข้อมูลที่ป้อนเข้าให้ Hash Function อาจได้คีย์แฮชเหมือนกัน ในกรณีนี้องค์ประกอบอาจทับซ้อนกัน เพื่อป้องกันการทับซ้อนขององค์ประกอบที่มีคีย์แฮชเหมือนกัน แนวคิด Chaining (เชนิ่ง) จึงถูกนำมาใช้

การสร้าง Hash Map

เพื่อสร้าง Hash Map เราต้องการ Hash Function ที่จะกำหนดค่าดัชนีขององค์ประกอบข้อมูล

เรามี Hash Table ที่มี n buckets เพื่อแทรกโหนดลงใน hash table เราได้รับ Hash Function ว่า:

hashIndex = key % noOfBuckets

ตอนนี้เราจะใช้ Hash Function นี้และคำนวณ hashIndex ของทุกค่าที่แทรกเข้า hashmap

• แทรกองค์ประกอบและคำนวณ hashIndex ของคีย์ที่กำหนด แล้วแทรกโหนดใหม่ไปที่ท้ายของลิสต์

• เพื่อลบโหนด เราจะคำนวณ hash index และใน bucket ที่ตรงกับ hash index เราจะค้นหาองค์ประกอบใน bucket และลบมัน

ตัวอย่าง

#include <iostream>
#include <list>
using namespace std;

class Hash {
    int BUCKET;
    list<int> *table;
public:
    Hash(int V);
    void insertItem(int x);
    void deleteItem(int key);
    int hashFunction(int x) {
        return (x % BUCKET);
    }
    void displayHash();
};

Hash::Hash(int b) {
    this->BUCKET = b;
    table = new list<int>[BUCKET];
}

void Hash::insertItem(int key) {
    int index = hashFunction(key);
    table[index].push_back(key);
}

void Hash::deleteItem(int key) {
    int index = hashFunction(key);
    list<int>::iterator i;
    for (i = table[index].begin(); i != table[index].end(); i++) {
        if (*i == key)
            break;
    }
    if (i != table[index].end())
        table[index].erase(i);
}

void Hash::displayHash() {
    for (int i = 0; i < BUCKET; i++) {
        cout << i;
        for (auto x : table[i])
            cout << " --> " << x;
        cout << endl;
    }
}

int main() {
    int a[] = {5, 12, 67, 9, 16};
    int n = 5;
    Hash h(7);
    for (int i = 0; i < n; i++)
        h.insertItem(a[i]);
    h.deleteItem(12);
    h.displayHash();
    return 0;
}

ผลลัพธ์

0
1
2 --> 9 --> 16
3
4 --> 67
5 --> 5
6