ELFHash
面试遇到过一个问题，怎样用字符串怎样用HASH码保存？查了一些资料，做了一个实验，是这样的。#include<stdio.h>unsignedint ELFHash( char * str) ;void print_bin(unsigned int n) ;void print_bin2(unsigned int n) ;int main(char* arg[]){ char * str = "12345678" ; printf("String:%s",str) ; unsigned int te = ELFHash(str) ; printf("\n%s'hash code:",str) ; print_bin(te) ; return 0 ;}unsignedint ELFHash( char * str){//定义无符号整数，在进行位运算时无需考虑符号位的影响，左移和右移均补位0;int 为32位 ，即 0000000000000000 00000000 00000000unsignedinthash= 0 ;unsignedintx = 0 ;while( * str){ printf("\ns1:") ; print_bin(hash) ; hash=(hash << 4 )+( * str ++ ); //hash值左移4位加上一个字符.例，如果hash为2时，（hash << 4）操作后，放大16（2的4次方）倍；然后加上(*str++)，(*str++)为8位的字符，所以对4-7为有影响，其后四位添到hash左移空出的四位。 printf("\ns2:") ; print_bin(hash) ; if((x=hash& 0xF0000000L )!= 0 )//判断hash值的高4位是否不为0，因为不为0时需要下面特殊处理，否则上面一步的左移4位会把这高四位给移走，造成信息丢失 {/*0xF0000000L表示28-31位这4位是1，后28为均为0的长整型（L），该操作的结果为x保存hash 的高4位& 按位与 如果两个相应的二进制位都为1，则该位的结果值为1，否则为0*/ hash^=(x>> 24 ); //把刚才的高4位跟hash的低5-8位异或 printf("\ns3:") ; print_bin(hash) ;/*hash ^= (x >> 24);首先x的拷贝进行右移23位的操作，然后与hash进行异或操作。右移后X的值为 00000000 00000000 00000000****0000;****为hash的高四位^ 按位异或 若参加运算的两个二进制位值相同则为0，否则为1*/ hash&= ~ x; //把高4位清0/*hash &= ~x;有 if ((x = hash & 0xF0000000L) != 0)，x保存着hash的高四位，虽然进行右移操作，但不会改变x的值，而是对副本进行操作。经过hash &= ~x; hash的高四位被清空。*/ printf("\ns4:") ; print_bin(hash) ; }}return(hash& 0x7FFFFFFF ); //希望hash值是一个非负数//返回一个符号位为0的数，即丢弃最高位，以免函数外产生影响。(我们可以考虑，如果只有字符，符号位不可能为负)}void print_bin(unsigned int n){ if(n < 2 ){printf("%d",n);} else{ print_bin(n/2) ; printf("%d",n%2) ; }} 结果：
http://dl.iteye.com/upload/attachment/0072/2843/88e1514b-a7f9-329b-a6f3-e720d172d9e8.bmp
注：字符1的ASCII码为：0x31 .
页:
[1]