1, Forerunner

1. Knowledge to be mastered

Implementation of Hash / Hash table through open address method

2. Topic information

2.1 topic source: PTA / puzzle A
2.2 Title address: 7-17 Hashing

2, Analysis of problem solving ideas

1. Understanding of the topic

Insert the entered number into the Hash table and print the inserted position

1.1 input data

4 4  //The size of the Hash table given by the user (if it is not a prime number, it needs to be adjusted) and the number of numbers to be entered
10 6 4 15 //Specific figures

1.2 output data

0 1 4 - //Print the insertion position. If it cannot be inserted, print '-'
......

2. Train of thought analysis

2.1 the idea is the same as that explained by Mr. He: first create a Hash table (development address), and then store the entered data in the Hash table. If there is a conflict, solve it through the forward square detection method. Such benefits are: the knowledge learned will be used for practical coding; The disadvantage is that the amount of code is too large and takes more time
2.2 simple method: without creating a Hash table, you can use an array. The initial value of the array element is 0. Inserting an element is equivalent to setting the element value of the corresponding array subscript to 1

3, Concrete implementation

1. Detours and bug s

Prime number refers to the natural number with no other factors except 1 and itself in the natural number greater than 1: maybe I ate brain fragments today and expelled 2 from the prime number, resulting in the failure of the minimum test point to pass normally

2. Code framework

2.1 adopted data structure

Construct Hash table / Hash table through open address method

typedef int ElementType;
typedef int Position;
typedef enum {Occupied,Empty,Deleted} PositionStatus; //As far as this topic is concerned, the Deleted status is useless because it does not involve deletion

struct HashTableCell //A cell in a Hash table
{
	ElementType Data;
	PositionStatus Status;
};
typedef HashTableCell Cell;


struct HashTableStructure //Hash table
{
	int TableSize;
	Cell *CellArray; //An array that holds hash cell data
};
typedef HashTableStructure *HashTable;

2.2 main framework of procedure

               Program pseudo code description
int main()
{
	1.establish Hash Table (open address)
	2.Insert the entered number into Hash And print the inserted position in the table
}

2.3 branching functions

2.3.1 CreateHashTable() creates a Hash table. Note: the size of the Hash table has been determined before creation, so it does not need to be processed during creation

HashTable CreateHashTable(int TableSize)
{
	HashTable H;
	H = (HashTable)malloc(sizeof(struct HashTableStructure));
	//H->TableSize = NextPrime(TableSize);
	H->TableSize = TableSize;

	H->CellArray = (Cell*)malloc(sizeof(Cell) * H->TableSize);

	for (int i = 0; i < H->TableSize; i++)
		H->CellArray[i].Status = Empty;

	return H;
}

2.3.2 Find() searches for elements in the Hash table, and the Find function is called by the Insert function. Note two points here: I. We use the forward bisection detection method to solve conflicts. Some numbers may not be inserted into the Hash table, so we need to set an exit condition. If the number of conflicts exceeds the size of the table, the insertion fails II The purpose of searching is to Find the vacancy, and there is no need to Find the corresponding element

		if (ConflictNumber > H->TableSize)
			return Null;	

Position Find(HashTable H, ElementType Key)
{
	Position CurrentPostion, NewPosition;
	int ConflictNumber=0;
	
	NewPosition = CurrentPostion = Hash(Key, H->TableSize);

	//The cell in the current position is not empty and is not the element to be found, triggering a conflict
	//while (H->CellArray[NewPosition].Status != Empty && H->CellArray[NewPosition].Data != Key)
	while (H->CellArray[NewPosition].Status != Empty )
	{
		ConflictNumber++;
		NewPosition = CurrentPostion + ConflictNumber * ConflictNumber;
		
		if (NewPosition > H->TableSize)
			NewPosition = NewPosition % H->TableSize;

		if (ConflictNumber > H->TableSize)
			return Null;	
	}
	return NewPosition;
}

2.3.3 Insert() inserts an element into the Hash table: insert it when an empty space is found and return the specific location of the insertion; otherwise, return - 1

int Insert(HashTable H, ElementType Key)
{
	Position Pos = Find(H, Key);

	if (Pos == Null)
		return Null;
	else
	{
		H->CellArray[Pos].Status = Occupied;
		H->CellArray[Pos].Data = Key;

		return Pos;
	}
}

3. Complete AC code

If you have any suggestions or questions, please leave a message

#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;

#define MAX 100000
#define Null -1

typedef int ElementType;
typedef int Position;
typedef enum {Occupied,Empty,Deleted} PositionStatus;

struct HashTableCell
{
	ElementType Data;
	PositionStatus Status;
};
typedef HashTableCell Cell;


struct HashTableStructure
{
	int TableSize;
	Cell *CellArray; //An array that holds hash cell data
};
typedef HashTableStructure *HashTable;

HashTable CreateHashTable(int TableSize);
Position Find(HashTable H, ElementType Key);
int Hash(int Key, int TableSize);
int Insert(HashTable H, ElementType Key);
int NextPrime(int n);
bool JudgePrime(int n);


int main()
{
	int Size, Number,Data,Pos;
	cin >> Size >> Number;

	if (!JudgePrime(Size))
		Size = NextPrime(Size);

	HashTable H;
	H = CreateHashTable(Size);


	cin >> Data;
	Pos = Insert(H, Data);

	if (Pos == Null)
		cout << '-';
	else
		cout << Pos;

	for (int i = 1; i < Number; i++)
	{
		cin >> Data;
		Pos = Insert(H, Data);

		if (Pos == Null)
			cout <<" -";
		else
			cout<<' '<< Pos;
	}


	return 0;
}

int Insert(HashTable H, ElementType Key)
{
	Position Pos = Find(H, Key);

	if (Pos == Null)
		return Null;
	else
	{
		H->CellArray[Pos].Status = Occupied;
		H->CellArray[Pos].Data = Key;

		return Pos;
	}

	/*if (H->CellArray[Pos].Status != Occupied)
	{
		H->CellArray[Pos].Status = Occupied;
		H->CellArray[Pos].Data = Key;

		cout << Pos << ' ';

		return true;
	}
	else
		return false;*/
}

Position Find(HashTable H, ElementType Key)
{
	Position CurrentPostion, NewPosition;
	int ConflictNumber=0;
	
	NewPosition = CurrentPostion = Hash(Key, H->TableSize);

	//The cell in the current position is not empty and is not the element to be found, triggering a conflict
	//while (H->CellArray[NewPosition].Status != Empty && H->CellArray[NewPosition].Data != Key)
	while (H->CellArray[NewPosition].Status != Empty )
	{
		ConflictNumber++;
		NewPosition = CurrentPostion + ConflictNumber * ConflictNumber;
		
		if (NewPosition > H->TableSize)
			NewPosition = NewPosition % H->TableSize;

		if (ConflictNumber > H->TableSize)
			return Null;	
	}
	return NewPosition;
}

HashTable CreateHashTable(int TableSize)
{
	HashTable H;
	H = (HashTable)malloc(sizeof(struct HashTableStructure));
	//H->TableSize = NextPrime(TableSize);
	H->TableSize = TableSize;

	H->CellArray = (Cell*)malloc(sizeof(Cell) * H->TableSize);

	for (int i = 0; i < H->TableSize; i++)
		H->CellArray[i].Status = Empty;

	return H;
}

int Hash(int Key, int TableSize)
{
	return Key % TableSize;
}

bool JudgePrime(int n)
{
	if (n == 1)
		return false;

	for (int i = 2; i * i <= n; i++)
	{
		if (!(n % i))
			return false;
	}
	return true;
}

int NextPrime(int n)
{
	if (n == 1) return 2;
	
	int i, next;

	next = (n % 2) ? n + 2:n+1; //next is an odd number greater than n

	while (next < MAX)
	{
		for (i = 3; i * i <= next; i += 2)
			if (next % i == 0)
				break;

		if (i * i > next)
			return next;
		else
			next += 2;
	}
	return next;
}

4, Reference

Chen Yue and he Qinming from Zhejiang University gave lectures on data structure