Linux kernel programming - hash

 最近看到這篇: 俠盜列車手 if 循環 19.8 億次

 深覺 Hash 的重要性

 Leet code 的第一題 Two Sum, 時間複雜度若要縮減到 O(1), 可以用 Hash Table, 

 例如 Approach 3: One-pass Hash Table

 在 Linux kernel 的這座寶山中, 也已經有神人實作 Hash table,

 這邊以 Linux kernel 的 Hash table 為例, 來實現 Two Sum 看看. 

Ref: https://liujunming.top/2018/03/12/linux-kernel%E4%B8%ADHList%E5%92%8CHashtable/

程式: github

Linux kernel 設計兩個 struct  : hlist_head 和 hlist_node

hlist_head 為 hash table, 用 hash 函式 (hash_32 或 hash_64) 選擇陣列位置

陣列大小為 1 << bits , (2^bits) , 可以視樣本大小設定 bits, 當 bits 大於 32 時,

則需要選擇改用 hash_64 來計算

實際資料存在 hlist_node 的 list 中, 當兩個資料碰在同一個hash table 陣列位置時, 

則用 hlist_node 的 list 繼續延展. 可以發現 hlist_node 的 頭指標為 **pprev, 

這個設計可以讓 hlist 在做 del 時, 可以節省所需要操作的動作.

https://github.com/neojou/leetcode-pub/blob/main/library/hashmap.c

https://github.com/neojou/leetcode-pub/tree/main/1-two-sum 

這樣透過 hash 就可以讓 two sum 時間複雜度降至 O(1)

而 Linux kernel code 不虧是小而美, 這 code 就算移植到其他 embedded system 中

也很適合.

Runtime: 0 ms, faster than 100.00% of C online submissions for Two Sum.

Memory Usage: 6.9 MB, less than 5.48% of C online submissions for Two Sum.

PS: 另外 Linux kernel 有 IDR 機制專做映射

      https://www.kernel.org/doc/html/latest/core-api/idr.html

      https://blog.popkx.com/linux-learning-20-mapping-idr-mechanism-in-kernel/