hashtest222.cpp

常用的hash算法APHash

// hashtest222.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream"
#include <time.h>
#include "stdlib.h"
#include "string.h"
#include "time.h"
#include <dos.h>
#include <stdio.h>

using namespace std;

struct blackIP
{
	string ip;
	struct blackIP *next;
};

struct blackIP *blackHash[100];

unsigned int APHash(string str)
{
    unsigned int hash = 0;
    int i;

    for (i = 0; i<str.length(); i++)
    {
        if ((i & 1) == 0)
        {
			hash ^= ((hash << 7) ^ (str[i]) ^ (hash >> 3));
        }
        else
        {
            hash ^= (~((hash << 11) ^ (str[i]) ^ (hash >> 5)));
        }
		
		//printf("hash=%u\n",hash);
    }
    //printf("i=%d\n",i);
    return (hash & 0x7FFFFFFF);
}

int IPMatch(int temp,string s)
{
    struct blackIP *p;
	if(blackHash[temp]!=NULL)
	{
		p=blackHash[temp];
		while(p!=NULL)
		{
			if(strcmp(s.c_str(),(p->ip).c_str())==0)
			{
				return -1;
			}
			p=p->next;
		}
		return 0;
	}
	else return 0;
}

int main(int argc, char* argv[])
{
	clock_t start,end;
	string array[100];
	struct blackIP *p,*q;
	int temp,i,j=0,flag;
	for(i=0;i<100;i++)
		blackHash[i]=NULL;	
	unsigned int hash;
    char str[20];
	string s,t;
	srand( (unsigned)time(NULL)); 
	for(i=0;i<3000;i++)
	{
        s="";
		temp=rand()%256;
		sprintf(str,"%d.",temp);
		t=str;
		s+=t;
		temp=rand()%256;
		sprintf(str,"%d.",temp);
		t=str;
		s+=t;
		temp=rand()%256;
		sprintf(str,"%d.",temp);
		t=str;
		s+=t;
		temp=rand()%256;
		sprintf(str,"%d",temp);
		t=str;
		s+=t;
		//printf("%s\n",s.c_str());
		if((i%30)==0)
		{
			array[j]=s;
			j++;
		} 
		hash=APHash(s);
		hash%=100;
		p=new struct blackIP;
        p->next=NULL;
		p->ip=s;
		if(blackHash[hash]==NULL)
		{
			blackHash[hash]=p;
		}
		else
		{
			q=blackHash[hash];
			blackHash[hash]=p;
			p->next=q;
		}
		
	}
	temp=0;
	int num=0,mm=0;
	start=clock();
	while(mm<300){
	for(i=0;i<100;i++)
	{
        temp=APHash(array[i]);
		temp%=100;
		flag=IPMatch(temp,array[i]);
		if (flag==-1)
		{
			num++;
		}
	}
	mm++;
	}
	
	end=clock();
	int tt=end-start;
	printf("\n%d",num);
	printf("\ntime=%d",tt);

	getchar();
	return 0;
}