Linux內核中最常用的兩種表
一種為lish，一種雙向鏈表
一種為hlist,一種哈希鏈表
本文從代碼和實際運用角度上解釋以下內核如何使用哈希鏈表
先上哈希list的結構
內核查找進程控制塊是通過hash鏈表的方法查找的
hlist的個數為pidhash_size（具體體系結構不一樣，算法也很復雜，直接在內核中printk打印出來就好了）
對每個節點進行初始化 將next 和 pprev置為NULL
具體hashfn是如何計算這裡暫不分析，這是個純數學的東西，我要搞懂的是內核的hlist原理
根據nr和ns，利用pid_hashfn算法，快速定位找到自己所在的hash_list
然後遍歷這個hash_list，匹配nr 和 ns，找到自己的pid
通過修改pprev在頭部插入新節點的時候，能修改頭部的指針，具體參考上圖的最後一句
為什麼不用雙向鏈表，而只用first來做單向鏈表，是因為在hash鏈表中，hashlist的數量很大，在初始化過程中就占用了內存空見，為了節約空間將hashlist做為單向鏈表
沖突解決辦法
內核利用pid的nr和ns來將所有關鍵字相同的pid連在一起來解決hash沖突
通過hashfn算法計算出nr和ns關鍵字所在的hashlist，如果這個hashlist有多個pid就進行遍歷，找到nr和ns相等的pid
為什麼呢，因為hashfn 可能因為不同的nr和ns計算出相同的散列地址，進而把nr和ns不同的pid放入一個hashlist
總結：
絕大多數情況下，一個hashlist就只有一個pid
沖突的情況下，一個hashlist有多個pid，再進行遍歷，比較nr和ns，找出我們需要的那個
在不沖突的情況下，查找pid的效率是O（1），沖突的情況下是O（n），主要看hashfn這個算法