C++ language implementation of hash table details and example code

C++ language implementation of hash table details

Summary:

The hash table, sometimes called a hash table. In my opinion, the hash table is an intermediate structure between a linked list and a two-fork tree. Linked list use 10 points convenient, but data search 10 points trouble; The data in the two-fork tree is strictly ordered, but at the expense of one more pointer. The hash table not only satisfies the convenience of data search, but also does not occupy too much content space.

For example, all data is like a lot of books. If the books are stacked one by one, like a linked list or a linear table, the whole data will be very disorderly and messy. Before you find the books you need, you will have to go through a lot of query process. If you number all the books and put them in order, then if the number you are looking for is n, you will find the books you need very quickly after 2 points of searching. But every one if you are not to be many kinds of books, then you can these books are classified, which one is literature and what is art, which are engineering, which is the science, you as long as these books are simple, looking for a book will become very simple, for example, if the book you are looking for is a book on computer, then you can search to the engineering of class 1, this also can appear trouble to find.

I don't know if this is clear to you, but the classification method mentioned above is actually the essence of hash table. Now we can write a simple hash operation code.

a) defines hash tables and base data nodes

typedef struct _NODE 
{ 
  int data; 
  struct _NODE* next; 
}NODE; 
 
typedef struct _HASH_TABLE 
{ 
  NODE* value[10]; 
}HASH_TABLE; 

b) create the hash table

HASH_TABLE* create_hash_table() 
{ 
  HASH_TABLE* pHashTbl = (HASH_TABLE*)malloc(sizeof(HASH_TABLE)); 
  memset(pHashTbl, 0, sizeof(HASH_TABLE)); 
  return pHashTbl; 
} 

c) look for data in the hash table

NODE* find_data_in_hash(HASH_TABLE* pHashTbl, int data) 
{ 
  NODE* pNode; 
  if(NULL == pHashTbl) 
    return NULL; 
 
  if(NULL == (pNode = pHashTbl->value[data % 10])) 
    return NULL; 
 
  while(pNode){ 
    if(data == pNode->data) 
      return pNode; 
    pNode = pNode->next; 
  } 
  return NULL; 
} 

d) inserts data into the hash table

STATUS insert_data_into_hash(HASH_TABLE* pHashTbl, int data) 
{ 
  NODE* pNode; 
  if(NULL == pHashTbl) 
    return FALSE; 
 
  if(NULL == pHashTbl->value[data % 10]){ 
    pNode = (NODE*)malloc(sizeof(NODE)); 
    memset(pNode, 0, sizeof(NODE)); 
    pNode->data = data; 
    pHashTbl->value[data % 10] = pNode; 
    return TRUE; 
  } 
 
  if(NULL != find_data_in_hash(pHashTbl, data)) 
    return FALSE; 
 
  pNode = pHashTbl->value[data % 10]; 
  while(NULL != pNode->next) 
    pNode = pNode->next; 
 
  pNode->next = (NODE*)malloc(sizeof(NODE)); 
  memset(pNode->next, 0, sizeof(NODE)); 
  pNode->next->data = data; 
  return TRUE; 
} 

e) deletes data from the hash table

STATUS delete_data_from_hash(HASH_TABLE* pHashTbl, int data) 
{ 
  NODE* pHead; 
  NODE* pNode; 
  if(NULL == pHashTbl || NULL == pHashTbl->value[data % 10]) 
    return FALSE; 
 
  if(NULL == (pNode = find_data_in_hash(pHashTbl, data))) 
    return FALSE; 
 
  if(pNode == pHashTbl->value[data % 10]){ 
    pHashTbl->value[data % 10] = pNode->next; 
    goto final; 
  } 
 
  pHead = pHashTbl->value[data % 10]; 
  while(pNode != pHead ->next) 
    pHead = pHead->next; 
  pHead->next = pNode->next; 
 
final: 
  free(pNode); 
  return TRUE; 
} 

Conclusion:

1, hash table is not complex, we often use in the development, we suggest friends to grasp;

2. The hash table can form a compound structure with a two-fork tree. As for why, I suggest you to think about it carefully.

Thank you for reading, I hope to help you, thank you for your support of this site!