4. 5.1哈希表

哈希表是进行快速查找的一种有效的组织方式。Linu在进程中引入的哈希表叫做pidhash，在include/linux/sched.h中定义如下：

#define PIDHASH_SZ (4096 >> 2)

extern struct task_struct *pidhash[PIDHASH_SZ];

#define pid_hashfn(x) ((((x) >> 8) ^ (x)) & (PIDHASH_SZ - 1))

其中，PIDHASH_SZ为表中元素的个数，表中的元素是指向task_struct结构的指针。pid_hashfn为哈希函数，把进程的PID转换为表的索引。通过这个函数，可以把进程的PID均匀地散列在它们的域（0 到 PID_MAX-1）中。

在数据结构课程中我们已经了解到，哈希函数并不总能确保PID与表的索引一一对应，两个不同的PID散列到相同的索引称为冲突。

Linux利用链地址法来处理冲突的PID：也就是说，每一表项是由冲突的PID组成的双向链表，这种链表是由task_struct 结构中的pidhash_next 和 pidhash_pprev域实现的，同一链表中pid的大小由小到大排列。如图4.3所示。

图4.3 链地址法处理冲突时的哈希表

在哈希表pidhash中插入和删除一个进程时可以调用hash_ pid( ) 和unhash_ pid( )函数。对于一个给定的pid，可以通过find_task_by_pid()函数快速地找到对应的进程：

static inline struct task_struct *find_task_by_pid(int pid)

{

struct task_struct *p, **htable = &pidhash[pid_hashfn(pid)];

for(p = *htable; p && p->pid != pid; p = p->pidhash_next)

;

return p;

}