散列表节

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

图 12-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 int h = 0, g;

        while (*name)
        {
                h = (h << 4) + *name++;
                if (g = h & 0xf0000000)
                        h ^= g >> 24;
                h &= ~g;
        }
        return h;
}