Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

Hello everyone, MY name is Melo, a sophomore majoring in software engineering. After a year of fumbling, I am now preparing to develop backstage projects in the studio. However, I still want to talk about data structure and algorithm in this article. The course of data structure was not opened until the second year of the university. I hope I can accumulate experience in background project development while learning data structure. Without realizing it, we’ve already touched on two or three data structures: linked lists, stacks, and queues, but have you noticed that the first few data structures don’t do very well in terms of lookup performance? To further improve lookup performance, we’re going to learn another entirely new data structure, hash tables!

Train of thought

Array + linked list to achieve

In Java8, when hash collisions reach a certain level, each location is transformed from a linked list to a red-black tree

An array of

An array of Pointers that hold the addresses of elements

The list

When we design hash functions, it is inevitable that there will be conflicts (i.e., A and B both find the position h.cd [I]). The idea of chained address method is to let them exist in A list of synonyms at this position (the so-called synonyms mean that their hash address is the same).

In contrast to the open address method, when a hash conflict occurs, instead of changing the value of the hash address, it allows them to co-exist in different places on the list of the same hash address.

Insert new elements

The hash function is called to find the key for val

If key has a value, the list of synonyms on [key] is iterated to verify that the val already exists.

- If yes, return UNSUCCESS; // Failed to insert
- If not, make val point to the original table header and become the new table header

Array [key]=val if key has no value

Of course, the above is pseudo code, the specific implementation of a lot of details need to pay attention to

And the above lookup can be wrapped as a separate function

The header file HashTable. H

typedef long KeyType;

//Node loads the structure definition, which may contain elements of various data types. This assumes only keyType, which is long
typedef struct{
	KeyType key;
} RcdType;
Copy the code

The header file CHashTable. H

#include "Common.h"
#include "HashTable.h"

typedef struct Node {
     RcdType r;
     struct Node *next;
 } Node;

typedef struct {
      // Array of Pointers
      Node **rcd;
      // Hash table capacity
	  int size;
      // The number of records in the current table
      int count; 
      // Function pointer variable used to select the hash function
      int (*hash)(KeyType key, int);  
} CHashTable; 

// Initialize the hash table
Status InitHash(CHashTable &H, int size, int (*hash)(KeyType,int));
// Destroy the hash table
Status DestroyHash(CHashTable &H); 
/ / to find
Node* SearchHash(CHashTable H, KeyType key); 
/ / insert
Status InsertHash(CHashTable &H, RcdType e); 
/ / delete
Status deleteHash(CHashTable &H, KeyType key, RcdType &e); 
Copy the code

The source file CHashTable. CPP

#include "CHashTable.h"

// Initialize the hash table
Status InitHash(CHashTable &H, int size, int (*hash)(KeyType,int))  {    
  int i;
  H.rcd = (Node**)malloc(sizeof(Node *)*size);
  if(NULL==H.rcd) return OVERFLOW;
  for (i = 0; i < size; i++) {
	  H.rcd[i] = NULL;
  }
  H.size = size;  
  H.hash = hash;  
  H.count = 0;
  return OK;
}

// Destroy the hash table
Status DestroyHash(CHashTable& H) {
	H.size = 0;
	H.count = 0;
	free(H.rcd);
	free(H.hash);
	// If the destruction fails
	if(H.rcd ! =NULL|| H.hash ! =NULL) {
		return UNSUCCESS;
	}
	return SUCCESS;
}

/ / to find
Node* SearchHash(CHashTable H, KeyType key) { 
	// Find the position in the array
   int p = H.hash(key, H.size);
   Node* np;
   // Search on the list of synonyms for that location
   for(np = H.rcd[p]; np ! =NULL; np = np->next) {
	   if (np->r.key == key) {
		   returnnp; }}return NULL;
}

// Insert record e
Status InsertHash(CHashTable &H, RcdType e){
   int p;   
   Node *np;
   // Insert into the header if the lookup is unsuccessful
   if((np = SearchHash(H, e.key))==NULL) { 
      p = H.hash(e.key, H.size);
      np = (Node*)malloc(sizeof(Node));      
	  if(np==NULL)return OVERFLOW;
      np->r = e;  
	  // point to the header first
	  np->next = H.rcd[p];   
	  // start the list
	  H.rcd[p] = np;     
	  H.count++; 
	  return OK;
   }   
   else   
	   return ERROR;
}

// Remove the specified element and return to e
Status deleteHash(CHashTable &H,KeyType key,RcdType &e) {
	// Find the location
	Node* np = SearchHash(H, key);
	// If not found
	if (NULL == np) {
		return UNSUCCESS;
	}
	// If you find it
	else
	{
		// Find the position in the array
		int p = H.hash(key, H.size);
		// The current node
		Node* pNow;
		// return to e
		e = np->r;
		// First to determine if it is the first
		if (H.rcd[p] == np) {
			// Change the new table header
			H.rcd[p] = np->next;
		}
		// If not the first
		else
		{
			// Search on the list of synonyms for that location
			for(pNow = H.rcd[p]; pNow ! =NULL&& pNow->next ! =NULL; pNow = pNow->next) {
				// If a precursor of the Search result is found
				if (pNow->next == np) {
					// Make the current node point to the next node to be deletedpNow->next = np->next; }}}/* If np is not null or reassigned, it will become a wild pointer to avoid being used again
		free(np);
		np = NULL;
        // Note that count is reduced accordingly
        H.count--;
		returnSUCCESS; }}Copy the code

For the problem of wild pointer here, you can refer to stray pointer

The Test file

#include "ChashTable.h"

int hash(KeyType key, int size) { 
    return (3*key)%size;
}

void collision(int &hashValue, int hashSize) {// Linear detection method
     hashValue = (hashValue +1)% hashSize;
}

void TraverseCHashTable(CHashTable H){
   Node* np;
   int i;
   for(i = 0; i<H.size; i++) {
	   printf("\n%d :", i);
	   for(np = H.rcd[i]; np! =NULL; np = np->next)
		   printf(" %d ", np->r.key); }}void main(a){
   /******** chain address hash table *********/
   CHashTable H;
   int (*h)(KeyType, int);
   h = hash;
   InitHash(H, 11, h);
   
   RcdType data[] = {22.41.53.46.30.13.12.67};
   int i;
   for(i = 0; i<8; i++)
     InsertHash(H, data[i]);  

   printf("Primitive linked list \n");
   TraverseCHashTable(H);
   printf("\n");
   RcdType e;
   KeyType k[] = { 41.22.40 };
   for (int i = 0; i < 3; i++) {
       if (deleteHash(H, k[i], e) == SUCCESS) {
           TraverseCHashTable(H);
           printf("\n Delete %d succeeded \n",k[i]);
       }
       else
       {
           TraverseCHashTable(H);
           printf("\n failed to delete %d \n",k[i]);
       }
       
   }
      
   system("pause");
}
Copy the code

Delete running Effect

Build hash table questions

In fact, it helps us initialize it, and h.size is also given

#include "allinclude.h"  //DO NOT edit this line

// Find the element key in the hash table
HNode* SearchHash(ChainHashTab H,HKeyType key){
  // Find the position in the array
   int p = Hash(H,key);
   HNode* np;
   // Search on the list of synonyms for that location
   for(np = H.rcd[p]; np ! =NULL; np = np->next) {
     // Return the pointer if it is found
	   if (np->data == key) {
		   returnnp; }}// Return NULL if not found
   return NULL;
}

// Insert key into the hash table
Status InsertHash(ChainHashTab &H,HKeyType key){
   int p;   
   HNode *np = SearchHash(H,key);
   // Insert into the header if the lookup is unsuccessful
   if(np == NULL) { 
      p = Hash(H,key);
      np = (HNode*)malloc(sizeof(HNode));  
      // If allocation fails, NULLKEY is returned
  	  if(np==NULL) {return NULLKEY;
  	  }
      np->data = key;  
  	  // point to the header first
  	  np->next = H.rcd[p];   
  	  // start the list
  	  H.rcd[p] = np;     
  	  H.count++; 
  	  return OK;
   }
   // UNSUCCESS is returned for repeated inserts
   else{   
	   returnUNSUCCESS; }}int BuildHashTab(ChainHashTab &H, int n, HKeyType es[])
{  // Add your code here
  
  for(int i=0; i<n; i++){ Status IfSucceed = InsertHash(H,es[i]);// Repeated insertion does not mean that the entire hash table has failed to build
    // Only if the allocation fails during insertion means.....
    if(NULLKEY == IfSucceed){
      returnERROR; }}return OK;
}
Copy the code

Write in the last

In fact, there are many ways to implement hash tables, and the underlying language is not the same, wait until later in the Java collection source, we can also talk about it!

Author: “Melo_” Source: juejin.cn/user/299988… The copyright of this article belongs to the author and blog garden, welcome to reprint, but without the consent of the author must retain this statement, and give the original link in the obvious position of the article page, otherwise reserve the right to pursue legal responsibility.

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Hash table – chained address method

Train of thought

An array of

The list

Insert new elements

The hash function is called to find the key for val

The header file HashTable. H

The header file CHashTable. H

The source file CHashTable. CPP

The Test file

Delete running Effect

Build hash table questions

Write in the last

Hash table – chained address method

Train of thought

An array of

The list

Insert new elements

The hash function is called to find the key for val

The header file HashTable. H

The header file CHashTable. H

The source file CHashTable. CPP

The Test file

Delete running Effect

Build hash table questions

Write in the last

Related Posts

How to elegantly design a distributed API return format?

PHP7 under the implementation of coroutine

Java8 Stream, simple and fast processing collection (part 2)