smilax:: tiny hash functions in C [Changes]   [Calendar]   [Search]   [Index]   [PhotoTags]   

[Bedstraw] *smilax*
 
[Mega-Changes]
[Mega-Calendar]

tiny hash functions in C

for malloc()ed pointers

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

for english word strings

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]
(No back references.)