ELFHash详细分析

// ELF Hash Function

unsigned int ELFHash(char *str)

{

       unsigned int hash = 0;

       unsigned int x = 0;

 

       while (*str)
      {
             hash = (hash << 4) + (*str++);//hash左移4位，当前字符ASCII存入hash
             if ((x = hash & 0xF0000000L) != 0)

             {//如果最高的四位不为0，则说明字符多余7个，如果不处理，再加第九个字符时，第一个字符会被移出，因此要有如下处理。

           //该处理，如果对于字符串(a-z 或者A-Z)就会仅仅影响5-8位，否则会影响5-31位，因为C语言使用的算数移位

           hash ^= (x >> 24);

                //清空28-31位。

           hash &= ~x;

            }

       }

      //返回一个符号位为0的数，即丢弃最高位，以免函数外产生影响。(我们可以考虑，如果只有字符，符号位不可能为负)
     return (hash & 0×7FFFFFFF);

}

 

  ELFhash函数在UNIX系统V 版本4中的“可执行链接格式”( Executable and Linking Format，即ELF )中会用到，ELF文件格式用于存储可执行文件与目标文件。ELFhash函数是对字符串的散列。它对于长字符串和短字符串都很有效，字符串中每个字符都有同样的作用，它巧妙地对字符的ASCII编码值进行计算，ELFhash函数对于能够比较均匀地把字符串分布在散列表中。

 

   说明：unsigned int hash = 0; unsigned int x = 0;
          定义无符号整数，在进行位运算时无需考虑符号位的影响，左移和右移均补位0

        int 为32位 ，即  00000000  00000000   00000000   00000000 

 

            hash = (hash << 4) + (*str++);//hash左移4位，当前字符ASCII存入hash

            例，如果hash为2时，（hash << 4）操作后，放大16（2的4次方）倍；然后加上(*str++)，(*str++)为8位的字符，所以对4-7为有影响，其后四位添到hash左移空出的四位。

             if ((x = hash & 0xF0000000L) != 0)
             0xF0000000L表示28-31位这4位是1，后28为均为0的长整型（L），该操作的结果为x保存hash 的高4位

             & 按位与 如果两个相应的二进制位都为1，则该位的结果值为1，否则为0

             hash ^= (x >> 24);
             首先x的拷贝进行右移23位的操作，然后与hash进行异或操作。

             右移后X的值为 00000000 00000000 00000000  ****0000  ;****为hash的高四位

             ^ 按位异或 若参加运算的两个二进制位值相同则为0，否则为1

 

             hash &= ~x;
             有 if ((x = hash & 0xF0000000L) != 0)，x保存着hash的高四位，虽然进行右移操作，但不会改变x的值，而是对副本进行操作。经过hash &= ~x;  hash的高四位被清空。

 

            //返回一个符号位为0的数，即丢弃最高位，以免函数外产生影响。(我们可以考虑，如果只有字符，符号位不可能为负)
             return (hash & 0×7FFFFFFF);

参考：http://www.yqshare.com/elfhash.html