Untitled
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...