“了解 Linux 内核第 3 版”一书的这一部分解释说，内核不是搜索进程列表来查找 PID，而是引入了 4 个哈希表，每个哈希表对应一种类型的 PID。
据我了解，表的每个元素都是 PID 的散列。但这如何使搜索变得容易？例如，给定一个 PID，是否存在 4 个哈希表，因为仅在该 PID 类型的哈希中搜索比在所有 PID 中搜索更快？另外，为什么散列有帮助？搜索哈希不是比搜索简单数字更难吗？
那么，这 4 个表中的一个表中的条目到底是什么？它们是过程描述符吗？我理解他们。并且在每个进程描述符中，都有一个结构链接到处于相同状态的其他类似进程，例如，处于同一组和相同状态的进程。
是这个吗？
最佳答案
内核将所有进程存储在任务列表中。任务列表是一个循环双向链表。这意味着列表中的每个元素都有指向下一个元素和前一个元素的指针。第一项链接到最后一项，反之亦然。它在概念上可以被认为是一个圆圈。
在每个任务中都有一个进程描述符，其中包含您感兴趣的 PID 信息。他们的意思是，通常情况下，要找到您要杀死的进程，您必须遍历任务列表，查看每个任务的每个进程描述符的 PID 字段，直到找到您要查找的那个。你不能通过 PID 直接引用它们，因为你不知道它在内存中的什么位置。这就是链接的用途。这样任务列表就不需要占用连续的内存空间。只需通过重新链接就可以进行插入和删除。每个进程都知道 IT 在内存中的位置。它可以使用它在内存中的位置来跟踪链接，直到找到它正在寻找的进程。
这就是所谓的线性时间搜索。最坏的情况是，给定 N 个元素，需要 N 次操作才能找到结果。在描述效率时，您总是假设平均最坏情况。在搜索是否有大量数据时，线性时间效率非常低。
他们的意思是，有 4 个表，您可以在其中通过哈希函数放置您的 PID(取决于您的预期目标)，检查结果所在位置的表，并确切知道该表的内存地址任务列表中的任务。那是一个操作。散列函数的工作是减轻冲突。但平均最坏的情况，这称为恒定时间。快得多。
没有搜索简单数字这样的东西。您正在遍历位于不同内存位置的数据结构。如果你有一个 C 数组，它们会预先分配在堆栈中的连续内存空间中。因此，在那种情况下，您的数组索引号将指向您立即需要的内存块。但这里不是这种情况。这些数据结构既不是静态的也不是预先分配的。所以你需要一些方法从一个内存地址跳转到另一个内存地址。这些数据结构解决的问题。
我希望一切都清楚了。
资料来源: https://en.wikipedia.org/wiki/Hash_table http://www.makelinux.net/books/lkd2/app01lev1sec1
关于c - 理解linux内核中的PID哈希表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41335509/