2022q1 Homework1 (quiz1)

contributed by < hsuedw >

測驗 1

LeetCode 1. Two Sum

作答

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

延伸題目: 1. 解釋上述程式碼運作原理

為了說明方便，將程式碼還原如下所示。




































































































































#include <stddef.h>
#include <stdlib.h>

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

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

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

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

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
}

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

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

`map_init()` (第 10~25 行)

map_init() 會為 hash table 配置記憶體空間，並對 hash table 做初始化。 map_init() 完成後，會產生如下圖所示的 object。
若配置成功 (第 18~19 行) ，則對hash table 中的每個 bucket 逐一設為 NULL ()。
若 hash table 的記憶體空間配置失敗 (第 11~13 行) ，或對 bucket 的記憶體空間配置失敗 (第 16 行與第 21~23 行)，則傳回NULL。否則傳回指向 hash table 的指標。

`map_add()` (第 61~77 行)

假設目前 hash table 的狀況如下圖所示。

新的資料節點在第 72~76 行間被插入 hash table 中。





  n->next = first;
  if (first)
      first->pprev = &n->next;
  h->first = n;
  n->pprev = &h->first;

狀況 1: 有碰撞。
- 假設新插入 hash table 的資料節點的 key 經 hash() 計算後，所對應到的 bucket 不為 empty。也就是有發生碰撞發生。
- 在此假設新要插入的 bucket 為 ht[1] 所指向的非環狀雙向鏈結串列。則 kn 指標所指向的新節點會會成為此非環狀雙向鏈結串列的第一個節點。
- 插入新節點的過程如下圖所示。
狀況 2: 沒有碰撞。
- 假設新插入 hash table 的資料節點的 key 經 hash() 計算後，所對應到的 bucket 為 empty。也就是沒有發生碰撞發生。
- 在此假設新要插入的 bucket 為 ht[2] 所指向的非環狀雙向鏈結串列。
- 插入新節點的過程如下圖所示。

`map_get()` 與 `find_key()` (第 45~59 行)

map_get() 經由 find_key() 的協助，在 hash table 中尋找與 key 相吻合的資料節點 ( struct hash_key 型別的 object )。若有找到，則傳回該資料節點中表示資料的 object。否則傳回 NULL。
在 find_key() 中，經 hash() 計算得到 key 的雜湊值。也就是找到可能具有 key 這個資料節點的 bucket。然後，在第 47~51 行的 for 迴圈中，會在此 bucket (即 ht[k]->first 所指向的非環狀雙向鏈結串列)中搜尋具有 key 的資料節點。若有找到，則返回此資料節點。否則，返回NULL。

`map_deinit()` (第 79~106 行)

釋放 hash table 中，所有 object 所佔用的記憶體空間。

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

乘法運算子為二元運算子 (binary operator)，也就是有兩個運算元 (operand) 。若有一個運算元為變數，另一個為常數，那麼就可以用 bitwise left shift 與減法得到乘法的效果，而不必真的動用到硬體的乘法指令。
- 以 x * 14 這個 C 語言運算式為例。因為
  $14_{10} = 1110_{2}$ ，所以可以把 x * 14 改寫為 (x << 3) + (x << 2) + (x << 1) 或 (x << 4) - (x << 1) 。

再看看 linux kernel 是如何計算雜湊值的。



























#ifndef HAVE_ARCH__HASH_32
#define __hash_32 __hash_32_generic
#endif
static inline u32 __hash_32_generic(u32 val)
{
    return val * GOLDEN_RATIO_32;
}

static inline u32 hash_32(u32 val, unsigned int bits)
{
    /* High bits are more random, so use them. */
    return __hash_32(val) >> (32 - bits);
}

#ifndef HAVE_ARCH_HASH_64
#define hash_64 hash_64_generic
#endif
static __always_inline u32 hash_64_generic(u64 val, unsigned int bits)
{
#if BITS_PER_LONG == 64
    /* 64x64-bit multiply is efficient on all 64-bit processors */
    return val * GOLDEN_RATIO_64 >> (64 - bits);
#else
    /* Hash 64 bits using only 32x32-bit multiply. */
    return hash_32((u32)val ^ __hash_32(val >> 32), bits);
#endif
}

請注意第 6 行與第 22 行。這兩行說明了在計算雜湊值的過程中，會用到一個變數乘以一個常數的運算。

根據 [PATCH v3 05/10] Eliminate bad hash multipliers from hash_32() and hash_64()，早期的 GOLDEN_RATIO_PRIME 的定義如下:
```
/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
#define GOLDEN_RATIO_PRIME_32 0x9e370001UL
/*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
#define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001UL
```
而目前的 GOLDEN_RATIO_PRIME 的定義如下:
```
 #define GOLDEN_RATIO_32 0x61C88647
 #define GOLDEN_RATIO_64 0x61C8864680B583EBull
```
以 GOLDEN_RATIO_PRIME_32 做說明。原本的定義中，bit 1 ~ bit 15 全部為 0。如果變數 val 的值的二進位中為 1 的 bit 集中在這個範圍內，那麼計算出來的雜湊值就會很接近，而造成碰撞發生的機會大增。原本的 GOLDEN_RATIO_PRIME_64 也有相同問題。
所以，目前的 GOLDEN_RATIO_32 與 GOLDEN_RATIO_64 分別定義為 0x61C88647 與 0x61C8864680B583EBull 讓 0 與 1 交錯地均勻分布。這樣一來，計算出來的雜湊值發生碰撞的機會就會下降。

測驗 2

題目

LeetCode 82. 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;
}

作答

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

延伸問題: 1. 嘗試避免遞迴，寫出同樣作用的程式碼

不是很簡潔。再想想。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode *deleteDuplicates(struct ListNode* head)
{
    if (!head || !head->next)
        return head;
    
    struct ListNode *dummy = malloc(sizeof(struct ListNode));
    struct ListNode *prev = NULL, *node = dummy, *next = head;
    bool is_dup = false;
    
    dummy->next = head;
    dummy->val = 1000;
    
    while (node && next) {
        while (node && next && node->val == next->val) {
            struct ListNode *x = next;
            node->next = next->next;
            next = next->next;
            free(x);
            is_dup = true;
        }
        
        if (is_dup) {
            struct ListNode *x = node;
            prev->next = node->next;
            node = node->next;
            if (next)
                next = next->next;
            free(x);
            is_dup = false;
        } else {
            prev = node;
            node = node->next;
            next = next->next;           
        }

    }
    
    head = dummy->next;
    free(dummy);
    
    return head;
}

延伸問題: 2. 以類似 Linux 核心的 circular doubly-linked list 改寫，撰寫遞迴和迭代 (iterative) 的程式碼

迭代 (iterative)

struct list_head *q_delete_dup_iter(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return head;

    struct list_head *prev = head->next, *node = head->next->next;
    bool dup_flag = false;

    while (prev != head && node != head) {
        element_t *prev_element = list_entry(prev, element_t, list);
        element_t *node_element = list_entry(node, element_t, list);

        while (node != head &&
               strcmp(prev_element->value, node_element->value) == 0) {
            dup_flag = true;
            list_del(node);
            q_release_element(node_element);
            node = prev->next;
            node_element = list_entry(node, element_t, list);
        }

        if (dup_flag) {
            dup_flag = false;
            list_del(prev);
            q_release_element(prev_element);
        }

        prev = node;
        node = node->next;
    }

    return head;
}

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return false;

    q_delete_dup_iter(head);

    return true;
}

遞迴
- 尚未完成

struct list_head *q_delete_dup_rec(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return head;

    if (!list_is_singular(head) && strcmp(list_entry(head, element_t, list)->value, list_entry(head->next, element_t, list)->value) == 0) {
        while (!list_is_singular(head) && strcmp(list_entry(head, element_t, list)->value, list_entry(head->next, element_t, list)->value) == 0) {
            struct list_head *x = head;
            head = q_delete_dup_rec(head->next);
            list_del(x);
            //free(x);
            return head;
        }
    }
    head->next = q_delete_dup_rec(head->next);
    return head;

}

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return false;

    q_delete_dup_rec(head);

    return true;
}

測驗 3

題目

LeetCode 146. LRU Cache

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

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

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

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

void lRUCachePut(LRUCache *obj, int key, int 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;
        }
    }

    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->key = key;
    list_add(&lru->dlink, &obj->dhead);
    list_add(&lru->hlink, &obj->hheads[hash]);
    lru->value = value;
}

作答

MMM1 = list_for_each_entry_safe
MMM2 = list_for_each_entry
MMM3 = list_for_each_entry
MMM4 = list_last_entry

延伸問題:

1. 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
2. 在 Linux 核心找出 LRU 相關程式碼並探討

延伸問題: 1. 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作

資料結構(LRUCache, LRUNode)
- LRUCache 是描述 cache 的資料結構。
  - capacity 為 LRU cache 能容納的節點數。
  - count 為目前 LRU cache 內的節點數目。當 count 等於 capacity 時，表示 LRU cache 已滿。
- LRUNode 是描述 cache 中資料節點的資料結構。
  - key 與 value 為資料節點的 key 與 value。
```
typedef struct {
    int capacity, count;             
    struct list_head dhead, hheads[];
} LRUCache;
  
typedef struct {
    int key, value;
    struct list_head hlink, dlink;
} LRUNode;
```
LRUCache *lRUCacheCreate(int capacity)
```
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;
}
```
- lRUCacheCreate 會配置記憶體空間給一個型態為 LRUCache 的 object 並對它做初始化。 LRUCache 會產生如下圖所示的 object。
- LRUCache object 中有兩 dhead 與 hhead 兩種雙向鏈結串列。
  - dhead 是一個以資料節點被存取的時間序為排列順序的雙向鏈結串列。最近被存取過的資料節點會被放在 dhead 所指向之雙向鏈結串列的最前端。最早被存取過的資料節點則被放在 dhead 所指向之雙向鏈結串列的尾端。
  - hhead 則是一個 hash table。被插入的資料節點的 key 所對應的 hash 為 k 時，則此資料節點會被插入 hhead[k] 所指向的雙向鏈結串列中。
  - 在 LRU cache 中的一個節點，會同時被 dhead 與 hhead[k] 所管理。
void lRUCachePut(LRUCache *obj, int key, int value)
```
void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    list_for_each_entry (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            lru->value = value;
            return;
        }
    }

    if (obj->count == obj->capacity) {
        lru = list_last_entry(&obj->dhead, LRUNode, dlink);
        list_del(&lru->dlink);
        list_del(&lru->hlink);
    } else {
        lru = malloc(sizeof(LRUNode));
        obj->count++;
    }
    lru->key = key;
    list_add(&lru->dlink, &obj->dhead);
    list_add(&lru->hlink, &obj->hheads[hash]);
    lru->value = value;
}
```
- 當有資料要插入 LRU cache 時，在第4行算出 key 的 hash。這裡的實作是用取餘數的方式算 hash。
- 假設 LRU cache 此時的狀況如下:
  1. LRU cache 的 capacity 為 3。
  2. 已存在的資料節點的 key 為 0， value 為 0。
  3. 要插入的資料的 key 為 1， value 為 1。
- 則這筆資料會被插入 hheads[1] 所指向的雙線鏈結串列中。
  * 第 18~19 行配置記憶體空間給一個型態為 LRUNode 的 object。並增加 LRU cache 中的節點個數 (count)。
  * 第 22 行將新節點插入 dhead 所指向之雙向鏈結串列的最前端 (原本最前端的節點為 key = 0, value = 0)。
  * 第 23 行將新節點插入hhead[1] 所指向的雙向鏈結串列的最前端 (原本為 empty)。
  * 第 21 行將新節點的 key 更新為 1。
  * 第 24 行將新節點的 value 更新為 1。
- 討論第二種狀況如下圖所示。再插入一個 key = 3, value = 6 的節點。
- 第 5~11 行的 for 迴圈會找到已存在 hhash[0] 所指的雙向鏈結串列中那個 key = 3 的節點。然後操作 dhead 所指向的雙向鏈結串列，將此資料節點移到此雙向鏈結串列的第一個節點，再將此節點的 value 更新為 6。但 hhead[0] 所指之雙向鏈結串列維持不動。完成狀況如下圖所示。
- 再討論第三種情況，如下圖所示。此時， LRU cache 已滿。若要再插入一個新節點 (key = 4, value = 4)。
- 則第 13 行的 if 條件式成立，並執行第 14~16 行。將 dhead 所指之雙向鏈結串列的最後一個節點 (key = 6, value = 6)自 ddhead 與 hhead[0] 雙向鏈結串列中移除(但不刪除)，並以 lru 指標指向此被刪除的節點。
- 接著執行第 21~24 行。
  - 第此 lru 所指向的節點的 key 更新為 4。
  - 將此 lru 所指向的節點插入 dhead 所指向之雙向鏈結串列的最前端。
  - 然後再將此 lru 所指向的節點插入hhead[1] 所指向的雙向鏈結串列的最前端 (原本為 empty)。
  - 第此 lru 所指向的節點的 value 更新為 4。
  - 最後如下圖所示。
- 以上討論的幾種情況已涵蓋整個 lRUCachePut() 的主要程式碼。

int lRUCacheGet(LRUCache *obj, int key)












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

假設目前 LRU cache 的狀況如下圖所示。
若要找的資料節點的 key 不為 0、3 或 6，則返回 -1。
若要找的資料節點的 key 為 6。則第 5~10 行的 for 迴圈會在 hhead[0] 所指的雙向鏈結串列中找到最後一個節點的 key 為 6。然後將此節點移到 ddhead 所指的雙向鏈結串列的第一個節點。完成後，如下圖所示。

void lRUCacheFree(LRUCache *obj)
```
void lRUCacheFree(LRUCache *obj)
{       
    LRUNode *lru, *n;
    list_for_each_entry_safe (lru, n, &obj->dhead, dlink) {
        list_del(&lru->dlink);
        free(lru);
    }
    free(obj); 
}  
```
- lRUCacheFree 會釋放 LRU cache 所占用的記憶體空間。
- 由先前對 lRUCachePut() 與 lRUCacheGet() 的討論得知，ddhead 所指的雙向鏈結串列涵蓋整個 LRU cache 的所有資料節點。所以只要遍歷此雙向鏈結串，並逐一移除節點，再釋放節點記憶體空間，就可以清除所有的資料節點。這就是第 4~7 行 for 迴圈所做的事。
- 最後於第 8 行將 LRU cache 所占用的記憶體空間釋放掉。

延伸問題: 2. 在 Linux 核心找出 LRU 相關程式碼並探討

working

測驗 4

題目

LeetCode 128. Longest Consecutive Sequence
































































  #include <stdio.h>
#include <stdlib.h>
#include "list.h"

struct seq_node {
    int num;
    struct list_head link;
};                                                                                                                                                            
            
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;
}

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

    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

延伸問題:

1. 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
2. 嘗試用 Linux 核心風格的 hash table 重新實作上述程式碼

延伸問題: 1. 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作

題目中的程式碼是以數學上集合 (set) 的概念搭配 hash table 實作的解法。這裡的 hash talbe 是第 25 行的 heads 指標所指向的 object。此 hash table 可容納的節點數為 nums 陣列的大小。
第 10~19 行的 find() 函式負責在 hash table 中尋找指定的數值 (nums[i])。若此數值存在 hash table 中，則返回該資料節點。否則，返回 NULL。
第 27~28 行的 for 迴圈對 hash table 進行初始化。假設 nums = [100,4,1,200,1,100,3,2] ，則初始化後的 hash table 如下圖所示。

第 30~37 行的 for 迴圈把 nums 陣列中的所有元素插入 hash table 中。在插入的過程中，若發現 nums[i] 已經存在 hash table 中，則不予插入。所以 nums[4] 與 nums[5] 會被跳過。這段程式碼完成後，hash table 的狀態如下圖所示。

第 39~61 行的 for 迴圈從頭開始逐一走訪 nums 陣列中的每個元素。而針對某一元素 nums[i]，在第 43~60 行的 while 迴圈中，以 nums[i] 為中心，在 hash table 中向左方找 nusm[i] - 1，向右方找 nums[i] + 1。
- 如上圖所示，若 nums 陣列中有連續數列 (consequtive sequence)，則會分布在 nums[i] 的左右兩邊。所以只要在 hash table 中找到連續數列中的任一元素，就可以找到其他元素。進而算出最長連續數列的長度。
- 且第 49~52 與 54~57 行的 while 迴圈中，會把找到的連續數列自 hash table 中移除。所以，某個連續數列的長度只會被計算一次。

延伸問題: 2. 嘗試用 Linux 核心風格的 hash table 重新實作上述程式碼

working

答案卷

2022 年 Linux 核心設計第 1 週隨堂測驗 (A)
2022 年 Linux 核心設計第 1 週隨堂測驗 (B)

2022q1 Homework1 (quiz1)

測驗 1

作答

延伸題目: 1. 解釋上述程式碼運作原理

map_init() (第 10~25 行)

map_add() (第 61~77 行)

map_get() 與 find_key() (第 45~59 行)

map_deinit() (第 79~106 行)

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

測驗 2

題目

作答

延伸問題: 1. 嘗試避免遞迴，寫出同樣作用的程式碼

延伸問題: 2. 以類似 Linux 核心的 circular doubly-linked list 改寫，撰寫遞迴和迭代 (iterative) 的程式碼

測驗 3

題目

作答

延伸問題: 1. 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作

延伸問題: 2. 在 Linux 核心找出 LRU 相關程式碼並探討

測驗 4

題目

作答

延伸問題: 1. 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作

延伸問題: 2. 嘗試用 Linux 核心風格的 hash table 重新實作上述程式碼

答案卷

`map_init()` (第 10~25 行)

`map_add()` (第 61~77 行)

`map_get()` 與 `find_key()` (第 45~59 行)

`map_deinit()` (第 79~106 行)

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