|DT_GNU_HASH是GNU兼容软件中GNU系统使用的ELF更好的哈希表，也就是几乎所有linux发行版的GCC或clang编译的几乎所有程序中都使用的ELF哈希表。
它的问题是，除了GNU binutils和glibc源代码之外，没有任何地方记录dt_gnu_hash。您可以阅读源代码来获取一些英特尔，或者阅读邮件列表存档中带有补丁的电子邮件(Re：GNU_HASH部分格式是一个很好的格式)。这些是你唯一可以尝试找到这件事真相的地方。
当然，网络上也有一些文章，人们试图把它拆散开来。就像这个一样。
这篇文章也不想成为终极真理。但我将尝试涵盖GNU哈希表的所有内容，并解释其工作的方方面面。
在进一步阅读之前，请确保您了解ELF中的符号表和字符串表是什么。此外，您可能想要阅读我以前的文章“ELF：通过dt_hash进行符号查找”，以了解执行符号查找的标准(90年代左右)方式。
DT_GNU_HASH与标准的DT_HASH没有任何共同之处，只是服务于相同的目的。它有自己的散列函数，自己的布局，它增加了对符号表的限制，并包含一个额外的布隆过滤器来提前停止查找丢失的符号。
让我们从散列函数开始。它可以在bfd_elf_gnu_hash或dl_new_hash中找到。
uint32_t(const uint8_t*name){uint32_t h=5381；for(；*name；name++){h=(h<；<；5)+h+*name；}return h；}gnu_hash("；"；)==0x00001505gnu_hash("；printf"；)==0x156b2bb8gnu_hash。flapenguin.me"；)==0x8ae9f18e
struct{uint32_t nbucket；uint32_t symoffset；uint32_t bloom_size；uint32_t bloom_shift；uint64_t bloom[bloom_size]；/*uint32_t 32位二进制文件*/uint32_t bucket[nbucket]；uint32_t chain[]；}；
Bloom Filter用于提前停止查找丢失的符号。BLOOM_SIZE、BLOOM_SHIFT和BLOOM顾名思义，它们都是结构的一部分。
对于不同的ELFCLASS二进制文件(由ELF标识中的EI_CLASS字段定义)，Bloom过滤器的行为略有不同。让将ELFCLASS_BITS定义为64位二进制(ELFCLASS64)和32位二进制(ELFCLASS32)。
在执行符号查找之前，获取bloom[(hash/ELFCLASS_BITS)%bloom_size]。如果设置了BITS HASH%ELFCLASS_BITS和(HASH&>；&gT；BLOOM_SHIFT)%ELFCLASS_BITS，则符号可能在哈希表中，也可能不在哈希表中，您应该继续定期查找桶和链。但是如果没有设置至少一个比特，则在哈希表中肯定不存在符号。
dt_hash为符号表的每个元素包含一个元素。这会导致空间浪费，因为STN_UNDEF和其他一些符号在哈希表中，但从未被查找过。GNU哈希表允许跳过符号表开头的第一个symoffset符号。
与dt_hash中的相同，根据符号的散列，将符号放入nbucket存储桶中的一个中。具体地说，每个符号都应该放入hash%nbucket桶中。
GNU哈希表中的链与DT_HASH中的奇怪链表完全不同，它们是具有相同索引的符号的连续哈希序列(记住，链索引相对于符号表是按symoffset移位的)。链元素中的最后一位被丢弃，取而代之地用于指示链的结束。如果设置了它，则该元素是链中的最后一个元素。
桶数组保存链中第一个符号的索引。请注意，这些不是链数组的索引。它的索引将是bucket[foobar]-symoffset。
作为连续序列的链意味着必须连续存储同一桶内的符号。符号表中存储桶的顺序并不重要，但通常它们是按升序存储的。
虽然看起来无关紧要，但在符号表上创建这样的限制会带来很大的好处：哈希表现在可以存储相同32位内的符号的几乎全部散列(没有最低位)。这允许链接器在比较字符串之前比较散列。此外，因为DT_GNU_HASH需要对符号表进行排序，而DT_HASH不需要，所以您可以将两者都放入一个二进制文件中。这样，标准链接器和GNU链接器都可以在其中查找符号。
我获取了与ELF中相同的符号：通过DT_HASH进行符号查找，并从它们创建了DT_GNU_HASH表。该示例针对的是64位ELF二进制文件，而对于32位，您将需要重新计算Bloom字和位。
nBuckets=4(因为我决定将有四个桶)symoffset=1(STN_UNDEF不是哈希表的一部分)Bloom_Size=2(因为我决定16字节的Bloom Filter就足够了)Bloom_Shift=5(再次，仅仅因为我可以)ix bucket[ix]链中第一个符号的名称-0 1cfsetiSpeed 1 5 uselib 2 8 freellocal 3 13 getspen请注意：-符号表按存储桶链排序-[ix]与哈希相同，但设置/清除了最低位符号表|GNU哈希表|name=。hash|ix nbucket chain[ix]word#0#1-|-0<；STN_UNDEF>；|1cfsetiSpeed 830acc54|0 0830acc54 1 20 34 2 strsigna 90f1e4b0|1 0 90f1e4b0 0 48 37 3 hcreate_4c7e3240|2 0 4c7e3240 1 0 18 4 endrpcen b6c44714|3 0 b6c44715 0 20 56 5 uselib 2124d3e9|4 1 2124d3e8 1 41 31 6 getttyffen。f07b2a7b|12 3 f07b2a7a 1 59 1914 pthread_mutex_lock 4f152227|13 3 4f152226 0 39 1715 getopt_long_onl 57b1584f|14 3 57b1584f 1 15 2布隆过滤器：位#56 48 40 32 24 16 8 0xx..x.xx.xxx.x xx.。x.x.xx.x..x.x.。.x..x.。.。.xx.x..x.。……x……。……x.x。……x……。xx..x.xx.xxx.x xx.。x.x.xx.xOr为两个`uint64_t`值：cb1dc0ad22120003 48040a04cb1dc0ad。
了解这些规则，并建立一个表格，让我们试着用手找出一些符号。
请注意，在比较散列时，左侧和右侧都设置了最低位。
正在查找"；strsigna"；(hash=0x90f1e4b0)在布隆过滤器中检查字0以查找位48和37的哈希表可能包含从ix=1开始的符号比较散列：(Chain)0x830acc55==0x90f1e4b1错误的散列肯定不是"；strsigna"；移动到下一个符号比较散列：(Chain)0x90f1e4b1==0x90f1e4b1==0x90f1e4b1==0x90f1e4b1==0x90f1e4b1==0x90f1e4b1==0x90f1e4b1。比较在索引2处找到的字符串："；strsigna"；=="；strsigna"；
正在查找"；foobar"；(hash=0xfde460be)在布隆过滤器中检查字0以查找不在布隆过滤器中的位62和5未找到
查找"；vLoun"；(hash=0x1081e019)在布隆过滤器中检查字0以查找位25和0的哈希表可能包含从ix=5开始的符号比较哈希：(Chain)0x2124d3e9==0x1081e019错误的哈希肯定不是"；vLoun"；正在移动到下一个符号比较哈希：(Chain)0xfff51839==0x1081e019。比较字符串："；umoun"；=="；vLoun"；仅此存储桶中最后一个符号的散列冲突未找到。
实现要比dt_hash的实现稍微复杂一些，但是上面的例子应该是不言而喻的。
/*不同架构的符号结构大小不同。*那些实际上应该根据输入二进制的ELFCLASS进行选择，*但为简单起见，我将它们保留为typedefs和定义。*/tyfinf Elf64_Sym Elf_Sym；tyfinf bloom_el_t uint64_t；/*32位二进制：tyfinf Elf32_Sym Elf_Sym；tyfinf bloom_el_t uint32_t；#定义ELFCLASS_BITS 32*/const Elf_Sym*(const char*strtab，/*string table*/const Elf_Sym*symtab，/*Symbol table*/const uint32_t*hashtab，/*hash table*/const char*name/*要查找的符号*/){const uint32_t namehash=gnu_hash(Name)；const uint32_t nbucket kets=hh。const uint32_t bloom_shift=hashtab[3]；const bloom_el_t*bloom=(void*)&；hashtab[4]；const uint32_t*bucket=(void*)&；bloom[bloom_size]；const uint32_t*chain=&；bucket[nbucket]；bloom_el_t word=bloom[(namehash/ELFCLASS_BITS)%bloom。(namehash%ELFCLASS_BITS)|(Bloom_El_T)1<；<；((namehash>；>；bloom_Shift)%ELFCLASS_BITS)；/*如果至少没有设置一位，则肯定缺少符号。*/if((word&；ask)！=ask){return null；}uint32_t syMix=bucket[namehash%nbucket]；if(syMix<；symoffset){return null；}/*循环通过链。*/While(True){const char*symname=strtab+symtab[syMix].st_name；const uint32_t hash=chain[syMix-symoffset]；if((namehash|1)==(hash|1)&；&；strcmp(name，symname)==0){return&；symtab[syMix]；}/*chain以最低位设置为1的元素结束。*/if。
由于我不知道的原因，DT_GNU_HASH中缺少符号总数。要获得符号的总数，您必须找到索引最高的链元素。为此，首先找到一个从最高索引(max(Bucket))开始的链，然后将链遍历到它的末端(while((chain[ix-symoffset]&；1)==0)ix++；)。
如果您只能访问动态程序信息，例如，如果您的程序是动态链接器或ELF加载器，这可能会很有用。但是，如果您有权访问小节标题，您可以简单地计算小节标题中的符号总数：只需将小节大小除以条目大小即可。
DT_GNU_HASH是一种比DT_HASH更好的结构。遗憾的是它没有标准化，因为每个使用ELF的系统都使用DT_GNU_HASH。正如最初的GNU binutils补丁中指出的那样，它将链接时间缩短了高达50%。这是加载时间的两倍！考虑到一个普通的C++共享库导出和导入了多少符号，以及这些符号名称的大小(所有名称空间、类型和模板参数都适合最终的符号名称)，模糊的DT_GNU_HASH可以让您的应用程序尽可能快地启动。