linux內核hash表的使用

Linux內核中最常用的兩種表

一種為lish，一種雙向鏈表

一種為hlist,一種哈希鏈表

本文從代碼和實際運用角度上解釋以下內核如何使用哈希鏈表

先上哈希list的結構

先從應用的角度上觀察hash鏈表

內核查找進程控制塊是通過hash鏈表的方法查找的

內核申請了一片空間來存儲hash_list

hlist的個數為pidhash_size（具體體系結構不一樣，算法也很復雜，直接在內核中printk打印出來就好了）

對每個節點進行初始化 將next 和 pprev置為NULL

這裡我節選了alloc_pid函數中將根據upid的nr和ns將pid_chain插入到指定的hash_hlist中，顯然這裡的hash算法是pid_hashfn

具體hashfn是如何計算這裡暫不分析，這是個純數學的東西，我要搞懂的是內核的hlist原理

內核如何去尋找pid的

根據nr和ns，利用pid_hashfn算法，快速定位找到自己所在的hash_list

然後遍歷這個hash_list，匹配nr 和 ns，找到自己的pid

至於pprev是指向前節點的next指針

通過修改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這個算法