哈希函数——ELF HASH和CRC HASH解析

哈希函数——ELF HASH和CRC HASH解析

 一.  简介

     Hash应用中，字符串是最为常见的关键字，应用非常普通，现在的程序设计语言中基本上都提供了字符串hash表的支持。字符串hash函数非常多，常见的主要有Simple_hash, RS_hash, JS_hash, PJW_hash, ELF_hash, BKDR_hash, SDBM_hash, DJB_hash, AP_hash, CRC_hash等。

二.  ELF HASH函数解析

      

// 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 & 0x7FFFFFFF);

}

三.  CRC HASH函数解析

/* CRC Hash Function */
unsigned int CRC_hash(char *str)
{
    unsigned int        nleft   = strlen(str);//得到字符串的长度，以char为单位。
    unsigned long long  sum     = 0;
    unsigned short int *w       = (unsigned short int *)str; //将char*转换为short int*
    unsigned short int  answer  = 0;

    /*
     * Our algorithm is simple, using a 32 bit accumulator (sum), we add
     * sequential 16 bit words to it, and at the end, fold back all the
     * carry bits from the top 16 bits into the lower 16 bits.
     */
    while ( nleft > 1 ) {
        sum += *w++;
        nleft -= 2; //nleft是以char型计数的，是short int的2倍
    }
    /*
     * mop up an odd byte, if necessary(处理奇数情况)
     */
    if ( 1 == nleft ) {
        *( unsigned char * )( &answer ) = *( unsigned char * )w ;//去w的低8bit
        sum += answer;
    }
    /*
     * add back carry outs from top 16 bits to low 16 bits
     * add hi 16 to low 16
     */
    sum = ( sum >> 16 ) + ( sum & 0xFFFF );
    /* add carry */
    sum += ( sum >> 16 );
    /* truncate to 16 bits */
    answer = ~sum;

    return (answer & 0xFFFFFFFF);
}