hash address

• The hash address is a logical address, not an actual address. The hash address is obtained through the hash function

hash function

• The hash function is determined by yourself. You can choose any function. Suppose you use the array to store the hash data, use the subscript to describe the position in the array, and construct the hash address through the data. The address is the subscript of the array

• The maximum capacity of the hash structure in the figure is 7

• Generally, the hash constructor is used to connect the data with the subscript

• The hash address is obtained by the remainder method: the hash address of the data = = Data% P (maximum capacity), and the hash address is obtained through% 7

• Through the hash constructor, get the hash address 88% 7 = = 4, and put the remaining 4 in the position where the index of the array is 4 (put the current element in the position of the capacity with the current hash address as the index)

• Direct addressing method: the number of data, the constructed hash address, the element is 88, the constructed hash address is 88, the data is the address, and the address is the data. The minimum required array length of the elements in the figure is 89, which wastes space

• Square middle method: square the original data and take the middle part

• Folding method: convert the string into ASCII code, which is a large number. Fold the number

Hash Collisions

• The address obtained by 1 hash function may be duplicate (the same element)

Handling hash conflicts

• Open address method: if you want to store element 4 with hash conflict in the hash structure, you need to find the empty position behind the array. Assuming that the position with subscript 6 of the array is empty, put 4 in this position. Open address method is to store elements with hash conflict in other empty positions

• Adjacency list method: the adjacency list method is used for graph storage. The following elements are not opened. Create a linked list with the current position (where there are conflicts), and put the elements with conflicts in the current linked list -- > store the elements with the current element as the header of the linked list

Build data type

• If you want to process string data, you need to construct a key to solve the address of the hash structure

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct pair 
{
	int key;			
	char element[20];	//data type
}DATA,*LPDATA;

Creation of hash table

typedef struct hashTable 
{
	LPDATA* table;	   //The secondary pointer is easy to initialize and judge whether the current hash address has conflict and null
	int divisor;       //H (key) = key% p -- > defines the number of hash addresses and needs to be passed in p
	//[0,p-1]
	int curSize;	   //Number of current elements
}HASH,*LPHASH;

Structure description of hash structure -- > the hash structure is represented by structure pointer

LPHASH createHashTable(int p) 
{
	LPHASH hash = (LPHASH)malloc(sizeof(HASH)); //Dynamic memory request
	assert(hash);
    //Initialize data
	hash->curSize = 0;
	hash->divisor = p;
	hash->table = (LPDATA*)malloc(sizeof(LPDATA)* hash->divisor); //Determined by the remainder
	assert(hash->table);
	for (int i = 0; i < hash->divisor; i++) 
	{
		hash->table[i] = NULL;                 //After the secondary pointer applies for memory, initialize each primary pointer
	}
	return hash;
}

Insert data

• Pay attention to apply for memory before copying elements

//Table to insert data to insert
void insertData(LPHASH hash, DATA data) 
{
	//Find the hash address before inserting -- > call the hash function. / / there is no hash conflict
	int pos = search(hash, data.key);        
	if (hash->table[pos] == NULL)                        //Insert directly without data
	{
		hash->table[pos] = (LPDATA)malloc(sizeof(DATA)); //Memory application note
		memcpy(hash->table[pos], &data, sizeof(DATA));   //Memory Copy 
		hash->curSize++;
	}
	else                                                 //There is a hash conflict
	{
		if (hash->table[pos]->key == data.key)           //The same key overrides the element
		{
			strcpy(hash->table[pos]->element, data.element);
		}
		else                                             //Back to the original position, the key is different
		{
			printf("hash The watch is full,Cannot insert!\n");
			return;
		}
	}
}

Hash function

• There may be hash conflicts. You need to find a suitable location to store elements

• Find the address where the current element is stored

• Return to the original position after finding a circle (through the remainder method), indicating that there is no suitable position

• curPos + 1 if there is no element, just put the element in the current position

//The table to be found is found through the key: because the hash address is generated through the key
int search(LPHASH hash, int key) 
{
	int pos = key % hash->divisor;  //There are no conflicting hash addresses
	//There is a conflict. Open address method is used to find hash address
	int curPos = pos;
	do 
	{
		//The key is the same, and the overwriting data method is used as a conflict
		if (hash->table[curPos] == NULL||hash->table[curPos]->key==key)
			return curPos;          //==NUll description can be used
		curPos = (curPos + 1) % hash->divisor; //Don't be empty. Go back
	} while (curPos != pos);        //If the current POS is not equal to the original POS, search it
	return curPos;
}

Print hash table -- > Print array

void printHash(LPHASH hash) 
{
	for (int i = 0; i < hash->divisor; i++) //Print with maximum capacity length
	{
		if (hash->table[i] == NULL) 
		{
			printf("NULL\n");
		}
		else                               //Not empty print element
		{
			printf("%d:%s\n", hash->table[i]->key, hash->table[i]->element);
		}
	}
}

Test code

int main() 
{
	LPHASH hash = createHashTable(10); //Create table
	DATA array[5] = { 1,"thunder",11,"spring",23,"April",44,"baby",56,"virtual" };
	for (int i = 0; i < 5; i++) 
	{
		insertData(hash, array[i]);
	}
	printHash(hash);
	return 0;
}
//Test code

NULL
1:thunder
11:spring
23:April
44:baby
NULL
56:virtual
NULL
NULL
NULL