# 2022q1 Homework1 (quiz1)
contributed by < `a12345645` >

## 測驗1
題目為 Leetcode [Two Sum](https://leetcode.com/problems/two-sum/)

int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
    map_t *map = map_init(10);
    *returnSize = 0;
    int *ret = malloc(sizeof(int) * 2);
    if (!ret)
        goto bail;

    for (int i = 0; i < numsSize; i++) {
        int *p = map_get(map, target - nums[i]);
        if (p) { /* found */
            ret[0] = i, ret[1] = *p;
            *returnSize = 2;
            break;
        }

        p = malloc(sizeof(int));
        *p = i;
        map_add(map, nums[i], p);
    }

bail:
    map_deinit(map);
    return ret;
}

在這裡使用 hash table 實作
把 `target - nums[i]` 作為 key 使用 `map_get` 來尋找
如果在 hash table 中找到就可以與之相加為 `target` 並且回傳
沒有就把 `nums[i]` 作為 key 使用 `map_add` 加入 hash table

### hash table

#### hlist_node 與 hlist_head

struct hlist_node { struct hlist_node *next, **pprev; };
struct hlist_head { struct hlist_node *first; };


在 hash table 中每個單位為 `hlist_head` 而要加入新的元素或是發生碰撞時，就會在後面接上 `hlist_node`
- 為什麼 `hlist_head` 與 `hlist_node` 的結構不一樣

因為 hash table 為了避免常常發生碰撞，通常會建的比較大有很多的空缺，而在 hash table 只需要單向的 linked list 所以使用了兩種不同結構來儲存，這樣就可以減少一半的儲存空間。

- 為什麼 `hlist_node` 的 `pprev` 會是 pointer to pointer

因為 head 跟 node 的結構是不一樣的，如果只使用 `prev` 的話就必須判斷是否回 head ，並且需要做強制的型態轉換，所以使用 `pprev` 指向前一個元素的 `struct hlist_node *next` 元素，如果是 head 就會是 `first` ，把特例變成通例。

#### map_t

typedef struct { int bits; struct hlist_head *ht; } map_t;

`bits` 表示 `ht` 的大小為 2 的 `bit` 次方

#### map_get

#define GOLDEN_RATIO_32 0x61C88647
static inline unsigned int hash(unsigned int val, unsigned int bits) {
    /* High bits are more random, so use them. */
    return (val * GOLDEN_RATIO_32) >> (32 - bits);
}

static struct hash_key *find_key(map_t *map, int key) {
    struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
    for (struct hlist_node *p = head->first; p; p = p->next) {
        struct hash_key *kn = container_of(p, struct hash_key, node);
        if (kn->key == key)
            return kn;
    }
    return NULL;
}

void *map_get(map_t *map, int key)
{
    struct hash_key *kn = find_key(map, key);
    return kn ? kn->data : NULL;
}

主要是使用 `find_key` 來在 hash table 尋找
`target = ht[hash(key)]`
把 key 通過 hash function 再去 hash table 中尋找是否有值

#### map_add

void map_add(map_t *map, int key, void *data)
{
    struct hash_key *kn = find_key(map, key);
    if (kn)
        return;

    kn = malloc(sizeof(struct hash_key));
    kn->key = key, kn->data = data;

    struct hlist_head *h = &map->ht[hash(key, map->bits)];
    struct hlist_node *n = &kn->node, *first = h->first;
    AAA;
    if (first)
        first->pprev = &n->next;
    h->first = n;
    BBB;
}

`AAA` = `n->next = first;`
`BBB` = `n->pprev = &h->first;`

要把新的 `hash_key` 插入 list 的頭
所以在 `AAA` 要先把原本的第一個放到 `n->next`
然後確認原本的 `first` 是否為空，把 `first->pprev` 指向 `n`
再把 head 的 `first` 指向 `n`
最後 `BBB` 是在把 `n->pprev` 指回去 head

<!--
## 測驗2
題目為 Leetcode [82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)

#include <stddef.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;

    if (COND1) {
        /* Remove all duplicate numbers */
        while (COND2)
            head = head->next;
        return deleteDuplicates(head->next);
    }

    head->next = deleteDuplicates(head->next);
    return head;
}

-->