2022q1 Homework (quiz1)

contributed by < hankluo6 >

第 1 週測驗題

測驗 1

運作原理

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

map_add 將新的節點加入到 hash 中，find_key 先從 hash 檢查該 key 是否已經存在，如果已經存在則直接回傳，尚未存在則分配新的記憶體放置 data。故可知 AAA 及 BBB 為將新的節點連接到 hash 上的 linked list，且為插入到 linked list 的前端。

• add new item

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

map_deinit 釋放所有 hash 的記憶體，for 迴圈遍歷所有 hash entry，內部在一個一個把 linked list 上的節點及其 data 釋放。在遍歷每個節點時，同時透過指標的指標更改 head->firt 及 next->prev。

• 刪除的節點 n 為 data1。

• 將 pprev 的指標內指向的值(map.ht[0].first)設為 next；next 的 prev 設為 pprev 指標的指標，並把 n 的 prev 及 next 設為 NULL，最後釋放。

Linux hashtable

DEFINE_HASHTABLE & DECLARE_HASHTABLE

#define DEFINE_HASHTABLE(name, bits)						\
	struct hlist_head name[1 << (bits)] =					\
			{ [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }

#define DECLARE_HASHTABLE(name, bits)                                   	\
	struct hlist_head name[1 << (bits)]

以 hlist_head 當作每個 hash table 上每個 bucket 的 list，其中不用 list_node 的原因為不需要用到 circular linked list。bits 決定需要 hash table 的大小。

特別要注意的為初始化 name 時使用的 ... 為 GCC extension 的 Designated Initializers，可以一次初始化所有 index 為 HLIST_HEAD_INIT。

HLIST_HEAD_INIT 定義在 list.h 內，及初始化 first 為 NULL。

hash_init

static inline void __hash_init(struct hlist_head *ht, unsigned int sz)
{
	unsigned int i;

	for (i = 0; i < sz; i++)
		INIT_HLIST_HEAD(&ht[i]);
}

#define hash_init(hashtable) __hash_init(hashtable, HASH_SIZE(hashtable))

專門將 DECLARE_HASTABLE 宣告的 hash table 初始化，作用與 DEFINE_HASTABLE 相同。

hash_add & hash_del

#define hash_add(hashtable, node, key)						\
	hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])

static inline void hash_del(struct hlist_node *node)
{
	hlist_del_init(node);
}

add 與 del 都為呼叫 hlist API，其實作皆與 list_head 相似。

hash_for_each

#define hash_for_each(name, bkt, obj, member)				\
	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
			(bkt)++)\
		hlist_for_each_entry(obj, &name[bkt], member)

遍歷 hash table 所有的 entry，bkt 表示 bucket，每一次迴圈透過 hlist_for_each_entry 遍歷這個 bucket 內的 linked list。

GOLDEN_RATIO

#define GOLDEN_RATIO_32 0x61C88647
#define GOLDEN_RATIO_64 0x61C8864680B583EBull

註解中的 phi = (sqrt(5)-1)/2 指的是 ${\varphi }^{-1}$，為 golden ratio 的倒數。

• $\text{0x61C88647}=\text{1640531527}=2^{32}\times {\varphi }^{-1}=2^{32}\times \frac{\sqrt{5}-1}{2}$
• $\text{0x61C8864680B583EB}=\text{7046029254386353842}\approx 2^{64}\times {\varphi }^{-2}=2^{64}\times \frac{3-\sqrt{5}}{2}$

任意數乘上這兩個數再取其高位元可以呈現好的數值分布。在連續的數值中，利用這種 Fibonacci Hashing 方法可以將 hash 後對應的值分散到其他 hash value 的值之間 (將最大區間以 golden ratio 分割的點)。

而現實生活上的 keys 值分布常常會有某種數值分布，類似 $\{K,K+d,K+2d,...,K+td\}$，例如字串集合 $\{"PART1","PART2","PART3"\}$，這種情況利用此種 hash function 的行為就如同計算 $h(0),h(1),h(2)$，便能將 key 值映射到沒有使用過的 value，減少 collision 的機率。

假設 $\theta$ 為一有理數，要將 $\{\theta ,2\theta ,3\theta ,...,n\theta \}$ 的小數部分放到 $[0,1]$ 之間，則會發現 $(n+1)\theta$ 放置的位置會在由前面的點分割成的線段中最長的線段，而當 $\theta$ 過大或過小時 (接近 0 或 1)，產生的分布區間便會由小而大，並不是均勻分布。

可證明能產生較好的分布的數值為 ${\varphi }^{-1}$ 及 ${\varphi }^{-2}$ (Knuth vol 3, section 6.4, exercise 9.)，故選擇這兩個數計算 hash。

• Reference: The Art of Computer Programming, section 6.4

測驗 2

運作原理

COND1

• head->next && head->val == head->next->val

COND2

• head->next && head->val == head->next->val

根據註解可知道第二個 if 用來刪除重複的節點，故 COND1 應為判斷是否有重複的值。在 if block 裡面最後回傳 head->next，可知道中間 while 迴圈需跳過相同值的節點，最後停在所有有著相同值的節點中的最後一個節點，得出 COND2。

改寫

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

    struct ListNode *newhead = malloc(sizeof(struct ListNode));
    newhead->next = head;
    struct ListNode *prev = newhead;
    
    while (head) {
        if (head->next && head->val == head->next->val) {
            while (head->next && head->val == head->next->val) {
                head = head->next;
            }
            prev->next = head->next;
        } else {
            prev = prev->next;
        }
        head = head->next;
    }
    
    return newhead->next;
}

測驗 3

運作原理

MM1

• list_for_each_entry_safe

MM2

• list_for_each_entry

MM3

• list_for_each_entry

MM4

• list_last_entry

LRU 由兩個部分組成

• dhead：為 doubly-linked list，用來取得 Least Recently Used 的 node，靠近頭端部分表示存取時間與當前時間越近，靠近尾端則越遠。
• hheads：為 hash map，用來儲存 key 及 value 的資訊，以 key % capacity 當作 hash function。

GET 操作時，從對應的 hash 值的 list 中尋找，如果有找到，透過 list_move 將該 node 移到 dhead 的頭端，表示最近使用。故 MM2 為 list_for_each_entry 遍歷對應 hash 上的 list。

PUT 操作時，先檢查該 key 是否有存在 hash map 當中，故 MM3 與 MM2 相同，如果不存在，則要新建一個新的 node，此時若 LRU 已滿，必須剔除掉最久沒使用的節點，該節點及為 dhead 的 tail，故 MM4 為 list_last_entry。建立完新的節點後，再放到 dhead 及對應的 hhead 頭端。

CREATE 操作時，必須將所有 list_head 透過 INIT_LIST_HEAD 初始化，把相對應的 next 與 prev 欄位設定，list 相關巨集才能正確使用。

FREE 操作時，因為每個存在於 hash map 的 node 都與 dhead 鏈結，所以只要遍歷 dhead 釋放所有節點即可。

• 初始化，capacity 為 3

digraph linked_list{
    rankdir = LR;
    node [shape = record];
    node0 [label = "<f0> hheads[0]<style></style> | <f1> hheads[1] |<f2> hheads[2]",height=1.2];
    "dhead"[height=0.4];
    { rank="same"; node0; "dhead" }
}
Error: bad label format <f0> hheads[0]<style></style> | <f1> hheads[1] |<f2> hheads[2]

• push item1 (hash value: 0)

digraph linked_list{
    rankdir = LR;
    node [shape = record];
    node0 [label = "<f0> hheads[0] | <f1> hheads[1] |<f2> hheads[2]",height=1.2];
    "dhead"[height=0.4];
    "item1:hlink"[height=0.4];
    "item1:dlink"[height=0.4];
    node0:f0->"item1:hlink";
    "dhead"->"item1:dlink";
    { rank="same"; node0; "dhead" }
    
    
}
Error: ̓

• push item2 (hash value: 1)，新建立的 node 放到 list 的頭端

digraph linked_list{
    rankdir = LR;
    node [shape = record];
    node0 [label = "<f0> hheads[0] | <f1> hheads[1] |<f2> hheads[2]",height=1.2];
    "dhead"[height=0.4];
    "item1:dlink"[height=0.4];
    "item2:dlink"[height=0.4];
    node1 [label = "<f0> item1:hlink | <f1> item2:hlink",height=0.8];
    node0:f0->node1:f0;
    node0:f1->node1:f1;
    "dhead"->"item2:dlink"->"item1:dlink";
    { rank="same"; node0; "dhead" }
}
Error: ̓

• push item3 (hash value: 0)

digraph linked_list{
    rankdir = LR;
    node [shape = record];
    node0 [label = "<f0> hheads[0] | <f1> hheads[1] |<f2> hheads[2]",height=1.2];
    "dhead"[height=0.4];
    "item1:hlink"[height=0.4];
    "item1:dlink"[height=0.4];
    "item2:dlink"[height=0.4];
    "item3:dlink"[height=0.4];
    node1 [label = "<f0> item3:hlink | <f1> item2:hlink",height=0.8];
    node0:f0->node1:f0->"item1:hlink";
    node0:f1->node1:f1;
    "dhead"->"item3:dlink"->"item2:dlink"->"item1:dlink";
    { rank="same"; node0; "dhead" }
}
Error: <ۂ

• push item4 (hash value: 2)，因為 LRU 空間已滿，將最久未使用的節點 (item1) 移除

digraph linked_list{
    rankdir = LR;
    node [shape = record];
    node0 [label = "<f0> hheads[0] | <f1> hheads[1] |<f2> hheads[2]",height=1.2];
    "dhead"[height=0.4];
    "item3:dlink"[height=0.4];
    "item2:dlink"[height=0.4];
    "item4:dlink"[height=0.4];
    node1 [label = "<f0> item3:hlink | <f1> item2:hlink | <f2> item4:hlink",height=1.2];
    node0:f0->node1:f0;
    node0:f1->node1:f1;
    node0:f2->node1:f2;
    "dhead"->"item4:dlink"->"item3:dlink"->"item2:dlink";
    { rank="same"; node0; "dhead" }
}
Error: <ۂ

item:dlink 與 item:hlink 為同一個物件中的不同成員

---

測驗 4

運作原理

LLL

• --left

RRR

• ++right

longestConsecutive 內的第二個 for 迴圈將 nums 陣列中出現的所有數字以 hash map 存起。第三個 for 迴圈遍歷整個陣列，每次迴圈有個 current value 當作基準點，left 表示往小於 current value 的方向從 hash map 中尋找；right 表示往大於 current value 的方向尋找。因為要尋找連續的序列，故每次都以加一或減一的值尋找，得出 --left 及 ++right。每找到一個數字與 current value 為連續序列，則將其從 hash map 中移除，下次迴圈選到相同序列內的數就不需要重新計算。

改寫

struct seq_node {
    int num;
    struct hlist_head link;
};                                                                                                                                                            
            
static struct seq_node *find(int num, int size, struct hlist_head *map)
{   
    struct seq_node *node;
    int hash = num < 0 ? -num % size : num % size;
    hash_for_each_possible (node, map, link) {
        if (node->num == num)
            return node;
    }
    return NULL;
}

int longestConsecutive(int *nums, int n_size)
{
    DEFINE_HASHTABLE(map, n_size);
    
    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];
            hash_add(map, node, 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;
            hash_del(&node->link);

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

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

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

    return length;
}