Index of /canasai/software/ckhash/ckhash-0.4.2

Icon  Name                      Last modified      Size  Description
[DIR] Parent Directory                               -   
[TXT] Makefile                  25-Jan-2008 19:20   18K  
[   ] Makefile.am               24-Jan-2008 20:49   27   
[TXT] Makefile.in               24-Jan-2008 23:30   18K  
[TXT] aclocal.m4                24-Jan-2008 23:30   30K  
[DIR] autom4te.cache/           24-Jan-2008 23:30    -   
[DIR] build-aux/                24-Jan-2008 23:30    -   
[TXT] config.h                  24-Jan-2008 20:54  967   
[TXT] config.h.in               24-Jan-2008 23:40  821   
[   ] config.log                25-Jan-2008 19:20   14K  
[TXT] config.status             25-Jan-2008 19:20   35K  
[TXT] configure                 24-Jan-2008 23:30  160K  
[   ] configure.ac              24-Jan-2008 20:53  684   
[DIR] cuckoo_hash/              25-Jan-2008 19:21    -   
[TXT] libtool                   24-Jan-2008 20:52  221K  
[   ] stamp-h1                  25-Jan-2008 19:20   23   
[DIR] test/                     25-Jan-2008 19:21    -   

Introduction
------------

Cuckoo Hashing was proposed by Pagh and Rodler (2001). The idea is to build a
dictionary data structure with two hash tables and two different hash functions.
The performance of applying Cuckoo Hashing to the real-world problem is very
promising in terms of memory consumption and lookup time (Jaruskulchai and
Kruengkrai, 2002).

ckhash is an implementation of Cuckoo Hashing that can receive the input in
the form of strings directly. ckhash is a hash package written in C. The original
source code can be found from this url: http://www.it-c.dk/people/pagh/papers/cuckoo.tar.
You can use functions in ckhash by linking the library to your program.
See `test/test-cuckoo.c' for examples of function calls.


Quick Start
-----------

(1) In the ckhash base directory, type:

$ ./configure
$ make

(2) To test that the program works properly, type:

$ cd test
$ ./test-cuckoo linux.words

You should get the following results:

> test insert...
>  45402 entries, table size = 65536
> test lookup...
>  0 errors
> test get...
>  found [ALGOL] value=0
>  found [ANSI] value=1
>  could not find [ansi]
> test delete...
>  0 errors, remain 0 entries, table size = 2


References
----------

Rasmus Pagh and Flemming Friche Rodler. 2001. Cuckoo Hashing, Proceedings of
ESA 2001, Lecture Notes in Computer Science, vol. 2161.

Chuleerat Jaruskulchai and Canasai Kruengkrai. 2002. Building Inverted Files
Through Efficient Dynamic Hashing. Proceedings of the Fifth National Computer
Science and Engineering Conference (NCSEC-2002).