07_ Hash

Hash

What is hash ：
Hash ：hash; It's a hash function

1 Hash conflicting 4 Method of disposal ：

• 1. Open addressing ： Also called linear detection ;
  

The disadvantage of one detection is that the data will be concentrated in one piece , The solution is square detection （ Second detection ）, Avoid stacking

Positive numbers ： Represents right probe
negative ： Represents left probe

• 2. Hash function again （ Hash ） Law ：
  

• 3. Chain address ：
  As long as there is data conflict, the header is inserted under the same subscript

• Public spill area law ：
  A basic table , An overflow table ; Put the conflicting data into the overflow table .
  The disadvantage is when the data is too large , The basic table is too small , The specification of overflow table will be very large

2 Chained hash

Structure definition ：

#define HASHSIZE 12
typedef struct Node
{
    
	int data;
	struct Node* next;
}Node, * PNode;


typedef struct Head
{
    
	//struct Node *arr[HASHSIZE];// Pointer array （ An array of pointers ）
	struct Node arr[HASHSIZE];// Array arr In the store Node In itself 
}Head, * PHead;

API Realization

void Init_listhash(PHead ph)
{
    
	//assert
	for (int i = 0; i < HASHSIZE; i++)
	{
    
		//ph->arr[i].data;//  Don't use 
		ph->arr[i].next = NULL;
	}
}

bool Insert_hash(PHead ph, int key)// Head insertion 
{
    
	int hash = key % HASHSIZE;

	// Create a new node 
	struct Node* pnewnode = (Node*)malloc(sizeof(Node) * 1);
	assert(pnewnode != NULL);
	pnewnode->data = key;

	// Insert 
	pnewnode->next = ph->arr[hash].next;
	ph->arr[hash].next = pnewnode;

	return true;
}

bool Del_Hash(PHead ph, int key)
{
    
	int hash = key % HASHSIZE;

	struct Node* p = &ph->arr[hash];
	for (p; p->next != NULL; p = p->next)
	{
    
		if (p->next->data == key)
		{
    
			// here p->next  The node pointed to is the node we want to delete 
			struct Node* q = p->next;
			p->next = q->next;
			free(q);
			q = NULL;

			return true;
		}
	}
	return false;
}

struct Node* Search(PHead ph, int key)
{
    
	int hash = key % HASHSIZE;

	struct Node* p = ph->arr[hash].next;
	for (p; p != NULL; p = p->next)
	{
    
		if (p->data == key)
		{
    
			return p;
		}
	}

	return NULL;
}

void Show_Hash(PHead ph)
{
    
	for (int i = 0; i < HASHSIZE; i++)
	{
    
		printf("%3d: ", i);
		struct Node* p = ph->arr[i].next;
		for (p; p != NULL; p = p->next)
		{
    
			printf("%d ", p->data);
		}
		printf("\n");
	}

}

3 Consistent hashes and virtual nodes