HackMD
2022q1 Homework1 (quiz1)
contributed by < Chao-Shun-Cheng >
測驗 1
程式碼解釋
map_init
map_init 會建立 ht 會指向 2^n * sizeof(struct hlist_head) 的連續記憶體空間。
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;
}
首先第七行用 malloc 建立 hashtable 所需要的連續記憶體空間，空間大小為 sizeof(struct hlist_head)
map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
再來就是進行初始化的部分，使得 hashtalbe 都沒指向任何內容。
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
(map->ht)[i].first = NULL;
find_key
find_key 有兩個輸入參數，分別是 map 跟 key ，會從 map 去尋找有沒有符合的 key ，有找到就會回傳對應的 hash_key ，否則就回傳 NULL。
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;
}
首先可以看到第二行，hash 是雜湊函式，會利用 key 去找到 hash table 中對應的 hlist_head
struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
#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);
}
不同的 key 經過雜湊函式計算後可能得到同樣的結果，所以會在用一個 for 迴圈去看每個結果的 key 是不是跟 input 的 key 一樣，一樣的話就代表有找到，會回傳找到的 hash_key。第三到第七行就是在進行這個功能。
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;
}
其中 container_of 可以從一個結構體中的每個成員，去得到結構體的最前面的地址，詳細可以參考Linux 核心原始程式碼巨集: container_of
map_get
map_get 搭配 find_key 去使用，目的是用來查看是否已經存在。
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 會將資料存進 hash_table 當中。
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;
}
首先看到第三行，如果 key 已經存在 hash_table 當中，就不用再加進去 hash_table。
struct hash_key *kn = find_key(map, key);
if (kn)
return;
如果找不到則會利用 malloc 分配一個 hash_key 的空間，並且初始化。
kn = malloc(sizeof(struct hash_key));
kn->key = key, kn->data = data;
接著利用雜湊函式 hash 找出要放置在 hash_table 的位置，並用 h 指著 hlist_head。另外 n 指向剛剛建立的 hash_key 當中的 node 、first 則指向 h 當中的第一個 node。
struct hlist_head *h = &map->ht[hash(key, map->bits)];
struct hlist_node *n = &kn->node, *first = h->first;
緊接著要將剛剛建立的 node 插入進 list 的頭，以下是對應的操作。n->next 要指向原本的 first ，所以 AAA 是 n->next = first ；再來要去要去看原本到底有沒有 first ，如果本來有，則要調整原本 first 的 pprev (13、14 行)；最後要將插入的 node 的 pprev 指回去 list ，所以 BBB 是 n->pprev = &h->first。
AAA; // n->next = first;
if (first)
first->pprev = &n->next;
h->first = n;
BBB; // n->pprev = &h->first;
twoSum
twoSum 利用上面所建立的 hash table 的操作來進行實作。
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 初始化 map 所需要的空間 (第 3 行)，以及用 malloc 建立回傳答案所需要的空間 (第 5 行)。
map_t *map = map_init(10);
*returnSize = 0;
int *ret = malloc(sizeof(int) * 2);
接下來是利用一個 for 迴圈去建立 hash_table 與查找 key。如果 key 可以從 hash table 中找到就回傳答案，如果找不到，就將 key 加進去 hash_table 當中。
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);
}
hash table 如何使用在 twoSum 可以參考 2022q1 第 1 週測驗題之說明。
測驗 2
程式碼解釋
deleteDuplicates
deleteDuplicates 要可以將所以重複出現的 Node 都 delete 掉，以下是實作方式。
struct ListNode *deleteDuplicates(struct ListNode *head)
{
if (!head)
return NULL;
if (COND1) { // head->next && head->val == head->next->val
/* Remove all duplicate numbers */
while (COND2) // head->next && head->val == head->next->val
head = head->next;
return deleteDuplicates(head->next);
}
head->next = deleteDuplicates(head->next);
return head;
}
首先可以注意到我們需要去比較下一個 node 與現在的 node 是不是一樣的值，所以要先確定有下一個 node ，再去看下一個 node 的值，因此 COND1 就會是 head->next && head->val == head->next->val ；緊接著可以看到有提示 /* Remove all duplicate numbers */ ，因此可以知道 while 迴圈會去把相同的 node 都 delete 掉。因此 while 的條件就會是要有下一個 node 並且值是一樣的，因此 COND2 就是 head->next && head->val == head->next->val。
測驗 3
程式碼解釋
lRUCacheCreate
lRUCacheCreate 會依據 capacity 的大小，建立出相對應的空間，並且將 dhead 與 hheads 進行初始化。
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;
}
其中在第三行的 sizeof(*obj) 其實與 sizeof(LRUCache) 是一樣的。
lRUCacheFree
lRUCacheFree 會將 obj->dhead 之所有 Node 給釋放掉。因此 MM1 會是 list_for_each_entry_safe 用來去歷遍所有的 Node entry。
void lRUCacheFree(LRUCache *obj)
{
LRUNode *lru, *n;
MMM1 (lru, n, &obj->dhead, dlink) {
list_del(&lru->dlink);
free(lru);
}
free(obj);
}
lRUCacheGet
lRUCacheGet 會利用 key 去看目前的 hheads 當中有無一樣的 key ，如果有就代表有存在 cache 當中。因此 MM2 是要用來歷遍 bucket 的，所以會是 list_for_each_entry。
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;
}
lRUCachePut
lRUCachePut 可以分成三個部分，首先是已經存在 cache 當中，要把 node 更新到 list 最前面；再來就是如果 cache 容量已經滿了，要把最舊的 node 移除，並且放進新的 node；最後就是還有空間，可以直接放進去新的 node。
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;
}
可以發現這邊就是要找尋是不是已經在 cache 當中，因此要歷遍 bucket 去看有沒有符合的 key。因此 MM3 是 list_for_each_entry。假如有找到就會進行第七行，將這個 node 移至 list 最前方。
MMM3 (lru, &obj->hheads[hash], hlink) {
if (lru->key == key) {
list_move(&lru->dlink, &obj->dhead);
lru->value = value;
return;
}
}
這邊則是判斷還有沒有容量，假如容量不夠，就要移除最舊的 node，所以 MM4 會是 list_last_entry ，用來移除 list 中最後面的 node。
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++;
}
測驗 4
程式碼解釋
find
find 會去從 bucket 當中去尋找是否有對應的數字 num。
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;
}
longestConsecutive
longestConsecutive 是利用 hash table 將資料先分成不同 bucket 再找出最長的連續數字。
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;
}
首先看到這個 for 迴圈，會把每個數字經過 hash fuction 計算後，放進對應的 bucket 當中。
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 迴圈去看每個 node。第 23 ~ 26 行會把 node 的 num 提出來並且移出 bucket；緊接在再往 num + 1 與 num - 1 去尋找是否有對應的 node，有的話就繼續找，直到不連續為止。因此可以得知 LLL 是 --num 而 RRR 是 ++num。
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;
}
}
