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