# 2022q1 Homework1 (quiz1)
contributed by < `Kevin-Shih` >
## 測驗一 LeetCode 1 Two Sum
### 所用到的結構
- map: hash table
```c
typedef struct {
int bits; // 用於紀錄 hash table 大小為 2^bits
struct hlist_head *ht;
} map_t;
```
- hlist_node、hlist_head
```c
struct hlist_node { struct hlist_node *next, **pprev; };
struct hlist_head { struct hlist_node *first; };
```
- hash_key:
```c
struct hash_key {
int key; // key = target - nums[i]
void *data; // nums[i] 的 index `i`
struct hlist_node node; // 用於串接 hlist
};
```
先分開來看各個 function 的用途：
### 建立大小為 2^bits 的 hash table
```c
// 計算 hash table 大小為 2^bits
#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;
// malloc 2^map->bits 個 hlist_head 的大小給 hash table
map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
// 成功建立 hash table 時初始化所有 first
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;
}
```
### 尋找 key 相同的節點 kn
若有找到則回傳該節點，否則回傳 NULL。
- map_t *map: 對應的 hash table
- int key: 要尋找的 key
```c
static struct hash_key *find_key(map_t *map, int key) {
struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
// 走訪 ht[hash(key, map->bits)] 中所有 chain 起來的 list node
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 後的地址為 `2`：
```graphviz
digraph "hash list" {
node [shape=record];
rankdir=LR;
a [label=" map-\>ht | {[0] | [0].first } | {[1] | [1].first } | {[2] | <2>[2].first } | ...}"];
b [label="{ <pprev> pprev| <key> 1 | <next> next}"];
c [label="{ <pprev> pprev| <key> 5 | <next> next}"];
d [label="{ <pprev> pprev| <key> -2 | <next> next}"];
null;
p;
a:2:c -> b:key:n [arrowhead=vee];
b:pprev:w -> a:2:e [arrowhead=vee, tailclip=false, color="#808080"];
b:next:n -> c:key:n [arrowhead=vee, tailclip=false];
c:pprev:s -> b:next:s [arrowhead=vee, tailclip=false, color="#808080"];
c:next:n -> d:key:n [arrowhead=vee, tailclip=false];
d:pprev:s -> c:next:s [arrowhead=vee, tailclip=false, color="#808080"];
d:next:e -> null:w [arrowhead=vee, tailclip=false];
p -> b:key:s [arrowhead=vee];
}
```
`find_key()` 會以 pointer `p` 如上圖依序走訪 `1`、`5`、`-2`，並比較 `key` 值是否與輸入的 `@key` 相等，若相等則回傳該 `hash_key` 的位址。
### 取得 key 相同的節點的 data
```c
void *map_get(map_t *map, int key)
{
// 呼叫前述的 find_key 取得 key 與 @key 相同的節點 address
struct hash_key *kn = find_key(map, key);
// 當 kn 有找到 (kn != NULL) 時取得對應 data 的 address
return kn ? kn->data : NULL;
}
```
### 將新的 node 加入 hash table
會將新的 node `kn` 插到原先的 fisrt 前面。
- AAA = `n->next = first;`
- BBB = `n->prev = &h->first;`
```c=
void map_add(map_t *map, int key, void *data)
{
// 如果 hash table 中該 @key 已有 key 相等的節點
// 表示找到答案了，故 return
struct hash_key *kn = find_key(map, key);
if (kn)
return;
// 為新的節點 malloc 並填入 key 及 data (答案的 index)
kn = malloc(sizeof(struct hash_key));
kn->key = key, kn->data = data;
// 將該節點接上 hash table 對應的 bucket h
struct hlist_head *h = &map->ht[hash(key, map->bits)];
struct hlist_node *n = &kn->node, *first = h->first;
n->next = first; // AAA's answer
if (first)
first->pprev = &n->next;
h->first = n;
n->prev = &h->first; // BBB's answer
}
```
```graphviz
digraph "hash list" {
node [shape=record];
rankdir=LR;
a [label=" map-\>ht | {[0] | [0].first } | {[1] | [1].first } | {[2] | <2>[2].first } | ...}"];
b [label="<key> 1 | { <pprev> pprev | <next> next }"];
c [label="<key> 5 | { <pprev> pprev | <next> next }"];
d [label="<key> -2 | { <pprev> pprev | <next> next }"];
null;
n;
first;
{rank=min;first}
n:e -> b:key:n [arrowhead=vee];
first:e -> c:key:n [arrowhead=vee];
a:2:e -> b:key:w [arrowhead=vee, weight = 100];
b:pprev:w -> a:2:e [arrowhead=vee, tailclip=false, color="#808080"];
b:next:e -> c:key [arrowhead=vee, tailclip=false];
c:pprev:s -> b:next:s [arrowhead=vee, tailclip=false, color="#808080", weight = 100];
c:next:e -> d:key [arrowhead=vee, tailclip=false];
d:pprev:s -> c:next:s [arrowhead=vee, tailclip=false, color="#808080", weight = 100];
d:next:e -> null:w [arrowhead=vee, tailclip=false];
}
```
- #17 : `n->next` 接到原先的第一個 node ，`first` 可以為 `NULL`。
- #18~19 : 如果原先的第一個 node 存在，將其 `pprev` 指回 `n`。
:::info
#19 的 first->pprev = &n->next;
是將 `first->pprev` 指向存放 `n->next` 這個 pointer 的位址，而非 `n->next` 這個 pointer 中存放的位址。 因此該行作用相當於將 `first->pprev` 指回 `n`。 (用 `containerof()` 即可取得 `n` 的位址)
:::
- #20 : hash table 中將對應的 `head->first` 指向新的 "first" 也就是 `n`。
- #21 : 將 `n->pprev` 指向 `head`。
:::info
同 #19 的 first->pprev = &n->next;
#21 將 `n->pprev` 指向存放 `&h->first` 這個 pointer 的位址。 (用 `containerof()` 即可取得 `head` 的位址)
:::
看懂 #18~20 的是將新的節點 n 放在 hlist 中的第一個位置就很好推論出 #17 的 AAA 是將 `n->next` 指向原先的 `first`、#21 的 BBB 則是將 `n->pprev` 指向 `&head->first`。
### 清除 hash table
```c
void map_deinit(map_t *map)
{
// 如果 hash table 不存在就 return
if (!map)
return;
// 對 hash table 中的每個 bucket
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
struct hlist_head *head = &map->ht[i];
// 依序走訪 bucket 中的 node
for (struct hlist_node *p = head->first; p;) {
// kn 指向 p 對應的 entry
struct hash_key *kn = container_of(p, struct hash_key, node);
struct hlist_node *n = p;
// p 移到下個 node
p = p->next;
// TODO: 這是什麼？
if (!n->pprev) /* unhashed */
goto bail;
// 將 n 移出 hlist
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next; // 前一個 node 的 next 接到 n 的 next
if (next)
next->pprev = pprev;
n->next = NULL, n->pprev = NULL;
// 釋放 kn(n) 所佔用的資源
bail:
free(kn->data);
free(kn);
}
}
// 釋放 hash table 本身
free(map);
}
```
### 執行 Two Sum
- int *nums: 給定的 int 陣列
- int numsSize: int 陣列的大小
- int target: 目標的總和
- int *returnSize: 成功找到時為 2，失敗時為 0
```c
int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
// 建立 1024 個 bucket 的 hash table
map_t *map = map_init(10);
*returnSize = 0;
int *ret = malloc(sizeof(int) * 2);
// 回傳值的 array malloc 失敗，清除 hash table 後 return
if (!ret)
goto bail;
/*
* 若 target - nums[i] 的 key 不存在於 hash table 中，
* 則將 nums[i] 作為 key, i 作為 data(index) 加入 hash table，
* 當下次有 target - nums[i] 的數查找 hash table 時即可找到答案。
*
* 若 target - nums[i] 的 key 存在於 hash table 中，
* 則對 map_get 回傳的 int pointer 取值存入答案 ret[1]，
* 另一個答案則是目前的 index i 存入 ret[0] 並將 returnSize
* 設為 2 表示成功找到，接著釋放 hash table 並回傳 ret 即可。
*/
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;
}
```
### GOLDEN_RATIO_PRIME
節錄自[linux/hash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h):
```c
/*
* The "GOLDEN_RATIO_PRIME" is used in ifs/btrfs/brtfs_inode.h and
* fs/inode.c. It's not actually prime any more (the previous primes
* were actively bad for hashing), but the name remains.
*/
#if BITS_PER_LONG == 32
#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_32
#define hash_long(val, bits) hash_32(val, bits)
#elif BITS_PER_LONG == 64
#define hash_long(val, bits) hash_64(val, bits)
#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_64
#else
#error Wordsize not 32 or 64
#endif
```
```c
#define GOLDEN_RATIO_32 0x61C88647
#define GOLDEN_RATIO_64 0x61C8864680B583EBull
```
可以發現 GOLDEN_RATIO_PRIME 在 32 bit 系統(unsigned long 為 32 bit)上為 `0x61C88647` 而在 64 bit 系統上為 `0x61C8864680B583EBull`，兩者皆非時會 error。
Sign in with Wallet
Connect another wallet