Tcl Hash Table

Tcl has been designed as a general purpose cross-platform scripting language. Also it can be easily extendable and embeddable. However, not many people know that you can use part of its C library in your current program. Library functions include hash table, dynamic string allocation, a platform and compiler independent interface for memory allocation, regular expression, ... See Tcl library documentation for more details.

You don't have to be a Tcl programmer to use Tcl stuff.

Couple of years ago, one of my project partners used the Tcl hash table implementation in their AutoCAD extension running in Windows environment. Below shows a sample implementation of hash table. As you can see it took only 1.3 milliseconds to locate the value from a key out of a hash table with half a million key-value pairs. BTW, my notebook is running Cygwin in Windows XP (SP2) with Intel Celeron 1.4GHz CPU.

Source code: hash.c

#include <stdio.h>
#include <math.h>
#include "tcl.h"


double elapsedTime(Tcl_Time start, Tcl_Time stop)
{
 double microsecond;

 /* copy from Tcl_TimeObjCmd (tclCmdMZ.c) */
 microsecond = ( ( (double) ( stop.sec - start.sec ) ) * 1.0e6
                      + ( stop.usec - start.usec ) );
 return(microsecond);
}


int main(int argc, char *argv[])
{
 Tcl_HashTable t;
 Tcl_HashEntry *entry, *hasEntry;
 Tcl_Time start, stop;
 int i, max, isNew, lookup;
 char *key, *mesg;
 char keyFormat[]="key-%08d";


 max=500000;
 if ( argc != 2 ) {
  fprintf(stderr, "Usage: %s <1..%d>\n", argv[0], max); 
  exit(1);
 }
 lookup=atoi(argv[1]);

 Tcl_GetTime(&start);
 Tcl_InitHashTable(&t, TCL_STRING_KEYS);
 key=Tcl_Alloc(sizeof(char)*13);
 for ( i=0 ; i<=max ; ++i ) {
  sprintf(key, keyFormat, i);
  entry=Tcl_CreateHashEntry(&t, key, &isNew);
  if ( isNew ) {
   Tcl_SetHashValue(entry, i);
  }
 }
 Tcl_GetTime(&stop);
 printf("Took %lf microseconds to populate hash\n", elapsedTime(start,stop));

 sprintf(key, keyFormat, lookup);
 Tcl_GetTime(&start);
 hasEntry=Tcl_FindHashEntry(&t, key);
 printf("Key: %s, ", key);
 if ( hasEntry ) {
  printf("Value: %d\n", (int)Tcl_GetHashValue(hasEntry));
 } else {
  printf("Value: NOT FOUND\n");
 }
 Tcl_GetTime(&stop);
 printf("Took %lf microseconds to locate \"%s\"\n",elapsedTime(start,stop),key);

 mesg=Tcl_HashStats(&t);
 printf("\nHash Statistics:\n%s\n", mesg);
 Tcl_Free(mesg);
}

Environment, Compilation, Demonstation:

$ /usr/local/bin/tclsh
% parray tcl_platform
tcl_platform(byteOrder) = littleEndian
tcl_platform(machine)   = i686
tcl_platform(os)        = CYGWIN_NT-5.1
tcl_platform(osVersion) = 1.5.25(0.156/4/2)
tcl_platform(platform)  = unix
tcl_platform(user)      = chchan
tcl_platform(wordSize)  = 4
% exit

$ gcc --version
gcc (GCC) 3.4.4 (cygming special, gdc 0.12, using dmd 0.125)
Copyright (C) 2004 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ gcc -o hash.exe -I /usr/local/include -L /usr/local/lib -O3 hash.c -

$ ./hash.exe 2345
Took 967343.000000 microseconds to populate hash
Key: key-00002345, Value: 2345
Took 1333.000000 microseconds to locate "key-00002345"

Hash Statistics:
500001 entries in table, 262144 buckets
number of buckets with 0 entries: 0
number of buckets with 1 entries: 122400
number of buckets with 2 entries: 85450
number of buckets with 3 entries: 28016
number of buckets with 4 entries: 17240
number of buckets with 5 entries: 3784
number of buckets with 6 entries: 3622
number of buckets with 7 entries: 607
number of buckets with 8 entries: 661
number of buckets with 9 entries: 192
number of buckets with 10 or more entries: 172
average search distance for entry: 1.8

$ ./hash.exe 234592302
Took 890433.000000 microseconds to populate hash
Key: key-234592302, Value: NOT FOUND
Took 1342.000000 microseconds to locate "key-234592302"

Hash Statistics:
500001 entries in table, 262144 buckets
number of buckets with 0 entries: 0
number of buckets with 1 entries: 122400
number of buckets with 2 entries: 85450
number of buckets with 3 entries: 28016
number of buckets with 4 entries: 17240
number of buckets with 5 entries: 3784
number of buckets with 6 entries: 3622
number of buckets with 7 entries: 607
number of buckets with 8 entries: 661
number of buckets with 9 entries: 192
number of buckets with 10 or more entries: 172
average search distance for entry: 1.8