作者zstar (zstar)
看板LinuxDev
标题[问题] 为何 process list 使用质数乘法 hash？
时间Thu Jan 22 12:12:53 2009
在 Understanding the Linux kernel 3rd, 章节 3.2.3.1 读到
为了有效率的从 PID 找出 process descriptor，因而使用 hash table
将 32 bit 的 PID 排进 2048 个entry 的表格。
hash function 是：
index = PID * 0x9e370001 >> 21
书中解释 0x9e370001 是选择接近 2^32 黄金分割的质数 --> 魔术常数
我对於 hash 及 linux kernel都只有初浅知识，所以不太了解：
为何不简单的取 PID 的 LSB 11 bits当 index？
能指点其中原因吗？
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 203.73.49.155
※ 编辑: zstar 来自: 203.73.49.155 (01/22 13:09)
1F：推 zwai:也许这样hash table会比较均匀? 01/22 22:55
2F：→ zstar:想了几天後，我想，这个hash应该不是很critical的部分， 01/24 11:16
3F：→ zstar:乘"魔术质数"可让碰撞发生条件不规则一些，不用太深究~~ 01/24 11:20