Data structure - Hash table

รวมโค้ด Hash table

• Close hashing (Open address) - Linear probing

#include <iostream>

using namespace std;

#define HASH_SIZE 10

// ข้อมูล
class Data
{
public:
    long std_id;
    string val;
};

// Hash table: get, put, remove
class Hash
{
private:
    Data *arr[HASH_SIZE];
    bool is_removed[HASH_SIZE];
    int hash(long std_id)
    {
        return std_id % HASH_SIZE;
    }

public:
    // Contructor
    Hash()
    {
        for (int i = 0; i < HASH_SIZE; i++)
        {
            arr[i] = NULL;
            is_removed[i] = false;
        }
    }
    void put(long std_id, string val)
    {
        Data *new_data = new Data();
        new_data->std_id = std_id;
        new_data->val = val;

        // real whang
        if (arr[hash(std_id)] == NULL)
        {
            arr[hash(std_id)] = new_data;
            is_removed[hash(std_id)] = false;
            return;
        }

        // try to find empty spot
        int i = 1;
        while (arr[hash(std_id) + i] != NULL)
        {
            i += 1;
        }

        arr[hash(std_id) + i] = new_data;
        is_removed[hash(std_id) + i] = false;
    }
    string get(long std_id)
    {
        if (arr[hash(std_id)] == NULL && is_removed[hash(std_id)] == false)
            return "-";

        // First found
        if (arr[hash(std_id)] != NULL && arr[hash(std_id)]->std_id == std_id)
        {
            return arr[hash(std_id)]->val;
        }

        // try to find empty spot
        int i = 1;
        while (arr[hash(std_id) + i] != NULL || is_removed[hash(std_id) + i] == true)
        {
            if (arr[hash(std_id) + i]->std_id == std_id)
                break;

            i += 1;
        }

        if (arr[hash(std_id) + i] == NULL)
            return "-";

        return arr[hash(std_id) + i]->val;
    }
    void remove(long std_id)
    {
        if (arr[hash(std_id)] == NULL && is_removed[hash(std_id)] == false)
            return;

        if (arr[hash(std_id)] != NULL && arr[hash(std_id)]->std_id == std_id)
        {
            arr[hash(std_id)] = NULL;
            is_removed[hash(std_id)] = true;
            return;
        }

        int i = 1;
        while (arr[hash(std_id) + i] != NULL || is_removed[hash(std_id) + i] == true)
        {
            if (arr[hash(std_id) + i] != NULL && arr[hash(std_id) + i]->std_id == std_id)
                break;

            i += 1;
        }

        if (arr[hash(std_id) + i] == NULL)
            return;

        arr[hash(std_id) + i] = NULL;
        is_removed[hash(std_id) + i] = true;
    }
    void display_all()
    {
        for (int i = 0; i < HASH_SIZE; i++)
        {
            if (arr[i] == NULL)
            {
                cout << "(-1,-)" << endl;
                continue;
            }

            cout << "(" << arr[i]->std_id << "," << arr[i]->val << ")" << endl;
        }
    }
};

int main()
{
    Hash hash;

    char cmd;
    cin >> cmd;

    long std_id;
    string val;

    while (cmd != 'e')
    {
        if (cmd == 'a')
        {
            cin >> std_id >> val;

            hash.put(std_id, val);
        }
        else if (cmd == 's')
        {
            cin >> std_id;

            cout << hash.get(std_id) << endl;
        }
        else if (cmd == 'r')
        {
            cin >> std_id;

            hash.remove(std_id);
        }
        else if (cmd == 'd')
        {
            hash.display_all();
        }

        cin >> cmd;
    }
    return 0;
}

• Open hashing (Close address / Seperate chaining)

#include <iostream>

using namespace std;

#define HASH_SIZE 10

class Node
{
public:
    long std_id;
    string name;
    Node *next;
    Node()
    {
        next = NULL;
    }
};

class Hash
{
private:
    Node *arr[HASH_SIZE];
    int hash(long std_id)
    {
        return std_id % HASH_SIZE;
    }

public:
    Hash()
    {
        for (int i = 0; i < HASH_SIZE; i++)
        {
            arr[i] = NULL;
        }
    }
    void display_all()
    {
        for (int i = 0; i < HASH_SIZE; i++)
        {
            if (arr[i] == NULL)
            {
                cout << "(-1 , -)" << endl;
                continue;
            }

            Node *tmp = arr[i];
            while (tmp->next != NULL)
            {
                cout << "(" << tmp->std_id << " , " << tmp->name << ") ";
                tmp = tmp->next;
            }

            cout << "(" << tmp->std_id << " , " << tmp->name << ")" << endl;
        }
    }
    void put(long std_id, string val)
    {
        Node *new_node = new Node();
        new_node->std_id = std_id;
        new_node->name = val;

        if (arr[hash(std_id)] == NULL)
        {
            arr[hash(std_id)] = new_node;
            return;
        }

        Node *tmp = arr[hash(std_id)];
        while (tmp->next != NULL)
        {
            tmp = tmp->next;
        }

        tmp->next = new_node;
    }
    string get(long std_id)
    {
        if (arr[hash(std_id)] == NULL)
            return "-";
        if (arr[hash(std_id)]->std_id == std_id)
            return arr[hash(std_id)]->name;

        Node *tmp = arr[hash(std_id)];
        while (tmp != NULL)
        {
            if (tmp->std_id == std_id)
                break;
            tmp = tmp->next;
        }

        if (tmp == NULL)
            return "-";

        return tmp->name;
    }

    void remove(long std_id)
    {
        if (arr[hash(std_id)] == NULL)
            return;

        if (arr[hash(std_id)]->std_id == std_id)
        {
            arr[hash(std_id)] = arr[hash(std_id)]->next;
            return;
        }

        Node *tmp = arr[hash(std_id)], *before_tmp = NULL;
        while (tmp != NULL)
        {
            if (tmp->std_id == std_id)
                break;
            before_tmp = tmp;
            tmp = tmp->next;
        }

        if (tmp == NULL)
        {
            return;
        }

        before_tmp->next = tmp->next;
    }
};

int main()
{
    Hash hash;
    char cmd;
    cin >> cmd;

    long std_id;
    string name;

    while (cmd != 'e')
    {
        if (cmd == 'a')
        {
            cin >> std_id >> name;

            hash.put(std_id, name);
        }
        else if (cmd == 's')
        {
            cin >> std_id;

            cout << hash.get(std_id) << endl;
        }
        else if (cmd == 'r')
        {
            cin >> std_id;

            hash.remove(std_id);
        }
        else if (cmd == 'd')
        {
            hash.display_all();
        }

        cin >> cmd;
    }
    return 0;
}