在Linux内核中，需要从进程的PID推导出对应的进程描述符指针。当然，顺序扫描进程链表并检查进程描述符的pid字段是可行的，但是相当低效。为了加快查找，Linux内核引入了pidhash哈希表来进行快速定位。

内核初始化期间（在pidhash_init()函数中）动态地为哈希表分配pid_hash数组。 

unsigned long megabytes = nr_kernel_pages>> (20 - PAGE_SHIFT);

pidhash_shift= max(4, fls(megabytes * 4));

pidhash_shift= min(12, pidhash_shift);

pidhash_size= 1 << pidhash_shift;

变量pidhash_size表示哈希表索引的长度，pidhash_shift是pidhash_size值所占的位数。这两个变量值在内核启动日志信息（例如：/var/log/messages文件）中查得到，以下是笔者机器上打印的消息。

PID hash table entries: 2048 (order: 11, 8192 bytes)

通过日志信息，可知本系统的pidhash_shift值为11，pidhash_size值为211=2048，即哈希表的长度为2048（个元素）。每个元素是链表头指针，一个元素占4个字节，因此整个哈希表占用8192字节的内存空间。Linux用pid_hashfn宏把PID转化为哈希表索引 #define pid_hashfn(nr, ns)  \ 

   hash_long((unsigned long)nr + (unsigned long)ns, pidhash_shift) 

其中hash_long 宏在32位体系结构中的定义如下所示： 

#define GOLDEN_RATIO_PRIME_32 0x9e370001UL

#define hash_long(val, bits) hash_32(val, bits) 

static inline u32 hash_32(u32 val, unsigned int bits) 

{ 

  /* On some cpus multiply is faster, on others gcc will do shifts */ 

  u32 hash = val * GOLDEN_RATIO_PRIME_32; 

  /* High bits are more random, so use them. */ 

  return hash >> (32 - bits);

在Linux中采用链地址法来处理哈希冲突，每一个表项是由冲突的进程描述符组成的双向链表

,如图：

通过哈希表查找进程描述符的函数find_pid_ns()如下所示：

structpid*find_pid_ns(intnr,structpid_namespace*ns)

{

  structhlist_node*elem;

  structupid*pnr;

  hlist_for_each_entry_rcu(pnr,elem,

  &pid_hash[pid_hashfn(nr, ns)], pid_chain)

  {

  if (pnr->nr== nr&& pnr->ns == ns)

  return container_of(pnr,structpid, numbers[ns->level]);

  }

  return NULL;

}

通过这个小例子介绍了嵌入式系统中哈希表的使用，很有效！