问理解linux内核中的PID哈希表

EN

内核将所有进程存储在任务列表中。任务列表是一个循环双链接列表。这意味着列表中的每个元素都有指向下一个元素和前一个元素的指针。第一项链接到最后一项，反之亦然。从概念上说，它可以看作是一个圆圈。

在每个任务中都有一个进程描述符，它保存您感兴趣的PID信息。他们的意思是，通常情况下，要找到你想要杀死的进程，你必须遍历任务列表，查看每个任务的进程描述符的PID字段，直到你找到你想要的任务。您不能通过PID直接引用它们，因为您不知道它们在内存中的位置。这就是链接的意义所在。这样，任务列表就不需要占用连续的内存空间。使插入和删除可以简单地通过重新链接。每个进程都知道它在内存中的位置。它可以利用它在内存中的位置跟踪链接，直到找到它正在寻找的过程。

这叫做线性时间搜索。最坏的情况是，给定N个元素，需要N个操作才能找到结果。在描述效率时，你总是假设最坏的情况。如果您有大量的数据，线性时间在搜索时是相当低效的。

他们的意思是，有4个表可以通过散列函数将PID (取决于目标)放入其中，检查结果所在位置的表，并准确地知道任务列表中任务的内存地址。那是一次手术。这是哈希函数的工作，以减轻冲突。但最坏的情况就是所谓的恒定时间。快多了。

找一个简单的数字是不可能的。您正在遍历位于不同内存位置的数据结构。如果您有一个C数组，则这些数组是在连续内存空间的堆栈中预先分配的。因此，在这种情况下，数组索引号将指示您立即需要的内存块。但这里不是这样的。这些数据结构既不是静态的，也不是预先分配的。因此，您需要某种方式从内存地址跳转到内存地址。这就是这些数据结构要解决的问题。

我希望这能把事情弄清楚。

资料来源：table http://www.makelinux.net/books/lkd2/app01lev1sec1