< C> C language hash table usage

C Language hash table usage example

One 、 The header file

#include "uthash.h"

Two 、API

Structure form

struct HashTable_t {
    
	int key;
	int value;
	UT_hash_handle hh;
}

• key The type of can be char *、char []、int、void* Four kinds of , value It can be of any type .
• UT_hash_handle The structure is hash API Use , You don't have to pay attention to .

HASH_ADD_INT()

add to int Parameters to hash table ,HASH_ADD_INT(hash, key, value)

HASH_FIND_INT()

Look up... From the hash table int Parameters ,HASH_FIND_INT(hash, &key, value)
And HASH_ADD_INT Different ,FIND API Medium key Need to get the address .

HASH_DEL（）

Remove node from hash table .

HASH_COUNT()

Count the number of nodes in the hash table .

3、 ... and 、 Sample code

The code is leetcode subject , Sum of two numbers

Given an array of integers nums And an integer target value target, Please find... In the array And is the target value target the Two Integers , And return their array subscripts .

You can assume that each input corresponds to only one answer . however , The same element in the array cannot be repeated in the answer .

You can return the answers in any order .

Example 1：

Input ：nums = [2,7,11,15], target = 9
Output ：[0,1]
explain ： because nums[0] + nums[1] == 9 , return [0, 1] .
Example 2：

Input ：nums = [3,2,4], target = 6
Output ：[1,2]

Example 3：

Input ：nums = [3,3], target = 6
Output ：[0,1]

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/two-sum
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

/** * Note: The returned array must be malloced, assume caller calls free(). */
 struct hashTable {
     //HASH Table structure definition 
     int key;
     int value;
     UT_hash_handle hh;
 };

struct hashTable *Hash; // Hash table global scalar 

 struct hashTable *find(int key) // Find out if there is... In the hash table 
 {
    
     struct hashTable *tmp = (struct hashTable *)malloc(sizeof(struct hashTable));
     HASH_FIND_INT(Hash, &key, tmp);

    if(tmp)
        return tmp;
    else
        return NULL;
 }

void insert(int key, int value)
{
    
    struct hashTable *tmp = find(key); // Before insertion , Find out if there are the same key

    if(tmp == NULL) {
     // inequality 
        struct hashTable *node = (struct hashTable *)malloc(sizeof(struct hashTable));
        node->key = key;
        node->value = value;
        HASH_ADD_INT(Hash, key, node); // Create a new hash node , insert data .
    } else
   		tmp->value = value // There is the same , Update data .
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    
    int *result = (int *)malloc(sizeof(int) * 2);
    struct hashTable *ret = NULL;
    Hash = NULL;

    for(int i = 0 ; i < numsSize; i++){
    
        ret = find(target - nums[i]);
        if(ret) {
    
            result[0] = ret->value;
            result[1] = i;
            *returnSize = 2;
            return result;
        }
        insert(nums[i], i);
    }
    *returnSize = 0;
    return NULL;
}

summary

1、 be familiar with C Use of Library hash table
2、 Sum of two numbers , How to convert to hash table . The same array that needs to be iterated , Consider using a hash table , Reduce time complexity , But the use of hash table increases the space complexity . Sacrifice space , Speed up .