hash.c

几种c语言的hash算法

#include <stdio.h>
#include <fcntl.h>
#include <sys/time.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <sys/time.h>
#include <time.h>
#include <math.h>


	struct timeval tpstart,tpend;
	float  timeuse;
#define HASH_VALUE 0x9E3779B9	//((sqrt(5)-1)/2)*(2^32)
// RS Hash Function
unsigned long RSHash(char* str)
{
    unsigned long b = 378551;
    unsigned long a = 63689;
    unsigned long hash = 0;

    while (*str)
    {
        hash = hash * a + (*str++);
        a *= b;
    }

    return (hash & 0x7FFFFFFF);
} 
 
// JS Hash Function
unsigned long JSHash(char* str)
{
    unsigned long hash = 1315423911;

    while (*str)
    {
        hash ^= ((hash << 5) + (*str++) + (hash >> 2));
    }

    return (hash & 0x7FFFFFFF);
}
 
// P.J.Weinberger Hash Function
unsigned long PJWHash(char* str)
{
    unsigned long BitsInUnignedInt = (unsigned long)(sizeof(unsigned long) * 8);
    unsigned long ThreeQuarters    = (unsigned long)((BitsInUnignedInt * 3) / 4);
    unsigned long OneEighth        = (unsigned long)(BitsInUnignedInt / 8);

    unsigned long HighBits         = (unsigned long)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
    unsigned long hash             = 0;
    unsigned long test             = 0;

    while (*str)
    {
        hash = (hash << OneEighth) + (*str++);
        if ((test = hash & HighBits) != 0)
        {
            hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
        }
    }

    //return (hash & 0x7FFFFFFF);
    return (hash);
} 
 
// ELF Hash Function
unsigned long ELFHash(char* str)
{
    unsigned long hash = 0;
    unsigned long x    = 0;

    while (*str)
    {
    		//printf("%c,%d ", *str, *str);
        hash = (hash << 4) + (*str++);        
        if ((x = hash & 0xF0000000L) != 0)
        {
            hash ^= (x >> 24);
            hash &= ~x;
        }
    }

    //return (hash & 0x7FFFFFFF);
    return (hash);
}

// BKDR Hash Function
unsigned long BKDRHash(char* str)
{
    unsigned long seed = 131;  //  31 131 1313 13131 131313 etc..
    unsigned long hash = 0;

    while (*str)
    {
        hash = hash * seed + (*str++);
    }

    return (hash & 0x7FFFFFFF);
}

// SDBM Hash Function
unsigned long SDBMHash(char* str)
{
    unsigned long hash = 0;

    while (*str)
    {
        hash = (*str++) + (hash << 6) + (hash << 16) - hash;
    }

    return (hash & 0x7FFFFFFF);
}

// DJB Hash Function
unsigned long DJBHash(char* str)
{
    unsigned long hash = 5381;

    while (*str)
    {
        hash += (hash << 5) + (*str++);
    }

    return (hash & 0x7FFFFFFF);
}

// AP Hash Function
unsigned long APHash(char* str)
{
    unsigned long hash = 0;
    int i;

    for (i = 0; *str; i++)
    {
        if ((i & 1) == 0)
        {
            hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
        }
        else
        {
            hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
        }
    }

    return (hash & 0x7FFFFFFF);
}

//------------------------------------------------------------------
//16进制转相同数值的10进制数
//------------------------------------------------------------------
unsigned char  bcd_hex_1byte(unsigned char value) 
{
  	unsigned char rtn_value;
  	rtn_value  = value/16;
  	rtn_value *= 10;
  	rtn_value += value&0x0f;
  	return rtn_value;
}
#define ulong unsigned long 
unsigned long MyHash(unsigned char *str)
{
	int i;
	unsigned long temp, value;
	
	temp = 0;
	value = 0;
	
	for (i = 0; i < 4; i++)
		temp = (ulong)str[3]<<24 | str[2]<<16 | str[1]<<8 | str[0];
	for (i = 4; i < 8; i++)
		value = (ulong)str[7]<<24 | str[6]<<16 | str[5]<<8 | str[4];
		
	//for (i = 0; i < 255; i ++)	
	//{
			value += temp;
			value *= HASH_VALUE;
			printf("--------0x%x--------\n", value);
			value >>= 15;
			printf("--------0x%x-------\n", value);
			//temp++;
	//}
	
	return value;
	//return (value & 0xFFFFFFFF);
}

//int main(int argc, char** argv)
int main()
{
	unsigned long key;
	int i;
	//unsigned char test[] = {0x00,0x11,0x22,0x33, 0x44,0x55, 0x66, 0x77};
	unsigned char test[] = {0x00,0x00,0x00,0x01, 0x00,0x0, 0x00, 0x01};
	unsigned char test1[] = {0x00,0x00,0x00,0x00, 0x00,0x00, 0x00, 0x02};
		
	//printf("%d,  %s\n", argc, argv[1]);
#if 0			
	gettimeofday(&tpstart,NULL);
	//---------------------------------------------
	key = RSHash(argv[1]);
	//---------------------------------------------
	gettimeofday(&tpend,NULL); 
	timeuse=1000000*(tpend.tv_sec-tpstart.tv_sec)+ 
	tpend.tv_usec-tpstart.tv_usec; 
 	timeuse/=1000000; 
 	printf("------Used Time:%fs-----key=%ld--------\n", timeuse, key); 
 	
 	gettimeofday(&tpstart,NULL);
	//---------------------------------------------
	key = JSHash(argv[1]);
	//---------------------------------------------
	gettimeofday(&tpend,NULL); 
	timeuse=1000000*(tpend.tv_sec-tpstart.tv_sec)+ 
	tpend.tv_usec-tpstart.tv_usec; 
 	timeuse/=1000000; 
 	printf("------Used Time:%fs-----key=%ld--------\n", timeuse, key); 
 	
 	gettimeofday(&tpstart,NULL);
	//---------------------------------------------
	key = PJWHash(argv[1]);
	//---------------------------------------------
	gettimeofday(&tpend,NULL); 
	timeuse=1000000*(tpend.tv_sec-tpstart.tv_sec)+ 
	tpend.tv_usec-tpstart.tv_usec; 
 	timeuse/=1000000; 
 	printf("------Used Time:%fs-----key=%ld--------\n", timeuse, key); 
//#endif

 	gettimeofday(&tpstart,NULL);
	//---------------------------------------------
	key = ELFHash(argv[1]);
	//---------------------------------------------
	gettimeofday(&tpend,NULL); 
	timeuse=1000000*(tpend.tv_sec-tpstart.tv_sec)+ 
	tpend.tv_usec-tpstart.tv_usec; 
 	timeuse/=1000000; 
 	printf("------Used Time:%fs-----key=%ld--------\n", timeuse, key); 

//#if 0 	
 	gettimeofday(&tpstart,NULL);
	//---------------------------------------------
	key = BKDRHash(argv[1]);
	//---------------------------------------------
	gettimeofday(&tpend,NULL); 
	timeuse=1000000*(tpend.tv_sec-tpstart.tv_sec)+ 
	tpend.tv_usec-tpstart.tv_usec; 
 	timeuse/=1000000; 
 	printf("------Used Time:%fs-----key=%ld--------\n", timeuse, key); 
 	
 	gettimeofday(&tpstart,NULL);
	//---------------------------------------------
	key = SDBMHash(argv[1]);
	//---------------------------------------------
	gettimeofday(&tpend,NULL); 
	timeuse=1000000*(tpend.tv_sec-tpstart.tv_sec)+ 
	tpend.tv_usec-tpstart.tv_usec; 
 	timeuse/=1000000; 
 	printf("------Used Time:%fs-----key=%ld--------\n", timeuse, key); 
 	
 	gettimeofday(&tpstart,NULL);
	//---------------------------------------------
	key = DJBHash(argv[1]);
	//---------------------------------------------
	gettimeofday(&tpend,NULL); 
	timeuse=1000000*(tpend.tv_sec-tpstart.tv_sec)+ 
	tpend.tv_usec-tpstart.tv_usec; 
 	timeuse/=1000000; 
 	printf("------Used Time:%fs-----key=%ld--------\n", timeuse, key); 
 	
 	
 	
 	gettimeofday(&tpstart,NULL);
	//---------------------------------------------
	key = APHash(argv[1]);
	//---------------------------------------------
	gettimeofday(&tpend,NULL); 
	timeuse=1000000*(tpend.tv_sec-tpstart.tv_sec)+ 
	tpend.tv_usec-tpstart.tv_usec; 
 	timeuse/=1000000; 
 	printf("------Used Time:%fs-----key=%ld--------\n", timeuse, key); 
#endif
	//---------------------------------------------
	//for (i = 0; i < 255; i++)
	//{
			MyHash(test);
			MyHash(test1);
			//printf("--------key=0x%x--------\n", key); 
			//test[7]++;
	//} 	
}