散列表节

散列表由用于符号表访问的 Elf32_Word 或 Elf64_Word 目标文件组成。SHT_HASH 节提供了此散列表。与散列关联的符号表在散列表节头的 sh_link 项中指定。下图中使用了标签来帮助说明散列表的结构，但这些标签不属于规范的一部分。

图 7–4 符号散列表

bucket 数组包含 nbucket 项，chain 数组包含 nchain 项。索引从 0 开始。bucket 和 chain 都包含符号表索引。链表的各项与符号表对应。符号表的项数应等于 nchain，因此符号表索引也可选择链表的各项。

接受符号名称的散列函数会返回一个值，用于计算 bucket 索引。因此，如果散列函数为某个名称返回值 x，则 bucket [x% nbucket] 将会计算出索引 y。此索引为符号表和链表的索引。如果符号表项不是需要的名称，则 chain[y] 将使用相同的散列值计算出符号表的下一项。

在所选符号表项具有需要的名称或者 chain 项包含值 STN_UNDEF 之前，可以遵循 chain 链接。

散列函数如下所示：

unsigned long

elf_Hash(const unsigned char *name)

{

    unsigned long h = 0, g;

 

	    while (*name)

	    {

		     h = (h << 4) + *name++;

		     if (g = h & 0xf0000000)

			      h ^= g >> 24;

				   h &= ~g;

	    }

	    return h;

}