Accepted C solution of HashMap in 4ms


  • 37
    T
    typedef struct HashNode {
        int key;
        int val;
    } HashNode;
    
    typedef struct HashMap {
        int size;
        HashNode** storage;
    } HashMap;
    
    HashMap* hash_create(int size);
    void hash_destroy(HashMap* hashMap);
    void hash_set(HashMap* hashMap, int key, int value);
    HashNode* hash_get(HashMap* hashMap, int key);
    
    HashMap* hash_create(int size){
        HashMap* hashMap = malloc(sizeof(HashMap));
        hashMap->size = size;
        hashMap->storage = calloc(size, sizeof(HashNode*));
        return hashMap;
    }
    
    void hash_destroy(HashMap* hashMap) {
        for(int i=0; i < hashMap->size; i++) {
            HashNode *node;
            if((node = hashMap->storage[i])) {
                free(node);
            }
        }
        free(hashMap->storage);
        free(hashMap);
    }
    
    void hash_set(HashMap *hashMap, int key, int value) {
        int hash = abs(key) % hashMap->size;
        HashNode* node;
        while ((node = hashMap->storage[hash])) {
            if (hash < hashMap->size - 1) {
                hash++;
            } else {
                hash = 0;
            }
        }
        node = malloc(sizeof(HashNode));
        node->key = key;
        node->val = value;
        hashMap->storage[hash] = node;
    }
    
    HashNode* hash_get(HashMap *hashMap, int key) {
        int hash = abs(key) % hashMap->size;
        HashNode* node;
        while ((node = hashMap->storage[hash])) {
            if (node->key == key) {
                return node;
            }
    
            if (hash < hashMap->size - 1) {
                hash++;
            } else {
                hash = 0;
            }
        }
    
        return NULL;
    }
    
    int* twoSum(int* nums, int numsSize, int target) {
        HashMap* hashMap;
        HashNode* node;
        int rest, i;
        
        // make the hashMap 2x size of the numsSize
        hashMap = hash_create(numsSize * 2);
        for(i = 0; i < numsSize; i++) {
            rest = target - nums[i];
            node = hash_get(hashMap, rest);
            if (node) {
                int* result = malloc(sizeof(int)*2);
                result[0] = node->val + 1;
                result[1] = i + 1;
                hash_destroy(hashMap);
                return result;
            } else {
                hash_set(hashMap, nums[i], i);
            }
        }
    }

  • 2
    J

    nice ,but why "// make the hashMap 2x size of the numsSize"


  • 0
    T

    why "// make the hashMap 2x size of the numsSize"?

    It's the load factor of a hashmap. I chose the load factor to be 0.5, which indicates how full the slots are.
    For example, If I have 16 slots, I only use half of them which is 16 * 0.5 = 8.
    AFAIK, Java's hashmap uses a load factor of 0.75, in the same case of which you use 16 * 0.75 = 12 slots.

    If you have a larger load factor, you use less memory but get more collisions. Otherwise, you have fewer collisions but use more memory. It's a tradeoff of implementation.


  • 1
    T

    is there any principle to follow when select the size of the hashmap?


  • 0
    I

    In hash_destory(), the variable i in for loop haven't initialized.


  • 0
    D

    In "hash_destory()":

    if((node == hashMap->storage[i]))


  • 0
    I

    @dimoret
    HashNode *node; if((node = hashMap->storage[i])) { free(node); }
    This set of codes is no problem, node just initialed by hashMap->storage[i], then checked whether node is null pointer, if not, free(node).


  • 0
    D

    @ishbguy
    Got it,thx!


  • 0
    B

    { 26, 32, 10, 18 } returns wrong answer.

    The hash function abs(key) % size may return same address for two numbers.


  • 0
    F

    @ban2 The program is right. when collision occurs, the address will add one until program find a free space can hold number.


  • 2
    M

    I got an AC in 3ms with this ugly code:

    int* twoSum(int* nums, int numsSize, int target) {
        int _[100001] = {0}, *index_plus_one = _ + 50000;
        for (int i = 0; i < numsSize; i++) {
            int rest = target - nums[i];
            if (index_plus_one[rest]) {
                int *ans = malloc(sizeof(int) * 2);
                ans[0] = i;
                ans[1] = index_plus_one[rest] - 1;
                return ans;
            }
            else
                index_plus_one[nums[i]] = i + 1;
        }
        return NULL;
    }

  • 0
    C

    great~~~~~~~


  • 0
    C

    @Carloss but why +1 in the final code


  • 0
    R

    Good solutions,but if you use list method ,will the results be better ?


  • 0
    R

    I think there is some initialized problem with the pointers. they are not initialized by NULL.


  • 0
    J

    What's the time complexity of the program? Should it be O(n^2) for the worst although the average running time seems much shorter? One test case is as follows: the first two number are the same, then increase them one by one, and the target is the sum of the last two numbers. eg:
    [2,2,3,4,5,6,7,8,9] and the target is 17

    Also, I want to know what running time given by the test system means? Is it the average running time for 19 cases?


  • 0
    J
    This post is deleted!

  • 0
    W

    @MyQQ said in Accepted C solution of HashMap in 4ms:

    I got an AC in 3ms with this ugly code:

    int* twoSum(int* nums, int numsSize, int target) {
        int _[100001] = {0}, *index_plus_one = _ + 50000;
        for (int i = 0; i < numsSize; i++) {
            int rest = target - nums[i];
            if (index_plus_one[rest]) {
                int *ans = malloc(sizeof(int) * 2);
                ans[0] = i;
                ans[1] = index_plus_one[rest] - 1;
                return ans;
            }
            else
                index_plus_one[nums[i]] = i + 1;
        }
        return NULL;
    }
    

    why plus 50000?


  • 0
    S

    @dimoret need't, in if((node = hashMap->storage[i])) is to find no null node and use the node for handle to free.


  • 0
    L

    @wm0823 rest may be a negative number.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.