#include<iostream>
using namespace std;


/* A hash table is an extension of an array. The hash table is an extension of an array. We use a "key" or "keyword" to identify an object. The mapping method that converts a "key" or "keyword" to an array subscript is called a "hash function", and the value computed by the hash function is called a "hash value". 1. The hash value is a non-negative integer value. If key1 = key2 then hash(key1) = hash(key2) ③if key1≠key2 then hash(key2)≠hash(key2) It is practically impossible to find a hash function that satisfies ③. A new algorithm is developed to improve the resolution of hash conflicts. On the other hand, a new algorithm is developed to improve the resolution of hash conflicts. When we insert data into the hash table, if the hash function hashes the data and the storage space is already occupied, we start at the current location and look for free space until we find it. Ps: When the linear detection method is used to resolve conflicts, the deletion operation cannot set the deleted element as empty singly, otherwise the search operation may fail. Quadratic detection and double hashing 2. Chaining */


class HashNode {
public:
	int value;
	int key;
	HashNode(int key, int value) : value(value), key(key) {}
};


class HashMap {
	HashNode** arr;
	int capacity;
	int size;
	HashNode* dummy;  // Virtual node represents the deleted node

public:
	HashMap() {
		capacity = 20;
		size = 0;
		arr = new HashNode * [capacity];
		for (int i = 0; i < capacity; i++) {
			arr[i] = nullptr;
		}
		dummy = new HashNode(- 1.- 1);
	}

	~HashMap() {
		for (int i = 0; i < capacity; i++) {
			if(arr[i] ! =nullptr) {
				deletearr[i]; }}delete[] arr;
	}

	int hashCode(int key) {
		return key % capacity;
	}

	void insertNode(int key, int value) {
		HashNode* temp = new HashNode(key, value);
		int hashIndex = hashCode(key);
		// Linear method to solve collisions
		while(arr[hashIndex] ! =nullptr&& arr[hashIndex]->key ! = key && arr[hashIndex]->key ! =- 1) {
			// An infinite loop is created if the capacity is full
			hashIndex++;
			hashIndex %= capacity;
		}

		// Delete the element with the same key value
		if(arr[hashIndex] ! =nullptr) {
			delete arr[hashIndex];
			size--;
		}

		arr[hashIndex] = temp;
		size++;
	}

	
	int deleteNode(int key) {
		int hashIndex = hashCode(key);
		while(arr[hashIndex] ! =nullptr&& arr[hashIndex]->key ! = key) { hashIndex++; hashIndex %= capacity; }if (arr[hashIndex] == nullptr) {
			return - 1;
		}

		int temp = arr[hashIndex]->value;
		delete arr[hashIndex];
		arr[hashIndex] = dummy;
		size--;
		return temp;


		return - 1;

	}

	int search(int key) {
		int hashIndex = hashCode(key);
		while(arr[hashIndex] ! =nullptr&& arr[hashIndex]->key ! = key) { hashIndex++; hashIndex %= capacity; }if (arr[hashIndex] == nullptr) {
			return - 1;
		}

		return arr[hashIndex]->value;
	}

	int sizeOfMap(a) {
		return size;
	}

	bool isEmpty(a) {
		return size == 0;
	}

	void display(a) {
		for (int i = 0; i < capacity; i++) {
			if(arr[i] ! =NULL) {
				cout << "key = " << arr[i]->key
					<< " value = " << arr[i]->value << endl; }}}};int main(a) {
	HashMap* h = new HashMap();
	cout << h->isEmpty() << endl;
	h->insertNode(1.1);
	h->insertNode(2.2);
	h->insertNode(2.3);
	h->insertNode(5.8);
	h->insertNode(6.9);
	h->display();
	cout << h->isEmpty() << endl;
	cout << h->sizeOfMap() << endl;
	cout << h->search(2) < <endl;
	h->display();
	cout << h->deleteNode(7) < <endl;
	cout << h->deleteNode(5) < <endl;
	h->display();
	delete h;
	return 0;
}
Copy the code

Ps: I am C++ small white, temporarily unable to implement generic hashtable, here to use int as key and value, secondly, the code passed the basic test, but whether there is memory leakage is not too clear, check online implementation found that there are problems, but difficult to correct.

Main reference

Implementing own Hash Table with Open Addressing Linear Probing in C++ (Implementing own Hash Table with Open Addressing Linear Probing in C++) I don’t know if it is my own understanding or there is a real problem)

C++ Program to Implement Hash Tables C++ Program to Implement Hash Tables C++ Program to Implement Hash Tables