smilax:: tiny hash functions in C | [Changes] [Calendar] [Search] [Index] [PhotoTags] |
[Bedstraw] *smilax* |
typedef unsigned u; #define M 31 u hash(u p) { return (p>>6) & M;} u t[M+1]; main() { int i; for (i=0; i<33000;i++) { u p= malloc(M); ++ t[hash(p)]; } for (i=0; i<M;i++) { printf("%u ",t[i]);} return 0; }
$ ./a.out
1032 1032 1032 1032 1032 1032 1032 1032 1032 1032 1032 1032 1032 1032 1032 1032 1032 1030 1031 1030 1030 1031 1030 1031 1030 1030 1031 1030 1031 1030 1030
hash: pushl %ebp movl %esp, %ebp movl 8(%ebp), %eax shrl $6, %eax andl $31, %eax leave ret
typedef unsigned u; #define M 31 u hashstr(char* p) { u x=0; while (*p) {x+=*p++;} return x&M; } u t[M+1]; main() { char b[9999]; int i; while (gets(b)) { ++ t[ hashstr(b) ]; } for (i=0; i<M;i++) { printf("%u ",t[i]);} return 0; }
$ ./a.out < /usr/share/dict/words
1401 1440 1407 1374 1425 1390 1446 1506 1421 1429 1401 1397 1347 1423 1407 1514 1375 1446 1410 1433 1413 1434 1440 1366 1500 1355 1426 1419 1477 1429 1321
hashstr: pushl %ebp movl %esp, %ebp movl 8(%ebp), %edx movb (%edx), %al xorl %ecx, %ecx testb %al, %al je .L27 .p2align 2,,3 .L25: movsbl %al,%eax incl %edx addl %eax, %ecx movb (%edx), %al testb %al, %al jne .L25 .L27: andl $31, %ecx movl %ecx, %eax leave ret
Linux localhost.localdomain 2.6.10-1.9_FC2 #1 Thu Jan 13 17:54:57 EST 2005 i686 athlon i386 GNU/Linux
gcc version 3.3.3 20040412 (Red Hat Linux 3.3.3-7)
glibc-2.3.3-27.1
(last modified 2005-05-12) [Login] |