1. Hash table
Note 1
Note 2
Hash table (also known as hash table) is a data structure that is accessed directly according to the key value. That is, it accesses records by mapping key values to a location in the table to speed up the search. This mapping function is called hash function, and the array storing records is called hash table.
Hash table hashtable(key, value) is to convert the Key into an integer number through a fixed algorithm function, that is, the so-called hash function, and then remainder the length of the array with the number. The remainder result is regarded as the subscript of the array, and the value is stored in the array space with the number as the subscript. reference resources
1. Using chain address method
A hash function can convert keys into array indexes. The second step of the hash algorithm is collision processing, that is, when the hash values of two or more keys are the same. Zipper method is to point each element in the array of size m to a linked list. Each node in the linked list stores the key value pair whose hash value is the index of the element. The idea of this method is to select a large enough m to make all linked lists as short as possible to ensure efficient search, otherwise it is easy to degenerate into a single linked list. As shown in the figure below, M=5:
reference resources

// Hash function cpp: defines the entry point for the console application.
//

#include "stdafx.h"
#include<memory.h>
#include<iostream>
using namespace std;

class HashTable
{
public:
	typedef struct _HashNode//Hash node
	{
		int key;//value
		_HashNode* pNext;//Value pointing to the next node
	}HashNode;

	typedef struct _Hash
	{
		_HashNode* pElement;//Storage space of data elements
	}_Hash;

public:
	void InitHashTable(int len);//Initialize hash table
	int Hash(int key);//DP Hash 
	void InsertData(int key);//insert data
	HashNode* SearchTable(int key, int *addr);//Find data
	void CreateTable(int array[], int n);//Create hash table
	void ShowHash();//Display data

private:
	_Hash m_hashTable;//Hashtable 
	int m_tableLength;//Hash table length

};

int _tmain(int argc, _TCHAR* argv[])
{
	HashTable hash;
	hash.InitHashTable(7);

	int arr[] = { 19, 1, 23, 14, 55, 68, 11, 82, 36 };
	hash.CreateTable(arr, 9);

	hash.ShowHash();

	int addr = 0;
	HashTable::_HashNode* pNode = hash.SearchTable(19, &addr);
	cout << "The values found are:" << pNode->key <<endl<< "The address is:" << addr << endl;

	return 0;
}

void HashTable::InitHashTable(int len)
{
	m_tableLength = len;
	m_hashTable.pElement = new _HashNode[len];//Open up space for storing array elements
	memset(m_hashTable.pElement, 0x00, sizeof(_HashNode)*len);
}

int HashTable::Hash(int key)//Hash value
{
	return key%m_tableLength;//The table length remainder of array elements is the hash value
}

void HashTable::InsertData(int key)
{
	int addr = Hash(key);//Get hash value
	if (m_hashTable.pElement[addr].key==0)//Determine whether there is hash conflict
	{
		m_hashTable.pElement[addr].key = key;//Place the value to be inserted in the corresponding position
	}
	else
	{
		_HashNode* pNew = new _HashNode;//Create a new node
		pNew->key = key;//Assign value to new node
		pNew->pNext = m_hashTable.pElement[addr].pNext;//Set the next position pointed by the new node to null
		m_hashTable.pElement[addr].pNext = pNew;//The new node is placed behind the previous point
	}

}

void HashTable::CreateTable(int array[], int n)//Insert the data of the array into the hash table
{
	for (int i = 0; i < n; i++)
	{
		InsertData(array[i]);
	}
}

void HashTable::ShowHash()
{
	for (int i = 0; i < m_tableLength; i++)
	{
		cout << "The first" << i << ":";
		_HashNode* pNode = &(m_hashTable.pElement[i]);
		while (pNode)
		{
			cout << pNode->key << " ";
			pNode = pNode->pNext;
		}
		cout << endl;
	}
}

HashTable::HashNode* HashTable::SearchTable(int key, int* addr)
{
	*addr = Hash(key);

	_HashNode* pNode = &(m_hashTable.pElement[*addr]);

	while (pNode)
	{
		if (pNode->key==key)
		{
			return pNode;
		}
		pNode = pNode->pNext;//Continue to find
	}
	return pNode;

}

2. Using open address method
The basic idea of this method is: when an address conflict occurs, continue to detect other storage units in the hash table according to some method until an empty location is found. This process can be described by the following formula:
H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,...... ， k ( k ≤ m – 1))
Where: H (key) is the direct hash address of the keyword key, m is the length of the hash table, and di is the address increment during each re detection.
When using this method, first calculate the direct hash address H (key) of the element. If the storage unit has been occupied by other elements, continue to check the storage unit with address H (key) + D 2. Repeat this until a storage unit is found to be empty, and store the data element with key word as key in the unit.
Increment d can be taken in different ways, and it can be called differently according to its method:
(1) d i = 1, 2, 3,... Linear detection re hashing;
(2) d i = 1 ^ 2, - 1 ^ 2, 2 ^ 2, - 2 ^ 2, k^2, - k^2... Secondary detection and hashing;
(3) d i = pseudo-random re hashing of pseudo-random sequence;
reference resources

#include"stdafx.h"
#include<iostream>
#include<memory.h>
using namespace std;

class HashTable
{
public:
	typedef struct _Hash
	{
		int *pElement;//Store array
		int nCount;//Number of array elements
	}_Hash;
	void InitHashTable(int len);//Initialize array
	int Hash(int key);//Calculate function value
	void InsertData(int key);
	void CreatHashTable(int array[], int n);
	bool SearchHash(int key, int *addr);
	void ShowHash();
private:
	_Hash hashTable;
	int TableLen;
};

int _tmain(int argc, _TCHAR* argv[])
{
	HashTable hashK;
	hashK.InitHashTable(17);

	int arr[] = { 47, 7, 29, 11, 16, 92, 22, 8, 3 };
	hashK.CreatHashTable(arr, 9);

	hashK.ShowHash();

	int addr = 0;
	bool ret = hashK.SearchHash(29, &addr);
	cout << "Search results : " << ret << "\t Address is : " << addr << endl;

	return 0;
}

void HashTable::InitHashTable(int len)
{
	TableLen = len;
	hashTable.pElement = new int[len];
	hashTable.nCount = 0;

	memset(hashTable.pElement, 0x00, sizeof(int)*len);
}

int HashTable::Hash(int key)
{
	return key%TableLen;
}

void HashTable::InsertData(int key)
{
	if (hashTable.nCount>=TableLen)
	{
		return;
	}

	int addr = Hash(key);

	while (hashTable.pElement[addr]!=0)//In case of conflict, the remainder will be + 1 before continuing processing
	{
		addr = (addr + 1) % TableLen;
	}

	hashTable.pElement[addr] = key;
	hashTable.nCount++;
}

void HashTable::CreatHashTable(int array[], int n)
{
	for (int i = 0; i < n; i++)
	{
		InsertData(array[i]);
	}
}

bool HashTable::SearchHash(int key, int *addr)
{
	*addr = Hash(key);

	int nCount = 0;
	while (hashTable.pElement[*addr]!=0)
	{
		*addr = (*addr + 1) % TableLen;

		if (++nCount>TableLen)
		{
			return false;
		}
	}
	return true;
}

void HashTable::ShowHash()
{
	for (int i = 0; i < TableLen; i++)
	{
		cout << "The first" << i <<" "<< hashTable.pElement[i] << endl;
	}
}