2022q1 Homework1 (quiz1)

contributed by < cwl0429 >

測驗題目

測驗 1

• 藉由 bitwise operation，定義 hash table 大小

#define MAP_HASH_SIZE(bits) (1 << bits)

• 配置空間給 map 及 map->ht，建立一個 map

map_t *map_init(int bits) {
    map_t *map = malloc(sizeof(map_t));
    if (!map)
        return NULL;

    map->bits = bits;
    map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
    if (map->ht) {
        for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
            (map->ht)[i].first = NULL;
    } else {
        free(map);
        map = NULL;
    }
    return map;
}

記得將 map->ht 所有的 first 指標初始化，避免有存取安全疑慮

for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
            (map->ht)[i].first = NULL;

• 用 linux 風格，將 hlist_node 嵌在 hash_key 內，方便後續操作

struct hash_key {
    int key;
    void *data;
    struct hlist_node node;
};

• 藉由 type 及當前 ptr 位址，回推出此 type 結構的起始位址

#define container_of(ptr, type, member)               \
    ({                                                \
        void *__mptr = (void *) (ptr);                \
        ((type *) (__mptr - offsetof(type, member))); \
    })

• 根據 hash table 的 bits 數量，將 hash 結果限縮在多少 bits 內
  • 譬如 bits = 4，則 hash 範圍在 0~15 (0000~1111)

#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);
}

為何使用 GOLDEN RATIO 作為 hash function?

• 根據 Fibonacci Hashing 的說明，在作者設計的實驗中，fibonacci hashing 較傳統的 integer modulo 快了兩倍左右(在資料量大於 400000 時)，圖表如下:
  

  
  其中只有 ska::unordered_map 使用 fibonacci hashing

• 先藉由 key 找到對應的 hlist_head，接著在此 head 不斷往後找，直到有 key 相等或找完所有 hlist

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;
}

• 取得 key 所在位址，若找到則傳該 key node

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

• 將 data 加入 map 中

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;
    n->next = first; // AAA;
    if (first)
        first->pprev = &n->next;
    h->first = n;
    n->pprev = &h->first; // BBB;

原先的 code 缺少了 AAA 及 BBB 兩部分，以下是不加 AAA 及 BBB 的示意圖(圖表改自開發紀錄(quiz1)，假設 hash key 為 n ):

可以看出，有兩條 link 沒有正確串接，分別是 n->next 和 n->pprev，於是將其補上，使其變成下面的圖表:

• 使 map 完整釋放空間
• 從 map->ht[0] 開始，先將此 slot 內的 hlist_node 逐一釋放，重複此動作，直到釋放完所有的 map->ht[MAP_HASH_SIZE]

需要注意的是，這段 code 使用到 goto 技巧，用以跳過 16~20 行，但我目前還沒想到何時會有 unhash 的狀況發生

void map_deinit(map_t *map)
{
    if (!map)
        return;

    for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
        struct hlist_head *head = &map->ht[i];
        for (struct hlist_node *p = head->first; p;) {
            struct hash_key *kn = container_of(p, struct hash_key, node);
            struct hlist_node *n = p;
            p = p->next;

            if (!n->pprev) /* unhashed */
                goto bail;

            struct hlist_node *next = n->next, **pprev = n->pprev;
            *pprev = next;
            if (next)
                next->pprev = pprev;
            n->next = NULL, n->pprev = NULL;

        bail:
            free(kn->data);
            free(kn);
        }
    }
    free(map);
}

• 找到二數相加後等於 sum

想法是不斷地將 nums 的數放入 map 中，直到 map_get 找到正確的數進行回傳

• 這裡也用到了 goto，目的是在 ret 無法被配置時，jump 至 bail 將配置完成的 map 釋放

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;
}

TODO

研讀 Linux 核心原始程式碼 include/linux/hashtable.h 及對應的文件 How does the kernel implements Hashtables?，解釋 hash table 的設計和實作手法，並留意到 tools/include/linux/hash.h 的 GOLDEN_RATIO_PRIME，探討其實作考量

測驗 2

• 目標是將重複的 node 移出 sorted list

觀察 COND1，此時需要進入 if 內做刪除重複 node 的動作，因此推斷 COND1 會需要 head->val == head->next->val 的條件，另外又需要考慮到若是 head->next 為 NULL 會產生問題，所以再將 head->next 加入判斷，於是得到結論

COND1: head->next && head->val == head->next->val

再觀察 COND2 會發現需要的條件和 COND2 相同，所以

COND2: head->next && head->val == head->next->val

完整程式碼

#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;
}

嘗試避免遞迴的版本

利用指標的指標 **tmp 移除重複的 node，方便移除 node

struct ListNode* deleteDuplicates(struct ListNode* head) {
    if(!head){
        return NULL;
    }
    int curr = -111;
    for(struct ListNode **tmp = &head; *tmp ;) {
        if((*tmp)->next && (*tmp)->val == (*tmp)->next->val) {
            *tmp = (*tmp)->next;
            curr = (*tmp)->val;
        }
        if(curr == (*tmp)->val)
            *tmp = (*tmp)->next;
        else
            tmp = &(*tmp)->next;
    }
    return head;
}

用 linux 核心 的 circular doubly-linked list 改寫

遞迴版