对整数hash的一些函数的测试

inthash.c

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

uint32_t hashint10(uint32_t h)
{
	h ^= (h >> 20) ^ (h >> 12);
	return h ^ (h >> 7) ^ (h >> 4);
}

uint32_t hashint9(uint32_t h)
{
	h ^= (h >> 20) ^ (h >> 12);
	h ^= (h >>  7) ^ (h >>  4);
	return h;
}

uint32_t hashint8(uint32_t a)
{
	a = a ^ (a >> 4);
	a = (a ^ 0xdeadbeef) + (a << 5);
	a = a ^ (a >> 11);
	return a;
}

uint32_t hashint7(uint32_t a)
{
	a = (a ^ 0xdeadbeef) + (a << 4);
	a = a ^ (a >> 10);
	a = a + (a << 7);
	a = a ^ (a >> 13);
	return a;
}

uint32_t hashint6(uint32_t a)
{
	a = (a + 0x7ed55d16) + (a << 12);
	a = (a ^ 0xc761c23c) ^ (a >> 19);
	a = (a + 0x165667b1) + (a << 5);
	a = (a + 0xd3a2646c) ^ (a << 9);
	a = (a + 0xfd7046c5) + (a << 3);
	a = (a ^ 0xb55a4f09) ^ (a >> 16);
	return a;
}

uint32_t hashint5(uint32_t a)
{
	a = (a + 0x479ab41d) + (a << 8);
	a = (a ^ 0xe4aa10ce) ^ (a >> 5);
	a = (a + 0x9942f0a6) - (a << 14);
	a = (a ^ 0x5aedd67d) ^ (a >> 3);
	a = (a + 0x17bea992) + (a << 7);
	return a;
}

uint32_t hashint4(uint32_t key)
{
	key += ~(key << 15);
	key ^=  (key >> 10);
	key +=  (key << 3);
	key ^=  (key >> 6);
	key += ~(key << 11);
	key ^=  (key >> 16);
	return key;
}

uint32_t hashint3(uint32_t key)
{
	key = ~key + (key << 15);	// key = (key << 15) - key - 1;
	key =  key ^ (key >> 12);
	key =  key + (key << 2);
	key =  key ^ (key >> 4);
	key =  key * 2057;	// key = (key + (key << 3)) + (key << 11);
	key =  key ^ (key >> 16);
	return key;
}

uint32_t hashint2(uint32_t a)
{
	a -= (a << 6);
	a ^= (a >> 17);
	a -= (a << 9);
	a ^= (a << 4);
	a -= (a << 3);
	a ^= (a << 10);
	a ^= (a >> 15);
	return a;
}

uint32_t hashint1(uint32_t a)
{
	a = (a ^ 61) ^ (a >> 16);
	a = a + (a << 3);
	a = a ^ (a >> 4);
	a = a * 0x27d4eb2d;
	a = a ^ (a >> 15);
	return a;
}


#define N_ 102400
#define M_ 2
#define D_ 8
int num[N_];
int set[N_*M_];

void rand_(void)
{
	int i = 0;
	for (i = 0; i < M_ * N_; i++)
		set[i] = random();
}

void loop(void)
{
	int i = 0;
	int d = random();
	int step = random() % 1024 + 1;
	for (i = 0; i < M_ * N_; i++)
		set[i] = d + i * step ;
}

void line(void)
{
	int i = 0;
	for (i = 0; i < M_ * N_; i++)
		set[i] = i;
}

void odd(void)
{
	int i = 0;
	for (i = 0; i < M_ * N_; i++)
		set[i] = i*2 + 1;
}

void even(void)
{
	int i = 0;
	for (i = 0; i < M_ * N_; i++) 
		set[i] = i*2;
}

void other(void)
{
	int i = 0; 
	int d = random() % 32 + 1;
	for (i = 0; i < M_ * N_; i++)
		set[i] = i * d;
}

int test(uint32_t (*hfn)(uint32_t), void (*data)(void))
{
	int i = 0;
	int m[D_] = { 0, };

	for (i = 0; i < N_; i++)
		num[i] = 0;

	data();

	for (i = 0; i < M_ * N_; i++) {
		uint32_t n = hfn(set[i]);
		num[n%N_]++;
	}

	for (i = 0; i < N_; i++) {
		if (num[i] < D_ - 1)
			m[num[i]]++;
		else
			m[D_-1]++;
	}

	for (i = 0; i < D_; i++) {
		int n = 100 * (m[i]/(double)N_);
		printf("%.2d: %lf|", i, m[i]/(double)N_);
		while (n-- > 0)
			printf(".");
		printf("\n");
	}

	return 0;
}

void test_d(const char *msg, uint32_t (*hfn)(uint32_t))
{
	printf("-------------------------------------------------\n");
	printf("TEST %s\n", msg);
	printf("-------------------------------------------------\n");
	printf("random\n"); test(hfn, rand_);
	printf("loop\n");  test(hfn, loop);
	printf("line\n"); test(hfn, line);
	printf("odd\n"); test(hfn, odd);
	printf("even\n");test(hfn, even);
	printf("other\n");test(hfn, other);
	printf("-------------------------------------------------\n");
	printf("\n");
}

#define TEST(fn) test_d(#fn, fn) 

int main(void) 
{
	TEST(hashint1);
	TEST(hashint2);
	TEST(hashint3);
	TEST(hashint4);
	TEST(hashint5);
	TEST(hashint6);
	TEST(hashint7);
	TEST(hashint8);
	TEST(hashint9);

	return 0;
}