2022q1 Homework1 (quiz1)

contributed by < kevinshieh0225 >

作業需求
 測驗題目

部分參考 freshLiver 的筆記作法進行改寫。

測驗 1 Hash Map Implementation

Two Sum 是在 leetcode 上的經典首選，讓大家見識到 hash table 演算法的妙用。本測驗希望我們進入到 hash table 內部實作中。

hash table 實作結構

hash table (HT)的性質如下：輸入特定鍵（key），HT 將回傳其對應的值(value)。基於一對一關係，理想上可使索取的時間複雜度為 O(1)。

在 HT 的實作如下：由於建立一個能含括所有 key 的 HT 是不實際的，故我們先為 key 做編碼，對應到我們建立的有限目錄中，隨後以 linked list (ll)的結構將鍵值串接起來（如同我們先將資料分門別類，隨後從分類中尋找我們要的是否存在）。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

(取自 jserv)

回到程式碼：map_t 建立 map ，其下會有 an array of hlist_head 。我們前面提到 key 會先編碼後置入目錄對應的 LL ，這裡即可看到我們會建立

2^{b i t s}

個目錄與 LL 。

hash_key 與 hlist_node 即為 key/value 節點。在透過編碼後 hlist_node 被安插在對應目錄中，在尋鍵時透過尋訪 hlist_node 並以 container_of 取 hash_key 的值。

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

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

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

hash table init

我們可以看到 map_t 初始化的過程，可以看到我們同時建立了一個 map_t 與（1 << bits ==

2^{b i t s}

）個 hlist_head，若建立中有失敗則清除內容並返回 NULL。

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

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

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

hash encode

執行 hash 的演算法。最後會生成並回傳一個

[0, 2^{b i t s} - 1]

範圍內的無號整數。

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

hash find, get

find_key function：在 HT 中尋找是否有對應 key 值，若有則回傳對應的 hasy_key * ，若無則回傳 NULL。
這裡首先我們先確認 key 被放在哪一個編碼的 bucket 中，透過 hash(key, map->bits) 這個函式取得編碼，並在 array 中取得對應的 hlist_head。接著就是逐一尋訪該 LL 去確認是否有 key 於當中。

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

map_get function：從 HT 中確認是否有對應鍵值，若有則回傳鍵值對應的 value，若無則返還 NULL。
這裡特別的是此 function 的回傳值是 void pointer。這是一種很有彈性的作法，我們可以用 void pointer 去指不同的變數，再把它透過轉型（casting）還原回來。由於我們在這個實作中不確定是否能有對應的回傳鍵值，所以使用這個的方式，若回傳 NULL 即可讓 if-else 更直覺的判斷與執行對應操作。

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

map_add 與考試答案

map_add function：確認是否有在 HT 中有對應鍵值，若有則不執行，無則新增鍵值在 HT 中。

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 到 BBB 的程式碼意思是要將新的 hlist_node *n 插入在 hlisthead *h 的 first 位置，其中如果 h->first 早就已經有 hlist_node 時，我就插入兩者之間。

AAA 應為 (c) n->next = first
BBB 應為 (a) n->pprev = &h->first

測驗 2 : 82. Remove Duplicates from Sorted List II

本題透過遞迴的方式實現刪除重複節點的函式。其中：

COND1 = head.next != null && head.val == head.next.val
COND2 = head.next != null && head.val == head.next.val

為何需要用 if 來包裝和裡面 while 相同的條件式呢？看似重複操作，但其實是因為條件內外執行操作是不同的行為，而必須在新增一個 if(COND1) 來隔離條件。

在 if(COND1) 內的操作是我們已經確定要移除當下重複的節點了，我們用 while 不斷將 head 重新指向其後，並在最後 return 遞迴中 head->next 的 ListNode 在這一番的操作下便可以把所有重複節點在這操作下完全移除。

相比於此，我們看 if(COND1) 外的操作：我們先對 head->next 後的節點進行 deleteDuplicates 的遞迴整理，最後回傳的還是 head node ，光是操作和回傳的形式都不同，而使他必須用 if(COND1) 來做內外切分。

iterate version

#include <stddef.h>

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

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;
    struct ListNode **ckp = &head;
    struct ListNode *iter = (*ckp)->next;
    while (iter) {
        if ((*ckp)->val == iter->val) {
            do {
                iter = iter->next;
            } while (iter && (*ckp)->val == iter->val);
            *ckp = iter;
            if (!iter)
                break;
        } else {
            ckp = &((*ckp)->next); 
        }
        iter = iter->next;
    }
    return head;
}

測驗 3 : 146. LRU Cache

在 Cache replacement policies 中，Least Recently Used 是一個策略之一。當 Cache 要更新時，將裡頭最後被使用的資料去除並更新。在 LRU 演算法我們面臨的問題是：如何在常數時間內達到兩件目的：如何確認 Cache hit、如何更新使用時間的紀錄。

LRU Cache 實作原理：Hashmap + DoubleLinkedList

透過 Hashmap 可在常數時間裡「確認是否 Cache hit」；透過 DoubleLinkedList 讓我們在常數時間裡「更新 Cache 紀錄」。

這時可能會有一個問題是：如果要做 DoubleLinkedList 的尋訪，那應該也需要線性時間吧？然而我們如果搭配著 list.h 與 container_of 的技巧：在 Hashmap 與 DoubleLinkedList 上使用共用的 list_head 節點，那麼當我要維護 DoubleLinkedList 時，只要從 Hashmap 取得該節點更新；或是當我要刪除最近未使用的節點時，從 DoubleLinkedList 找到最末的節點。

LRUNode 是紀錄在 LRUCache 中的 DoubleLinkedList(DLL) 節點。

我們觀察 LRUCache，dhead 與 hheads[] 分別就是 DLL 的首節點，與第一題類似形式的 Hashmap 實作。
capacity 代表 Cache 的大小， count 代表目前總共有多少筆資料存放其中。

typedef struct {
    int capacity, count;             
    struct list_head dhead, hheads[];
} LRUCache;
    
typedef struct {
    int key, value;
    struct list_head hlink, dlink;
} LRUNode;

LRU Cache create/free

在 lRUCacheCreate 中我們初始化紀錄使用時間 DLL 的 dhead，和紀錄是否存在其中的 Hashmap hhead[]。
在 lRUCacheFree 中我們也針對這些建立的動態記憶體位置依序釋放。

MM1 應填入 list_for_each_entry_safe ，在 DLL 中依序釋放節點，並不斷確認下一個節點是否為安全節點。

LRUCache *lRUCacheCreate(int capacity)
{   
    LRUCache *obj = malloc(sizeof(*obj) + capacity * sizeof(struct list_head));
    obj->count = 0;
    obj->capacity = capacity;
    INIT_LIST_HEAD(&obj->dhead);
    for (int i = 0; i < capacity; i++)
        INIT_LIST_HEAD(&obj->hheads[i]);
    return obj;
}
    
void lRUCacheFree(LRUCache *obj)
{       
    LRUNode *lru, *n;
    MMM1 (lru, n, &obj->dhead, dlink) {
        list_del(&lru->dlink);
        free(lru);
    }
    free(obj); 
}

LRU Cache Get

輸入整數 key，如果其值有在 hashmap 中找到，更新 &obj->dhead 的 DLL結構，把該節點更新到開頭，代表最近使用，並回傳該 lru->value；若未找到則回傳 -1。

這裡可以看到這裡的編碼方式是 key 值除 capacity 得到

[0, c a p a c i t y - 1]

的 hash ，相比前面的編碼來看是比較簡易的實作。

MMM2 應該是 list_for_each_entry。用該函數去尋訪 &obj->hheads[hash] 中的每個節點來確認是否該資料已存在於 hashmap 中。

int lRUCacheGet(LRUCache *obj, int key)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    MMM2 (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            return lru->value;
        }
    }
    return -1;
}

LRU Cache Put















































/**
 * @brief 插入新的鍵值並更新 Cache
 * 
 * @param *obj LRUCache
 * @param key 鍵
 * @param value 值
 */
void lRUCachePut(LRUCache *obj, int key, int value)
{
    /**
     * @ brief 執行 lRUCacheGet 行動：
     * 
     * 確認該 key 是否已存在於 Cache 中
     * 尋訪 LRUCache 的 HashTable
     * 若存在則更新 DLL 與該節點對應的 value 並函式結束回傳。
     */

    LRUNode *lru;
    int hash = key % obj->capacity;
    MMM3 (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            lru->value = value;
            return;
        }
    }
    /**
     * 確認此時的 Cache 存放容量（count）是否已經達到上限
     * if 到達上限，準備更新最近未使用的節點資料
     * else 未達到上限，建立新節點並更新 count 的大小
     */
    if (obj->count == obj->capacity) {
        lru = MMM4(&obj->dhead, LRUNode, dlink);
        list_del(&lru->dlink);
        list_del(&lru->hlink);
    } else {
        lru = malloc(sizeof(LRUNode));
        obj->count++;
    }
    /**
     * 依據輸入鍵值，對 lru 節點進行更新
     */
    lru->key = key;
    list_add(&lru->dlink, &obj->dhead);
    list_add(&lru->hlink, &obj->hheads[hash]);
    lru->value = value;
}

MMM3 應填入 list_for_each_entry。

MMM4 應填寫 list_last_entry 取得 DLL 中最後一個節點，意即是最近未使用的節點。

答案卻是 list_for_each_entry？有點怪。

測驗 4 : 128. Longest Consecutive Sequence

程式碼解析

/**
 * @brief LL 節點結構
 */
struct seq_node {
    int num;
    struct list_head link;
};                                                                                                                                                            
/**
 * @brief 尋訪 HashTable 中是否存在該資料
 *
 * 對 @num 取絕對值並編碼出所屬欄位
 * 尋訪該欄位確認是否存在該筆資料
 *
 * @param num 目標數值
 * @param size HT 大小（欄位大小）
 * @param *heads HT 的首節點
 * @return if true struct seq_node*; else NULL; 
 */           
static struct seq_node *find(int num, int size, struct list_head *heads)
{   
    struct seq_node *node;
    int hash = num < 0 ? -num % size : num % size;
    list_for_each_entry (node, &heads[hash], link) {
        if (node->num == num)
            return node;
    }
    return NULL;
}

/**
 * @brief 從一組整數陣列中，回傳最長的連續數組
 * 
 * 1. 建立欄位數 = n_size 大小的 HashTable
 * 2. 將整數陣列的數值插入進 HashTable 中
 * 3. 尋訪最長連續數組
 * 
 * @param *nums 整數陣列
 * @param n_size 陣列之大小
 */
int longestConsecutive(int *nums, int n_size)
{
    int hash, length = 0;
    struct seq_node *node;
    struct list_head *heads = malloc(n_size * sizeof(*heads));

    for (int i = 0; i < n_size; i++)
        INIT_LIST_HEAD(&heads[i]);

    for (int i = 0; i < n_size; i++) {
        if (!find(nums[i], n_size, heads)) {
            hash = nums[i] < 0 ? -nums[i] % n_size : nums[i] % n_size;
            node = malloc(sizeof(*node));
            node->num = nums[i];
            list_add(&node->link, &heads[hash]);
        }
    }

    /**
     * @brief 尋訪最長連續數組
     * 
     * length : 搜尋截至目前最長的連續數組
     * len : 本次搜索中的連續數組長度
     * 
     * for 迭代過所有的陣列數值
     * 
     *     len 重置為 0
     *     如果 node 存在於 HT 中，則開始尋找與其相連的連續數組
     * 
     *     while 向左 LLL = --left 搜尋連續數組
     *         若有則增加 len 長度，並刪除 HT 上該節點
     *     while 向右 RRR = ++right 搜尋連續數組
     *         若有則增加 len 長度，並刪除 HT 上該節點
     * 
     *     比較 length 與 len 的長度進行更新
     * 
     * 最後回傳 length
     */
    for (int i = 0; i < n_size; i++) {
        int len = 0;
        int num;
        node = find(nums[i], n_size, heads);
        while (node) {
            len++;
            num = node->num;
            list_del(&node->link);

            int left = num, right = num;
            while ((node = find(LLL, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            while ((node = find(RRR, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            length = len > length ? len : length;
        }
    }

    return length;
}

LLL = --left
RRR = ++right