看懂ELFHash

17-02-27 来源：[db:作者]

收藏我要投稿

// 该ELF Hash Function将任意长度的字符串，最后变成28位二进制长度。
unsigned int ELFHash(char *str)
{
unsigned int hash = 0;
unsigned int x = 0;
while (*str)
{
hash = (hash << 4) + (*str++);
if ((x = hash & 0xF0000000L) != 0)
{
//因为1-4位刚刚存储了新加入到字符，所以不能>>28，如果是右移小于24位也是可以的吧？？
hash ^= (x >> 24);
hash &= ~x;
}
}
return (hash & 0x7FFFFFFF);
}

（1）现在编译器中int和long int型都是32位。

（2）hash左移4位，把当前的ASCII存入hash低8位，单纯的二进制加的关系，前四位进行了一次杂糅，是为了更好的均匀性。

（3）为了使每个字符都被哈希到，因为初始化是0，在高四位不为0时，将高四位与低5-8位进行杂糅。下一步高四位被吃掉，新字符加入到低位。

举例：加入ASCII 1000 1000 的字符

初始h：0000 0000 0000 0000 0000 0000 0000 0000

加入一个字符：0000 0000 0000 0000 0000 0000 1000 1000

加入二个字符： 0000 0000 0000 0000 0000 1000 1000 0000

+ 1000 1000

0000 0000 0000 0000 0000 1001 0000 1000

加入三个字符： 0000 0000 0000 0000 1001 0000 1000 0000

+ 1000 1000

0000 0000 0000 0000 1001 0001 0000 1000

balabala

所以加入七个字符时，高四位将会非0.开始进行if{}处理

（4）假如最后结果是h为1100 1100 1100 1100 1100 1100 1100 1100

x = hash & 0xF0000000L，取高四位结果是1100 0000 0000 0000 0000 0000 0000 0000

x >> 24 ,右移24位0000 0000 0000 0000 0000 0000 1100 0000

^异或符号 h为1100 1100 1100 1100 1100 1100 1100 1100

因为0与A（0||1）异或都是A，所以异或结果是h除低5-8位是新的杂糅，其余位保持原样。

高四位已经杂糅到后面，下一步清零（左移），然后加入新字符。

所以我猜右移4~24位都是可以得吧？

（5）最后的结果应该是28，最后一次hash & 0x7FFFFFFF高位清0。

点击复制链接与好友分享!回本站首页