Download code

Jump to: navigation, search

Back to Hash_function_comparison_(C,_sh)

Download for Windows: zip

Download for UNIX: zip, tar.gz, tar.bz2

timecmp.sh

 1 #!/bin/sh
 2 # The authors of this work have released all rights to it and placed it
 3 # in the public domain under the Creative Commons CC0 1.0 waiver
 4 # (http://creativecommons.org/publicdomain/zero/1.0/).
 5 # 
 6 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 7 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 8 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 9 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
10 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
11 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
12 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
13 # 
14 # Retrieved from: http://en.literateprograms.org/Hash_function_comparison_(C,_sh)?oldid=19137
15 
16 
17 cat words words words words words words words words words words >words10
18 for hashfunc in add xor sax sdbm bernstein ; do
19 	printf "% 10s: " "$hashfunc"
20 	time ./hashcmp $hashfunc <words10 >/dev/null
21 done
22 
23 


hijacker
hijacker
hijacker
hijacker

hashcmp.c

 1 /* The authors of this work have released all rights to it and placed it
 2 in the public domain under the Creative Commons CC0 1.0 waiver
 3 (http://creativecommons.org/publicdomain/zero/1.0/).
 4 
 5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 
13 Retrieved from: http://en.literateprograms.org/Hash_function_comparison_(C,_sh)?oldid=19137
14 */
15 
16 
17 #include<stdio.h>
18 #include<string.h>
19 #include<stdlib.h>
20 
21 typedef unsigned long hash_t;
22 
23 hash_t add_hash(const unsigned char *key)
24 {
25 	hash_t h=0;
26 	while(*key) h+=*key++;
27 	return h;
28 }
29 hash_t xor_hash(const unsigned char *key)
30 {
31 	hash_t h=0;
32 	while(*key) h^=*key++;
33 	return h;
34 }
35 hash_t sax_hash(const unsigned char *key)
36 {
37 	hash_t h=0;
38 	while(*key) h^=(h<<5) + (h>>2) + *key++;
39 	return h;
40 }
41 hash_t sdbm_hash(const unsigned char *key)
42 {
43 	hash_t h=0;
44 	while(*key) h=*key++ + (h<<6) + (h<<16) - h;
45 	return h;
46 }
47 hash_t bernstein_hash(const unsigned char *key)
48 {
49 	hash_t h=0;
50 	while(*key) h=33*h + *key++;
51 	return h;
52 }
53 
54 struct hashfunc_s {
55 	char *name;
56 	hash_t (*func)(const unsigned char *key);
57 } funcs[]={
58 	{"add", add_hash},
59 	{"xor", xor_hash},
60 	{"sax", sax_hash},
61 	{"sdbm", sdbm_hash},
62 	{"bernstein", bernstein_hash}
63 };
64 
65 int main(int argc, char *argv[])
66 {
67 	char line[256];
68 	char *p;
69 	hash_t (*hash)(const unsigned char *key)=NULL;
70 	hash_t hsize;
71 	int i;
72 
73 	if(argc>1) {
74 		for(i=0; i<sizeof funcs/sizeof(struct hashfunc_s); ++i) {
75 			if(!strcmp(argv[1], funcs[i].name)) {
76 				hash=funcs[i].func;
77 				break;
78 			}
79 		}
80 		if(!funcs) {
81 			fprintf(stderr, "ERROR: Could not find the %s hash function\n", argv[1]);
82 			exit(EXIT_FAILURE);
83 		}
84 		
85 	} else hash=funcs[0].func;
86 
87 	if(argc>2) hsize=atol(argv[2]);
88 	else hsize=32768;
89 
90 	while(fgets(line, 256, stdin)) {
91 		if((p=strchr(line, '\r'))) *p='\0';
92 		if((p=strchr(line, '\n'))) *p='\0';
93 
94 		printf("%lu\n", hash((unsigned char *)line)%hsize);
95 	}
96 	
97 	return EXIT_SUCCESS;
98 }
99 


hijacker
hijacker
hijacker
hijacker

collcmp.sh

 1 #!/bin/sh
 2 # The authors of this work have released all rights to it and placed it
 3 # in the public domain under the Creative Commons CC0 1.0 waiver
 4 # (http://creativecommons.org/publicdomain/zero/1.0/).
 5 # 
 6 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 7 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 8 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 9 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
10 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
11 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
12 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
13 # 
14 # Retrieved from: http://en.literateprograms.org/Hash_function_comparison_(C,_sh)?oldid=19137
15 
16 
17 
18 case "$1" in
19 	"max")
20 		AWKCMD='{if($1>max) max=$1} END {print max?max:0}'
21 		FMT=" %7s"
22 	;;
23 	"avg")
24 		AWKCMD='{sum+=$1} END {print sum/NR}'
25 		FMT=" % 7.1f"
26 	;;
27 	*)
28 		AWKCMD='{if($1>1) ncoll+=$1} END {print ncoll?ncoll:0}'
29 		FMT=" %7s"
30 esac
31 	
32 echo "      func:size  10      50     100     500    1000    5000   10000   50000  100000  200000"
33 for hashfunc in add xor sax sdbm bernstein ; do
34 	printf "% 10s:" "$hashfunc"
35 	for size in 10 50 100 500 1000 5000 10000 50000 100000 200000; do
36 		head -n $size <words |
37 			./hashcmp $hashfunc $size |
38 			sort -n | 
39 			uniq -c | 
40 			awk "$AWKCMD" |
41 			xargs printf "$FMT"
42 	done
43 	echo
44 done


hijacker
hijacker
hijacker
hijacker

build.log

1 /tmp/litprog6683321/hashcmp.c: In function 'main':
2 /tmp/litprog6683321/hashcmp.c:80:6: warning: the address of 'funcs' will always evaluate as 'true' [-Waddress]


Makefile

# The authors of this work have released all rights to it and placed it
# in the public domain under the Creative Commons CC0 1.0 waiver
# (http://creativecommons.org/publicdomain/zero/1.0/).
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
# 
# Retrieved from: http://en.literateprograms.org/Hash_function_comparison_(C,_sh)?oldid=19137

all: hashcmp

hashcmp: hashcmp.c
	cc -o hashcmp -Wall -ansi -pedantic hashcmp.c


hijacker
hijacker
hijacker
hijacker