Untitled

 avatar
unknown
c_cpp
3 years ago
21 kB
4
Indexable
//! linear probing
{

#include <bits/stdc++.h>
    using namespace std;

    // template for generic type
    template <typename K, typename V>

    // Hashnode class
    class HashNode
    {
    public:
        V value;
        K key;

        // Constructor of hashnode
        HashNode(K key, V value)
        {
            this->value = value;
            this->key = key;
        }
    };

    // template for generic type
    template <typename K, typename V>

    // Our own Hashmap class
    class HashMap
    {
        // hash element array
        HashNode<K, V> **arr;
        int capacity;
        // current size
        int size;
        // dummy node
        HashNode<K, V> *dummy;

    public:
        HashMap()
        {
            // Initial capacity of hash array
            capacity = 20;
            size = 0;
            arr = new HashNode<K, V> *[capacity];

            // Initialise all elements of array as NULL
            for (int i = 0; i < capacity; i++)
                arr[i] = NULL;

            // dummy node with value and key -1
            dummy = new HashNode<K, V>(-1, -1);
        }
        // This implements hash function to find index
        // for a key
        int hashCode(K key)
        {
            return key % capacity;
        }

        // Function to add key value pair
        void insertNode(K key, V value)
        {
            HashNode<K, V> *temp = new HashNode<K, V>(key, value);

            // Apply hash function to find index for given key
            int hashIndex = hashCode(key);

            // find next free space
            //! 如果位置已經有人,且不是重複的key
            while (arr[hashIndex] != NULL && arr[hashIndex]->key != key && arr[hashIndex]->key != -1)
            // while (arr[hashIndex] != NULL && arr[hashIndex]->key != key)
            {
                hashIndex++;
                hashIndex %= capacity;
            }

            // if new node to be inserted
            // increase the current size
            if (arr[hashIndex] == NULL || arr[hashIndex]->key == -1)
                size++;
            arr[hashIndex] = temp;
        }

        // Function to delete a key value pair
        V deleteNode(int key)
        {
            // Apply hash function
            // to find index for given key
            int hashIndex = hashCode(key);

            // finding the node with given key
            while (arr[hashIndex] != NULL)
            {
                // if node found
                if (arr[hashIndex]->key == key)
                {
                    HashNode<K, V> *temp = arr[hashIndex];

                    //! Insert dummy node here for further use
                    arr[hashIndex] = dummy;

                    // Reduce size
                    size--;
                    return temp->value;
                }
                hashIndex++;
                hashIndex %= capacity;
            }

            // If not found return null
            return NULL;
        }

        // Function to search the value for a given key
        V get(int key)
        {
            // Apply hash function to find index for given key
            int hashIndex = hashCode(key);
            int counter = 0;

            // finding the node with given key
            while (arr[hashIndex] != NULL)
            { // int counter =0; // BUG!

                if (counter++ > capacity) // to avoid infinite loop
                    return NULL;

                // if node found return its value
                if (arr[hashIndex]->key == key)
                    return arr[hashIndex]->value;
                hashIndex++;
                hashIndex %= capacity;
            }

            // If not found return null
            return NULL;
        }

        // Return current size
        int sizeofMap()
        {
            return size;
        }

        // Return true if size is 0
        bool isEmpty()
        {
            return size == 0;
        }

        // Function to display the stored key value pairs
        void display()
        {
            for (int i = 0; i < capacity; i++)
            {
                if (arr[i] != NULL && arr[i]->key != -1)
                    cout << "key = " << arr[i]->key
                         << " value = "
                         << arr[i]->value << endl;
            }
        }
    };

    // Driver method to test map class
    int main()
    {
        HashMap<int, int> *h = new HashMap<int, int>;
        h->insertNode(1, 1);
        h->insertNode(2, 2);
        h->insertNode(2, 3);
        h->insertNode(1, 3);
        h->insertNode(1, 4);
        h->insertNode(3, 4);
        h->insertNode(7, 4);
        h->insertNode(8, 3);
        h->display();
        cout << h->sizeofMap() << endl;
        cout << h->deleteNode(2) << endl;
        cout << h->sizeofMap() << endl;
        cout << h->isEmpty() << endl;
        cout << h->get(2);

        return 0;
    }
}
//!  quadratic probing-1
{
    // C++ code
#include <iostream>
#include <string>

    using std::cout;
    using std::endl;
    using std::string;

    struct dict
    {
        int key;
        string value;
        dict() : key(0), value(""){};
        dict(int k, string s) : key(k), value(s){};
    };

    class HashOpenAddress
    {
    private:
        int size, count;
        dict *table;

        int QuadraticProbing(int key, int i);

        // TableDoubling()
        // TableShrinking()
        // Rehashing()

    public:
        HashOpenAddress() : size(0), count(0), table(0){};
        HashOpenAddress(int m) : size(m), count(0)
        {
            table = new dict[size];
        }
        void Insert(int key, string value);
        void Delete(int key);
        string Search(int key);
        void Display();
    };

    string HashOpenAddress::Search(int key)
    {

        int i = 0;
        while (i != size)
        {
            int j = QuadraticProbing(key, i);
            if (table[j].key == key)
            {
                return table[j].value;
            }
            else
            {
                i++;
            }
        }
        return "...data not found\n";
    }

    void HashOpenAddress::Delete(int key)
    {

        int i = 0;
        while (i != size)
        {
            int j = QuadraticProbing(key, i);
            if (table[j].key == key)
            {
                table[j].key = 0;
                table[j].value = "";
                count--;
                return;
            }
            else
            {
                i++;
            }
        }
        cout << "...data not found\n";
    }

    void HashOpenAddress::Insert(int key, string value)
    {

        int i = 0;
        while (i != size)
        {
            int j = QuadraticProbing(key, i);
            if (table[j].value == "")
            {
                table[j].key = key;
                table[j].value = value;
                count++;
                return;
            }
            else
            {
                i++;
            }
        }
        cout << "Hash Table Overflow\n";
    }

    int HashOpenAddress::QuadraticProbing(int key, int i)
    {
        // c1 = c2 = 0.5
        return ((int)((key % size) + 0.5 * i + 0.5 * i * i) % size);
    }

    void HashOpenAddress::Display()
    {

        for (int i = 0; i < size; i++)
        {
            cout << "slot#" << i << ": (" << table[i].key
                 << "," << table[i].value << ")" << endl;
        }
        cout << endl;
    }
    int main()
    {

        HashOpenAddress hash(8);   // probing sequence:
        hash.Insert(33, "blue");   // 1,2,4,7,3,0,6,5 -> 1
        hash.Insert(10, "yellow"); // 2,3,5,0,4,1,7,6 -> 2
        hash.Insert(77, "red");    // 5,6,0,3,7,4,2,1 -> 5
        hash.Insert(2, "white");   // 2,3,5,0,4,1,7,6 -> 3
        hash.Display();
        hash.Insert(8, "black");       // 0,1,3,6,2,7,5,4 -> 0
        hash.Insert(47, "gray");       // 7,0,2,5,1,6,4,3 -> 7
        hash.Insert(90, "purple");     // 2,3,5,0,4,1,7,6 -> 4
        hash.Insert(1, "deep purple"); // 4,5,7,2,6,3,1,0 -> 6
        hash.Display();
        hash.Insert(15, "green"); // hash table overflow

        cout << "number#90 is " << hash.Search(90) << "\n\n";

        hash.Delete(90);
        cout << "after deleting (90,purple):\n";
        cout << "number#90 is " << hash.Search(90) << "\n";

        hash.Insert(12, "orange"); // 4,5,7,2,6,3,1,0 -> 4
        hash.Display();

        return 0;
    }
}
//! quardetic probing-2
{

// C++ implementation of
// the Quadratic Probing
#include <bits/stdc++.h>
    using namespace std;

    // Function to print an array
    void printArray(int arr[], int n)
    {
        // Iterating and printing the array
        for (int i = 0; i < n; i++)
        {
            cout << arr[i] << " ";
        }
    }

    // Function to implement the
    // quadratic probing
    void hashing(int table[], int tsize, int arr[], int N)
    {
        // Iterating through the array
        for (int i = 0; i < N; i++)
        {
            // Computing the hash value
            int hv = arr[i] % tsize;

            // Insert in the table if there
            // is no collision
            if (table[hv] == -1)
                table[hv] = arr[i];
            else
            {
                // If there is a collision
                // iterating through all
                // possible quadratic values
                for (int j = 0; j < tsize; j++)
                {
                    // Computing the new hash value
                    int t = (hv + j * j) % tsize;
                    if (table[t] == -1)
                    {
                        // Break the loop after
                        // inserting the value
                        // in the table
                        table[t] = arr[i];
                        break;
                    }
                }
            }
        }
        printArray(table, N);
    }

    // Driver code
    int main()
    {
        int arr[] = {50, 700, 76, 85, 92, 73, 101};
        int N = 7;

        // Size of the hash table
        int L = 7;
        int hash_table[7];

        // Initializing the hash table
        for (int i = 0; i < L; i++)
        {
            hash_table[i] = -1;
        }

        // Function call
        hashing(hash_table, L, arr, N);
        return 0;
    }

    // This code is contributed by gauravrajput1
}

//! chaining
{
// C++ code
#include <iostream>
#include <vector>
#include <string>
#include <math.h> // floor()

    using std::cout;
    using std::endl;
    using std::string;
    using std::vector;

    struct Node
    {
        int key;      // number
        string value; // genre
        Node *next;   // pointer to remember memory address of next node

        Node() : key(0), value(""), next(0){};
        Node(int Key, string Value) : key(Key), value(Value), next(0){};
        Node(Node const &data) : key(data.key), value(data.value), next(data.next){};
    };

    class HashChainNode
    {
    private:
        int size,     // size: size of table, count: number of data
            count;    // count/size = load factor
        Node **table; // pointer to pointer, hash table

        int HashFunction(int key); // Multiplication method
        void TableDoubling();
        void TableShrinking();
        void Rehashing(int size_orig);

    public:
        HashChainNode(){};
        HashChainNode(int m) : size(m), count(0)
        {
            table = new Node *[size]; // allocate the first demension of table
            for (int i = 0; i < size; i++)
            {                 // initialization
                table[i] = 0; // ensure every slot points to NULL
            }
        }
        ~HashChainNode();

        void Insert(Node data); // consider TableDoubling()
        void Delete(int key);   // consider TableShrinking()
        string Search(int key);
        void DisplayTable();
    };

    void HashChainNode::Insert(Node data)
    {

        count++;
        if (count > size)
        {                    // consider load factor
            TableDoubling(); // if n/m > 1, then double the size of table
        }

        int index = HashFunction(data.key); // get index of slot
        Node *newNode = new Node(data);     // create new node to store data

        // push_front()
        if (table[index] == NULL)
        {                           // eg: list: (empty), add4
            table[index] = newNode; // eg: list: 4->NULL
        }
        else
        {                                    // eg: list: 5->9->NULL  , add 4
            Node *next = table[index]->next; //     list: 5->4->9->NULL
            table[index]->next = newNode;
            newNode->next = next;
        }
    }

    void HashChainNode::Delete(int key)
    {

        int index = HashFunction(key); // get index of slot
        Node *current = table[index],  // use two pointer for traversal in list
            *previous = NULL;

        while (current != NULL && current->key != key)
        {
            previous = current;      // traversal in list, 3 cases:
            current = current->next; // 1. data not found
        }                            // 2. data found at first node in list
                                     // 3. data found at other position in list

        if (current == NULL)
        { // eg: list:5->2->9->NULL, want to delete 3
            cout << "data not found.\n\n";
            return;
        }
        else
        {
            if (previous == NULL)
            {                                 // eg: list:5->2->9->NULL, want to delete 5
                table[index] = current->next; // after deleting 5, list:2->9->NULL
            }                                 // current points to 5

            else
            {                                   // eg: list:5->2->9->NULL, want to delete 2
                previous->next = current->next; // after deleting 2, list:5->9->NULL
            }                                   // current points to 2
            delete current;
            current = 0;
        }

        count--;
        if (count < size / 4)
        {                     // consider load factor
            TableShrinking(); // if n/m < 4, then shrink the table
        }
    }

    string HashChainNode::Search(int key)
    {

        int index = HashFunction(key); // get index of slot
        Node *current = table[index];  // current points to the first node in list

        while (current != NULL)
        { // traversal in list
            if (current->key == key)
            {
                return current->value;
            }
            current = current->next;
        }
        return "...\nno such data";
    }

    int HashChainNode::HashFunction(int key)
    {
        // Multiplication method
        double A = 0.6180339887,
               frac = key * A - floor(key * A);
        return floor(this->size * frac);
    }

    void HashChainNode::TableDoubling()
    {

        int size_orig = size; // size_orig represents the original size of table
        size *= 2;            // double the size of table
        Rehashing(size_orig);
        ; // create new table with new larger size
    }

    void HashChainNode::TableShrinking()
    {

        int size_orig = size; // size_orig represents the original size of table
        size /= 2;            // shrink the size of table
        Rehashing(size_orig); // create new table with new smaller size
    }

    void HashChainNode::Rehashing(int size_orig)
    {

        Node **newtable = new Node *[size]; // allocate memory for new table
        for (int i = 0; i < size; i++)
        {                    // initializetion
            newtable[i] = 0; // ensure every node in slot points to NULL
        }

        for (int i = 0; i < size_orig; i++)
        { // visit every node in the original table

            Node *curr_orig = table[i], // curr_orig: current node in original table
                *prev_orig = NULL;      // prev_orig: following curr_orig

            while (curr_orig != NULL)
            { // traversal in list of each slot in original table

                prev_orig = curr_orig->next; // curr_orig will be directly move to new table
                                             // need prev_orig to keep pointer in original table

                int index = HashFunction(curr_orig->key); // get index of slot in new table

                // push_front(), do not allocate new memory space for data
                // directly move node in original table to new table
                if (newtable[index] == NULL)
                { // means newtable[index] is empty
                    newtable[index] = curr_orig;
                    newtable[index]->next = 0; // equivalent to curr_orig->next = 0;
                }
                // if there is no initialization for newtable, segmentation faults might happen
                // because newtable[index] might not point to NULL
                // but newtable[index] is empty
                else
                {                                       // if newtable[index] is not empty
                    Node *next = newtable[index]->next; // push_front()
                    newtable[index]->next = curr_orig;
                    curr_orig->next = next;
                }
                curr_orig = prev_orig; // visit the next node in list in original table
            }
        }
        delete[] table;         // release memory of original table
        this->table = newtable; // point table of object to new table
    }

    HashChainNode::~HashChainNode()
    {

        for (int i = 0; i < size; i++)
        {                             // visit every node in table
                                      // and release the memory of each node
            Node *current = table[i]; // point *current to first node in list
            while (current != NULL)
            { // traversal in list
                Node *previous = current;
                current = current->next;
                delete previous;
                previous = 0;
            }
        }
        delete[] table;
    }

    void HashChainNode::DisplayTable()
    {

        for (int i = 0; i < size; i++)
        { // visit every node in table
            cout << "#slot#" << i << ": ";
            Node *current = table[i];
            while (current != NULL)
            {
                cout << "(" << current->key << "," << current->value << ") ";
                current = current->next;
            }
            cout << endl;
        }
        cout << endl;
    }

    int main()
    {

        HashChainNode hash(2);

        hash.Insert(Node(12, "post rock"));
        hash.Insert(Node(592, "shoegaze"));
        cout << "After inserting key(12),key(592):\n";
        hash.DisplayTable();
        hash.Insert(Node(6594, "blues")); // evoke TableDoubling()
        cout << "After inserting key(6594), evoke TableDoubling():\n";
        hash.DisplayTable();
        hash.Insert(Node(7, "folk"));
        cout << "After inserting key(7):\n";
        hash.DisplayTable();
        hash.Insert(Node(123596, "hiphop")); // evoke TableDoubling()
        cout << "After inserting key(123596), evoke TableDoubling():\n";
        hash.DisplayTable();
        hash.Insert(Node(93, "soul"));
        hash.Insert(Node(2288, "indie"));
        hash.Insert(Node(793, "jazz"));
        cout << "After inserting key(93),key(2288),key(793):\n";
        hash.DisplayTable();
        hash.Insert(Node(8491, "electro")); // evoke TableDoubling()
        cout << "After inserting key(8491), evoke TableDoubling():\n";
        hash.DisplayTable();
        hash.Insert(Node(323359, "pop"));
        cout << "After inserting key(323359):\n";
        hash.DisplayTable();

        cout << "Searching: genre(8491) is " << hash.Search(8491) << ".\n\n";
        cout << "Searching: genre(7) is " << hash.Search(7) << ".\n\n";

        hash.Delete(7);
        cout << "After deleting key(7):\n";
        cout << "Searching: genre(7) is " << hash.Search(7) << ".\n\n";

        hash.Delete(592);
        cout << "After deleting key(592):\n";
        hash.DisplayTable();

        cout << "Want to  delete key(592) again:\n";
        hash.Delete(592);

        hash.Delete(123596);
        hash.Delete(323359);
        hash.Delete(793);
        hash.Delete(93);
        cout << "After deleting key(123596),key(323359),key(793),key(93):\n";
        hash.DisplayTable();

        hash.Delete(6594); // evoke TableShrinking()
        cout << "After deleting key(6594), evoke TableShrinking():\n";
        hash.DisplayTable();

        return 0;
    }
}
Editor is loading...