1 /*************************************************************************************************
2 * Test unit for hash functions
3 *************************************************************************************************/
4
5
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <time.h>
9 #include <assert.h>
10
11 #define RECBUFSIZ 32
12 #define RANDDATAMIN 4
13 #define RANDDATAMAX 12
14
15
16 /* function prototypes */
17 int main(int argc, char **argv);
18 void usage(const char *progname);
19 int setrandstr(char *buf);
20 void printcol(const char *name, int (*hfunc)(const char *, int), int rnum, int bnum);
21 int dpfirsthash(const char *kbuf, int ksiz);
22 int dpsecondhash(const char *kbuf, int ksiz);
23 int dpthirdhash(const char *kbuf, int ksiz);
24
25
26 /* main routine */
main(int argc,char ** argv)27 int main(int argc, char **argv){
28 int rnum, bnum, i, len;
29 char buf[RECBUFSIZ];
30 rnum = argc > 1 ? atoi(argv[1]) : -1;
31 bnum = argc > 2 ? atoi(argv[2]) : -1;
32 srand(time(NULL));
33 if(rnum > 0 && bnum > 0){
34 printf("number of records: %d\n", rnum);
35 printf("number of buckets: %d\n", bnum);
36 printcol("dpfirsthash", dpfirsthash, rnum, bnum);
37 printcol("dpsecondhash", dpsecondhash, rnum, bnum);
38 printcol("dpthirdhash", dpthirdhash, rnum, bnum);
39 } else if(rnum > 0){
40 for(i = 1; i < rnum; i++){
41 len = sprintf(buf, "%X", i);
42 printf("%s", buf);
43 printf("\t%10d", dpfirsthash(buf, len));
44 printf("\t%10d", dpsecondhash(buf, len));
45 printf("\t%10d", dpthirdhash(buf, len));
46 printf("\n");
47 }
48 } else {
49 usage(argv[0]);
50 }
51 return 0;
52 }
53
54
55 /* show usage and exit */
usage(const char * progname)56 void usage(const char *progname){
57 fprintf(stderr, "%s: test unit for hash functions\n\n", progname);
58 fprintf(stderr, "usage:\n");
59 fprintf(stderr, " %s rnum bnum : print collision rate\n", progname);
60 fprintf(stderr, " %s rnum : print values\n", progname);
61 exit(1);
62 }
63
64
65 /* set randum string and return its length */
setrandstr(char * buf)66 int setrandstr(char *buf){
67 int i, len;
68 len = rand() % (RANDDATAMAX - RANDDATAMIN) + RANDDATAMIN + 1;
69 for(i = 0; i < len; i++){
70 buf[i] = rand() % 256;
71 }
72 buf[len] = '\0';
73 return len;
74 }
75
76
77 /* print collision rate of each hash functioon */
printcol(const char * name,int (* hfunc)(const char *,int),int rnum,int bnum)78 void printcol(const char *name, int (*hfunc)(const char *, int), int rnum, int bnum){
79 int *array, i, len, col;
80 char buf[RECBUFSIZ];
81 if(!(array = calloc(bnum, sizeof(int)))) return;
82 for(i = 1; i <= rnum; i++){
83 len = setrandstr(buf);
84 array[hfunc(buf, len) % bnum]++;
85 }
86 col = 0;
87 for(i = 0; i < bnum; i++){
88 if(array[i] > 1) col += array[i] - 1;
89 }
90 printf("collision rate: %5.2f%% (%8d) by %s\n",
91 ((double)col / (double)rnum) * 100.0, col, name);
92 free(array);
93 }
94
95
96 /* hash function to select a bucket element */
dpfirsthash(const char * kbuf,int ksiz)97 int dpfirsthash(const char *kbuf, int ksiz){
98 const unsigned char *p;
99 unsigned int sum;
100 int i;
101 assert(kbuf && ksiz >= 0);
102 p = (const unsigned char *)kbuf;
103 sum = 751;
104 for(i = 0; i < ksiz; i++){
105 sum = sum * 31 + p[i];
106 }
107 return (sum * 87767623) & 0x7FFFFFFF;
108 }
109
110
111 /* hash function to select a right/left node of binary search tree */
dpsecondhash(const char * kbuf,int ksiz)112 int dpsecondhash(const char *kbuf, int ksiz){
113 const unsigned char *p;
114 unsigned int sum;
115 int i;
116 assert(kbuf && ksiz >= 0);
117 p = (const unsigned char *)kbuf;
118 sum = 19780211;
119 for(i = ksiz - 1; i >= 0; i--){
120 sum = sum * 37 + p[i];
121 }
122 return (sum * 43321879) & 0x7FFFFFFF;
123 }
124
125
126 /* hash function for its applications */
dpthirdhash(const char * kbuf,int ksiz)127 int dpthirdhash(const char *kbuf, int ksiz){
128 const unsigned char *p;
129 unsigned int sum;
130 int i;
131 assert(kbuf && ksiz >= 0);
132 p = (const unsigned char *)kbuf;
133 sum = 774831917;
134 for(i = ksiz - 1; i >= 0; i--){
135 sum = sum * 29 + p[i];
136 }
137 return (sum * 5157883) & 0x7FFFFFFF;
138 }
139
140
141
142 /* END OF FILE */
143